Pollards p-1-methode

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

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

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

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

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

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

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