Der Index-Calculus-Algorithmus

Pakete laden

<< NumberTheory`NumberTheoryFunctions`

<<Statistics`Common`DistributionsCommon`

Problem generieren

p = NextPrime[2^20]

g = 7

MultiplicativeOrder[g, p]

a = Random[Integer, p - 1]
A = PowerMod[g, a, p]

Faktorbasis bauen

B = 200

faktorbasis = Cases[Range[B], x_ /; PrimeQ[x]]

Zufällige Kandidaten testen

kandidaten = 
        Table[Random[Integer, p - 1], {i, 1, 
            1000}];
kandidaten[[{1, 2, 3, 4}]]

ergebnisse = 
        Map[PowerMod[g, #, p]  &, kandidaten];
ergebnisse[[{1, 2, 3, 4}]]

Probedivision durch Primzahlen in der Faktorbasis

SmartFactor[
        xx_] := 
Module[
{x, i, prime, 
          equ}, 
x = xx; 
equ = 
          Table[0, {i, Length[faktorbasis]}]; 
i = 
          0; 
While[
          x > 1 && i ≤ 
              Length[faktorbasis], 
prime = 
            faktorbasis[[i]]; 
While[
            Mod[x, prime] == 0, x = x/prime; 
            equ[[i]] = 
              equ[[i]] + 
                1]; 
i++;
]; 
If[x > 1, Return[False], 
          Return[equ]]
]

Kandidaten durchtesten

faktorisierungen = Map[SmartFactor[#] &, ergebnisse]

Exponenten und Faktorsierungen speichern

paarexpfakt = Transpose[{kandidaten, faktorisierungen}]

Erfolgreiche Faktorisierungen herausfiltern

gutepaare = Cases[paarexpfakt, {x_, y_} /; ListQ[y]]

Length[gutepaare]

Length[faktorbasis]

Gleichungssystem modulo p-1 aufstellen

matrix = Transpose[gutepaare][[2]]

rechteseite = Transpose[gutepaare][[1]]

Lösen modulo der Primfaktoren von p-1

FactorInteger[p - 1]

m2 = LinearSolve[matrix, rechteseite, Modulus -> 2]

m29 = LinearSolve[matrix, rechteseite, Modulus -> 29]

m101 = LinearSolve[matrix, rechteseite, Modulus -> 101]

m179 = LinearSolve[matrix, rechteseite, Modulus -> 179]

Mit chinesischem Restsatz kombinieren

loesungen = 
      Map[ChineseRemainder[#, {2, 29, 101, 179}] &, 
        Transpose[{m2, m29, m101, m179}]]

MatrixForm[{faktorbasis, loesungen}]

A

FactorInteger[A]

FactorInteger[Mod[A*g^12, p]]

A*g^12 == 5^1*53^1 = g^949235*g^203441

949235 + 203441 - 12

PowerMod[g, %, p]