Inspired by https://www.di-mgt.com.au/rsa_factorize_n.html

RecoverPrimeFactors.cs

    private static (BigInteger, BigInteger) RecoverPrimeFactors(BigInteger n, BigInteger e, BigInteger d)
    {
        // Inspired by https://www.di-mgt.com.au/rsa_factorize_n.html
        var k = BigInteger.Subtract(BigInteger.Multiply(d, e), BigInteger.One);
        var primes = new List<int>
        {
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
            31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
            73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
            127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
            179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
            233, 239, 241, 251, 257, 263, 269, 271, 277, 281
        };

        foreach (var g in primes)
        {
            var t = k;
            BigInteger x;
            while (t.IsEven)
            {
                t = BigInteger.Divide(t, 2);
                x = BigInteger.ModPow(g, t, n);
                if (x > BigInteger.One)
                {
                    var y = BigInteger.GreatestCommonDivisor(BigInteger.Subtract(x, BigInteger.One), n);
                    if (y > BigInteger.One)
                    {
                        var p = y;
                        var q = BigInteger.Divide(n, y);
                        if (q > p)
                        {
                            return (q, p);
                        }
                        return (p, q);
                    }
                }
            }
        }

        throw new Exception("Giving up, consider adding larger primes for 'g'");
    }