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  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 
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 
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 
Het algoritme van Pollard om het getal  te factoriseren werkt als volgt:
 Kies een niet te groot en ook niet te klein getal  als grens voor de exponent.
 Bereken het kleinste gemene veelvoud van alle getallen 
 Kies een willeleurig getal 
 Bepaal 
 Bepaal de grootste gemene deler  van  en 
 Als , dan is  een deler van 
 Ontbind  
Als het algoritme niet meteen een priemfactor vindt, is het mogelijk te variëren met de keuze van  en .

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

 Kies 
 
 Kies 
  (zie hieronder uitwerking 1)
  (zie hieronder uitwerking 2)
 , dus 
 540143 = 421 × 1283

Uitwerking 1
Bepaal

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
 Pollards p-1-methode op modular maths

Algoritme