Pollards p–1-methode

Pollards p–1-methode is een methode voor het ontbinden van een geheel getal in priemfactoren. In 1974 publiceerde John Pollard zijn algoritme voor redelijk grote getallen. Deze getallen moeten zodanig zijn dat van elke priemfactor p {\displaystyle p} de voorganger p − 1 {\displaystyle p-1} een glad getal is. Als een getal aan deze voorwaarde voldoet, kan met Pollards p–1-methode een priemfactor van dit getal worden gevonden.

Gladheid

De eis voor gladheid van de voorganger p − 1 {\displaystyle p-1} van een priemfactor p {\displaystyle p} houdt niet alleen in dat p − 1 {\displaystyle p-1} B {\displaystyle B} -glad is, maar ook dat de voorkomende machten van de priemfactoren van p − 1 {\displaystyle p-1} niet groter zijn dan B {\displaystyle B} .

Basisgedachten bij Pollards algoritme

Er liggen twee basisgedachten ten grondslag aan Pollards p–1-methode.

  • Als p {\displaystyle p} een priemfactor is van het samengestelde gehele getal n {\displaystyle n} , dan geldt volgens de kleine stelling van Fermat voor alle gehele getallen a {\displaystyle a} relatief priem met p {\displaystyle p} en voor alle positieve gehele getallen k {\displaystyle k} :
a k ( p − 1 ) ≡ 1 ( mod p ) {\displaystyle a^{k(p-1)}\equiv 1{\pmod {p}}}
  • Als een getal x {\displaystyle x} congruent is aan 1 modulo een factor van n {\displaystyle n} , dan is de grootste gemene deler van x − 1 {\displaystyle x-1} en n {\displaystyle n} deelbaar door deze factor.

Dat leidt ertoe dat

a k ≡ 1 ( mod p ) {\displaystyle a^{k}\equiv 1{\pmod {p}}} ,

als p {\displaystyle p} een deler is van n {\displaystyle n} , en p − 1 {\displaystyle p-1} een deler van k {\displaystyle k} .

Hieruit volgt weer dat als a k − 1 {\displaystyle a^{k}-1} deelbaar is door p {\displaystyle p} en ook n {\displaystyle n} deelbaar is door p {\displaystyle p} , dat dan ook de grootste gemene deler van a k − 1 {\displaystyle a^{k}-1} en n {\displaystyle n} deelbaar is door p {\displaystyle p} .

Het idee is om voor de exponent een groot veelvoud van p − 1 {\displaystyle p-1} te nemen, door een getal met zeer veel priemfactoren te kiezen. Over het algemeen kiest men het product van machten van alle priemgetallen kleiner dan een bepaalde grens B {\displaystyle B} . Begin met een willekeurige x {\displaystyle x} , en bepaal iteratief een nieuwe x {\displaystyle x} als x w ( mod n ) {\displaystyle x^{w}{\pmod {n}}} , waarbij w {\displaystyle w} loopt door de machten van deze priemgetallen. Controleer in elk stadium, of eventueel aan het eind, of g g d ( x − 1 , n ) ≠ 1 {\displaystyle {\rm {ggd}}(x-1,n)\neq 1} .

Het algoritme van Pollard

Het algoritme van Pollard om het getal n {\displaystyle n} te factoriseren werkt als volgt:

  1. Kies een niet te groot en ook niet te klein getal B {\displaystyle B} als grens voor de exponent.
  2. Bereken het kleinste gemene veelvoud van alle getallen ≤ B {\displaystyle \leq B}
  3. Kies een willeleurig getal a < n − 1 {\displaystyle a<n-1}
  4. Bepaal a k ( mod n ) {\displaystyle a^{k}{\pmod {n}}}
  5. Bepaal de grootste gemene deler d {\displaystyle d} van a k − 1 {\displaystyle a^{k}-1} en n {\displaystyle n}
  6. Als 1 < d < n {\displaystyle 1<d<n} , dan is d {\displaystyle d} een deler van n {\displaystyle n}
  7. Ontbind n {\displaystyle n}

Als het algoritme niet meteen een priemfactor vindt, is het mogelijk te variëren met de keuze van B {\displaystyle B} en a {\displaystyle a} .

Voorbeeld

Hoe kunnen we het getal 540143 ontbinden in priemfactoren met behulp van het algoritme van Pollard?

  1. Kies B = 8 {\displaystyle B=8}
  2. k = k g v ( 2 , 3 , 4 , 5 , 6 , 7 , 8 ) = 840 {\displaystyle k={\rm {kgv}}(2,3,4,5,6,7,8)=840}
  3. Kies a = 2 {\displaystyle a=2}
  4. 2 840 ≡ 53047 ( mod 540143 ) {\displaystyle 2^{840}\equiv 53047{\pmod {540143}}} (zie hieronder uitwerking 1)
  5. d = g g d ( 53046 , 540143 ) = 421 {\displaystyle d={\rm {ggd}}(53046,540143)=421} (zie hieronder uitwerking 2)
  6. 1 < 421 < 540143 {\displaystyle 1<421<540143} , dus 421 | 540143 {\displaystyle 421|540143}
  7. 540143 = 421 × 1283

Uitwerking 1

Bepaal 2 840 ( mod 5 40143 ) {\displaystyle 2^{840}({\bmod {5}}40143)}

2 840 = 2 512 × 2 256 × 2 64 × 2 8 {\displaystyle 2^{840}=2^{512}\times 2^{256}\times 2^{64}\times 2^{8}}
2 8 = 256 {\displaystyle 2^{8}=256}
2 32 = 4294967296 ≡ 290303 ( mod 5 40143 ) {\displaystyle 2^{32}=4294967296\equiv 290303({\bmod {5}}40143)}
2 64 ≡ 290303 2 = 84275831809 ≡ 20234 ( mod 5 40143 ) {\displaystyle 2^{64}\equiv 290303^{2}=84275831809\equiv 20234({\bmod {5}}40143)}
2 128 ≡ 20234 2 = 409414756 ≡ 526505 ( mod 5 40143 ) {\displaystyle 2^{128}\equiv 20234^{2}=409414756\equiv 526505({\bmod {5}}40143)}
2 256 ≡ 526505 2 = 277207515025 ≡ 185852 ( mod 5 40143 ) {\displaystyle 2^{256}\equiv 526505^{2}=277207515025\equiv 185852({\bmod {5}}40143)}
2 512 ≡ 185852 2 = 34540965904 ≡ 441483 ( mod 5 40143 ) {\displaystyle 2^{512}\equiv 185852^{2}=34540965904\equiv 441483({\bmod {5}}40143)}
2 840 = 2 512 × 2 256 × 2 64 × 2 8 = 425013705465022464 ≡ 53047 ( mod 5 40143 ) {\displaystyle 2^{840}=2^{512}\times 2^{256}\times 2^{64}\times 2^{8}=425013705465022464\equiv 53047({\bmod {5}}40143)}

Uitwerking 2

Bepaal de ggd van 540143 en 53046 met het algoritme van Euclides

540143 = 10 × 53046 + 9683
53046 = 5 × 9683 + 4631
9683 = 2 × 4631 + 421
4631 = 11 × 421

Dus ggd( 540143 , 53046 ) = 421

Bronnen

  • (en) Pollards p-1-methode op modular maths