Pollards p–1-methode

Uit Wikipedia, de vrije encyclopedie
(Doorverwezen vanaf Pollards p-1-methode)
Ga naar: navigatie, zoeken

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

De eis voor gladheid van de voorganger van een priemfactor houdt niet alleen in dat -glad is, maar ook dat de voorkomende machten van de priemfactoren van niet groter zijn dan .

Basisgedachten bij Pollards algoritme[bewerken]

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

  • Als een priemfactor is van het samengestelde gehele getal , dan geldt volgens de kleine stelling van Fermat voor alle gehele getallen relatief priem met en voor alle positieve gehele getallen :
  • Als een getal congruent is aan 1 modulo een factor van , dan is de grootste gemene deler van en deelbaar door deze factor.

Dat leidt ertoe dat

,

als een deler is van , en een deler van .

Hieruit volgt weer dat als deelbaar is door en ook deelbaar is door , dat dan ook de grootste gemene deler van en deelbaar is door .

Het idee is om voor de exponent een groot veelvoud van 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 . Begin met een willekeurige , en bepaal iteratief een nieuwe als , waarbij loopt door de machten van deze priemgetallen. Controleer in elk stadium, of eventueel aan het eind, of .

Het algoritme van Pollard[bewerken]

Het algoritme van Pollard om het getal te factoriseren werkt als volgt:

  1. Kies een niet te groot en ook niet te klein getal als grens voor de exponent.
  2. Bereken het kleinste gemene veelvoud van alle getallen
  3. Kies een willeleurig getal
  4. Bepaal
  5. Bepaal de grootste gemene deler van en
  6. Als , dan is een deler van
  7. Ontbind

Als het algoritme niet meteen een priemfactor vindt, is het mogelijk te variëren met de keuze van en .

Voorbeeld[bewerken]

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

  1. Kies
  2. Kies
  3. (zie hieronder uitwerking 1)
  4. (zie hieronder uitwerking 2)
  5. , dus
  6. 540143 = 421 × 1283

Uitwerking 1[bewerken]

Bepaal

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]