Pollard's rho algorithm
Problemet kommer från boken An Introduction to Mathematical Cryptography:
i , det vill säga att vi vill hitta den diskreta logaritmen av 11 i det ändliga fältet 81799.
Vi ska använda oss av Pollards rho algoritm för att hitta koefficienter så att mod 81799. Vi har då fått en tabell där vi hittar en "match" vid steg 154 av algoritmen med koefficienter .
Vi kan då arrangera om våran ekvation och med hjälp av Fermat's little theorem får vi
.
Vi beräknar den största gemensamma delaren av 13974 och 81798 vilket är 6. Vi kan då faktorera bort 6 i våran kongruens vilket gör att vi får
.
Eftersom att sgd av 2329 och 13633 nu är 1 finns det en invers till 2329, vilket vi beräknar är 5877. Vi multiplicerar inversen på vänster sida i kongruensen och får
,
så t är ekvivalent med 136 modulo 13633. Vi vill ju hitta t i fältet 81798 så vi multiplicerar med 6 och får att
.
Eftersom vi har "förlorat" data när vi arbetade i ett lägre fält, alltså i fältet 13633, så kan ju t vara 816 + 13633k för k i de naturliga talen. Detta ger oss 6 stycken möjliga t (sedan blir det repetition) som finns i denna mängd:
.
Nu krävs det bara att vi testar dessa värden på t i ekvationen men när jag gör det går ingen av dem.
Jag har kollat igenom alla uträkningar steg för steg med en miniräknare men jag har inte hittat något fel.
Jag ska inte låtsas att jag vet någonting om matematisk kryptografi och därmed om rho-algoritmen, men det finns ett steg där jag ser ett fel:

Kort version: 136 borde inte ha multiplicerats med 6.
Lång version:
Om , så innebär det att för något heltal .
Frågan nu är vad :s rest blir vid divisionen med 81798. Med tanke på att 81798=6·13633, så kan du dela upp som en multipel av 6 plus resten, d.v.s. , där och är heltal.
.
Detta medför att , där är ett heltal.