Factorisation de la courbe elliptique en C# 4.0

Question

J'essaie de mettre en œuvre Elliptic curve factorisation en C# 4.
J'ai cependant quelques problèmes.
Premièrement, ma version semble être invinciblement lente. Factoriser 89041 * 93563 a pris environ 5 minutes sur une machine dual core 2GHZ et a nécessité un calcul 273! P.
Aussi je n'ai pas pu trouver un profileur pour C# 4 pour déterminer ce qui prend réellement le temps mais je suspecte que les appels récursifs O (log (N)) dans CalcNP ne sont probablement pas très rapides quand N >> 100 !

Une aide d'exécution plus rapide?

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

     } 
    } 
} 

Answer 1

Vous vous rendez compte que ce genre de factorisation a été conçu pour être infaisable? Cependant, en regardant votre code, il n'y a rien d'exceptionnellement lent, sauf peut-être le type BigInteger lui-même. Cependant, si vous avez besoin d'entiers de taille arbitraire, c'est le prix que vous payez. Si c'est juste un exercice mathématique, je me considérerais comme fait, sauf si vous voulez explorer un algorithme de factorisation différent pour lequel il n'existe aucun algorithme qui se termine avec une solution optimale en temps polynomial.

Je devrais ajouter que seulement dans la mesure où le problème a été conçu pour être difficile à calculer, il n'y a pas de façon possible de procéder à la factorisation. Je pensais automatiquement cryptage de cryptage qui pourrait avoir été source de confusion pour certaines personnes.