Эллиптическая кривая factorisng в C# 4.0

Question

Я пытаюсь реализовать Elliptic curve factorisation в C# 4.
У меня есть несколько проблем.
Во-первых, моя версия кажется невероятно медленной. Factorising 89041 * 93563 занял около 5 минут на двухъядерном процессоре 2GHZ и потребовал вычислить 273! P.
Также я не смог найти профайлер для C# 4, чтобы определить, что на самом деле занимает время, однако я подозреваю, что рекурсивные вызовы O (log (N)) в CalcNP, вероятно, не очень быстрые, когда N >> 100 !.

Любая помощь в ускорении этой работы?

Код:

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 }; 

     } 
    } 
} 

Answer 1

Вы понимаете, что этот вид факторизации был разработан, чтобы быть вычислительно неосуществимо?

Если вы посмотрите на свой код, в нем нет ничего необыкновенно медленного, кроме самого типа BigInteger. Однако, если вам нужны целые числа произвольного размера, это цена, которую вы платите.

Если это всего лишь математическое упражнение, я бы подумал о себе, если вы не захотите изучить другой алгоритм факторизации, для которого не существует алгоритма, который заканчивается оптимальным решением в полиномиальное время.

Я должен добавить, что только при условии, что проблема была сконструирована так, что ее сложно вычислить, нет никакого возможного способа делать факторизацию. Я автоматически думал взломать шифрование, что, возможно, было смущает некоторых людей.