c＃中的椭圆曲线因子4.0

Question

我想在c＃4中实现Elliptic curve factorisation。
虽然我有一些问题。
首先，我的版本显得非常慢。分解89041 * 93563在2GHZ双核机器上花费了大约5分钟，并且需要计算273！P。
此外，我还没有找到c＃4的分析器来确定什么是实际采取的时间，但我怀疑在CalcNP O（log（N））递归调用可能不是很快，当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类型本身外，没有什么特别慢的东西。但是，如果你需要任意大小的整数，那就是你付出的代价。

如果这只是一个数学练习，我会认为自己完成了，除非你想探索一个不同的因式分解算法，其中不存在以多项式时间终止于最优解的算法。

我应该补充一点，只有在考虑到问题的设计难以计算的情况下，才有可行的方法进行分解。我自动思考破解加密这可能会让某些人感到困惑。