Pollards p-1-methode

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Pollards p-1-methode is een methode voor het ontbinden in priemfactoren. In 1974 publiceerde John Pollard zijn algoritme voor redelijk grote getallen, deze getallen moeten p-1 glad zijn. Wanneer een getal aan deze voorwaarde voldoet, kan met Pollards p-1-methode een priemfactor van dit getal worden gevonden. Het gaat natuurlijk niet wanner het getal een priemgetal is.

B-glad[bewerken]

Een getal heet B-glad (B-smooth) indien elke priemfactor van dat getal kleiner is dan B.

Een voorbeeld:

1620 = 2^2.3^4.5.

1620 is dus 5-glad, omdat geen van zijn priemfactoren groter is dan 5.

Basisgedachten bij Pollards algoritme[bewerken]

Er liggen twee basisgedachten onder Pollards p-1-methode:

  • Als je werkt in de multiplicatieve groep (modulo n), dan werkt dit ook in de multiplicatieve groep (modulo (deler van n)). Dit geldt voor alle delers van n.
  • Er geldt dat a^{p-1}\equiv1(\bmod p)

Dus als p|n en als (p-1)|k, dan geldt dat

a^k\equiv1(\bmod p).

Hieruit volgt dat wanneer a^k-1 deelbaar is door p en ook n deelbaar is door p dat ook dat de grootste gemene deler (a^k-1,n) deelbaar is door p.

Het algoritme van Pollard[bewerken]

Het algoritme van Pollard om een zeker getal n te factoriseren werkt als volgt:

  1. Kies een zeker getal B, niet te groot en niet te klein. Dit getal wordt ingezet als B-smooth getal.
  2. Vind het kleinste gemene veelvoud (de kgv) van al de getallen ≤ B
  3. Kies een willeleurig getal  a<n-1
  4. Bepaal a^k (\bmod n)
  5. Bepaal de ggd d van  ((a^k-1), n)
  6. Als  1 < d < n , dan is d een deler van n
  7. Ontbind n in factoren.

Als het algoritme niet meteen een priemfactor vindt, is het mogelijk te variëren met de gekozen B of a

Voorbeeld[bewerken]

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

  1. Kies B = 8
  2. k = kgv(2, 3 , 4 , 5 , 6 , 7 , 8 ) = 840
  3. Kies a = 2
  4. 2^{840} \equiv53047 (\bmod 540143) zie hieronder uitwerking 1
  5. d = ggd (53046 , 540143) = 421 zie hieronder uitwerking 2
  6.  1 < 421 < 540143 , dan is dus  421 | 540143
  7. 540143 = 421 x 1283

Uitwerking 1[bewerken]

Bepaal  2^{840} (\bmod 540143)

 2^{840} = 2^{512}\times 2^{256}\times 2^{64}\times 2^8
\! 2^8= 256
 2^{32}= 4294967296 \equiv 290303 (\bmod 540143)
 2^{64} \equiv 290303^2=84275831809 \equiv 20234 (\bmod 540143)
 2^{128} \equiv 20234^2= 409414756 \equiv 526505 (\bmod 540143)
 2^{256} \equiv 526505^2= 277207515025 \equiv 185852 (\bmod 540143)
 2^{512} \equiv 185852^2= 34540965904 \equiv 441483 (\bmod 540143)
 2^{840} = 2^{512}\times 2^{256}\times 2^{64}\times 2^8 = 425013705465022464 \equiv 53047 (\bmod 540143)

Uitwerking 2[bewerken]

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[bewerken]