1 svar
19 visningar
SkogN Online 6
Postad: Idag 11:14

Pollard's rho algorithm

Problemet kommer från boken An Introduction to Mathematical Cryptography:
11t41387 F81799, 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 11α×41387β11γ×41387δ mod 81799. Vi har då fått en tabell där vi hittar en "match" vid steg 154 av algoritmen med koefficienter α154=81756, β154=9527, γ154=67782, δ154=28637.

Vi kan då arrangera om våran ekvation och med hjälp av Fermat's little theorem får vi 

13974t  19110( mod 81799-1).

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 

2329t 3185 (mod 13633).

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

t  5877×3185 (mod 13633),

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 

t  816 mod 81798.

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: 

816, 14449, 28082, 41715, 55348, 68981.

Nu krävs det bara att vi testar dessa värden på t i ekvationen 11t  41387 (mod 81799) 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. 

LuMa07 Online 665
Postad: Idag 13:57 Redigerad: Idag 14:02

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 t136  (mod13633)t \equiv 136 \quad (\mod 13633), så innebär det att t=136+k·13633t = 136 + k \cdot 13633 för något heltal kk.

Frågan nu är vad tt:s rest blir vid divisionen med 81798. Med tanke på att 81798=6·13633, så kan du dela upp kk som en multipel av 6 plus resten, d.v.s. k=κ+6mk = \kappa + 6m, där 0κ<60 \le \kappa < 6 och mm är heltal.

t=136+k·13633t = 136 + k\cdot 13633

=136+(κ+6m)·13633= 136 + (\kappa + 6m) \cdot 13633

=136+κ·13633+6m·13633= 136 + \kappa\cdot 13633 + 6m\cdot13633

=136+κ·13633+m·81798= 136 + \kappa\cdot13633 + m \cdot 81798.

Detta medför att t136+κ·13633  (mod81798)t \equiv 136 + \kappa\cdot13633 \quad (\mod 81798), där 0κ<60 \le \kappa < 6 är ett heltal.

Svara
Close