Elliptic curve factorisng in c# 4.0

I am trying to implement Elliptic curve factorisation in c# 4.

I have a few problems though.

Firstly, my version appears to be invredibly slow. Factorising 89041 * 93563 has taken about 5 minutes on a 2GHZ dual core machine and required computing 273!P.

Also I haven't been able to find a profiler for c# 4 to determine what is actually taking the time however I suspect that the O(log(N)) recursive calls in CalcNP are probably not very fast when N >> 100!.

Any help on making this run faster?

Code:

using System;
using System.Collections.Generic;
using bint = System.Numerics.BigInteger;
namespace ECM
{
    public class Program
    {
        static Tuple<bint, bint>[] pow2store; //caches the values of 2^n * P
        static bint Factor;
        static bint max2powstored = 0;
        static int maxexp = 0;
        public static void Main(string[] args)
        {
            pow2store = new Tuple<bint, bint>[100000];
            bint n = 89041 * (bint)93563;
            //curve params from wiki article
            bint x = 1;
            bint y = 1;
            bint a = 5;
            bint b = (y * y - x * x * x - a * x) % n;
            bool ftest = false;
            var P = new Tuple<bint, bint>(x, y);
            pow2store[0] = P;
            var twop = twoP(b, P, n, out ftest);
            pow2store[1] = twop;
            int factsteps = 1;
            bint factorial = 1;
            while (!ftest)
            {
                factorial *= ++factsteps;
                Console.WriteLine("calculating {0}! p", factsteps);
                CalcNP(factorial, b, n, out ftest);
            }
            Console.WriteLine("{0} = {1} * {2}", n, Factor, n / Factor);
            Console.ReadKey(true);
        }

        static Tuple<bint, bint> CalcNP(bint calc, bint b, bint n, out bool res)
        {
            int powguess = (int)Math.Floor(bint.Log(calc, 2));
            powguess = Math.Min(powguess, maxexp);
            bint max2pow = bint.Pow(2, (int)powguess);
            while (max2pow * 2 <= calc)
            {
                max2pow *= 2;
                powguess++;
                if (max2pow > max2powstored)
                {
                    maxexp++;
                    max2powstored = max2pow;
                    pow2store[powguess] = twoP(b, pow2store[powguess - 1], n, out res);
                    if (res)
                    {
                        return pow2store[powguess];
                    }
                开发者_运维百科}
            }
            calc -= max2pow;
            if (calc > 1)
            {
                var Q = CalcNP(calc, b, n, out res);
                if (res)
                {
                    return new Tuple<bint, bint>(0, 0);
                }
                return ECadd(pow2store[powguess], Q, n, out res);
            }
            else
            {
                res = false;
                return pow2store[powguess];
            }
        }

        static Tuple<bint, bint> twoP(bint b, Tuple<bint, bint> P, bint n, out bool Factor)
        {
            bint stop = (3 * P.Item1 * P.Item1 - b) % n;
            bint sbottom = (2 * P.Item2) % n;
            bint inv = ModInv(sbottom, n, out Factor);
            if (Factor)
            {
                return new Tuple<bint, bint>(0, 0);
            }
            bint s = (stop * inv) % n;
            bint xR = (s * s - 2 * P.Item1) % n;
            bint yR = (s * (P.Item1-xR)-P.Item2) % n;
            return new Tuple<bint, bint>(xR, yR);
        }

        static Tuple<bint, bint> ECadd(Tuple<bint, bint> P, Tuple<bint, bint> Q, bint n, out bool Factor)
        {
            bint stop = P.Item2 - Q.Item2 % n;
            bint sbottom = (P.Item1 - Q.Item1) % n;
            bint inv = ModInv(sbottom, n, out Factor);
            if (Factor)
            {
                return new Tuple<bint, bint>(0, 0);
            }
            bint s = (stop * inv) % n;
            bint xR = (s * s - P.Item1 - Q.Item1) % n;
            bint yR = (s * (xR-P.Item1) - P.Item2) % n;
            return new Tuple<bint, bint>(xR, yR);
        }

        static bint ModInv(bint a, bint m, out bool notcoprime)
        {
            bint[] arr = ExtGCD(a, m);
            if (!bint.Abs(arr[2]).IsOne)
            {
                Console.WriteLine("found factor when inverting {0} mod {1}", (a + m) % m, m);
                Factor = arr[2];
                notcoprime = true;
                return 0;
            }
            else
            {
                notcoprime = false;
                return arr[0];
            }
        }

        //extended euclidean
        static bint[] ExtGCD(bint a, bint b)
        {

            bint x = 0;
            bint y = 1;
            bint u = 1;
            bint v = 0;
            while (b != 0)
            {
                bint buffer = b;
                bint q = a / b;
                b = a % b;
                a = buffer;
                buffer = x;
                x = u - q * x;
                u = buffer;
                buffer = y;
                y = v - q * y;
                v = buffer;
            }
            return new bint[] { u, v, a };

        }
    }
}

You do realize that this kind of factorization was designed to be computationally infeasible?

Looking at your code though, there's nothing in there that's exceptionally slow, except maybe the BigInteger type itself. However, if you need arbitrary sized integers that's the price you pay.

If this is just a mathematical exercise I'd consider myself done unless you wanna explore a different factorization algorithm for which there exist no algorithm that terminate with an optimal solution in polynomial time.

I should add that only given that the problem was designed to be hard to compute is there no feasible way to do factorization. I was automatically thinking cracking encryption which might have been confusing to some people.