Algoritmo Pohlig-Hellman per calcolare logaritmi discreti

Question

ci sto lavorando codifica the-Hellman Pohlig Algoritmo ma sto avendo problemi a capire i passaggi della procedura in base alla definizione dell'algoritmo.

Andando dal Wiki del algoritmo :

So che la prima parte 1) è quello di calcolare il fattore primo di p-1 -. Che va bene

Comunque, io non sono sicuro di quello che ho bisogno di fare passi in 2) in cui si calcola il co-efficents:

Let x2 = c0 + c1(2). 
125(180/2) = 12590 1 mod (181) so c0 = 0.
125(180/4) = 12545 1 mod (181) so c1 = 0.
Thus, x2 = 0 + 0 = 0.

e 3) mettere i coefficienti insieme e risolvere nel teorema cinese del resto.

può aiutare qualcuno con spiegare questo in parole povere (i) - o pseudocodice. Voglio codice la soluzione io stesso, ovviamente, ma non riesco a fare più progresso se non ho capito l'algoritmo.

Nota: ho fatto un sacco di ricerca di questo e ho letto S. Pohlig e M. Hellman (1978). "Un algoritmo migliorato per il calcolo logaritmi su GF (p) e il suo significato crittografico ma la sua ancora non realmente dare un senso per me.

Grazie in anticipo

Aggiornamento: come mai q (125) Dettaglio costante questo esempio .

Dove come in questo esempio è appare come sta calcolando un nuovo q ogni tempo .

Per essere più precisi non capisco come si calcola il seguente: Ora dividere 7531 da un ^ C0 a ottenere 7531(a^-2) = 6735 mod p.

Answer 1

La partenza di Let con l'idea principale dietro Pohlig-Hellman. Supponiamo che ci viene dato y, g e p e che vogliamo trovare x, tale che

  

y == g ^x (mod p).

(sto usando == per indicare una relazione di equivalenza). Per semplificare le cose, sto anche assumendo che l'ordine di g è p-1, cioè il più piccolo k positivo con 1 == g ^k (mod p) è k = p-1.

Un metodo inefficiente per trovare x, sarebbe quello di provare semplicemente tutti i valori nel range 1 .. p-1. Un po 'meglio è il "Baby-passo da gigante-step" metodo che richiede O ( p ^0,5 ) operazioni aritmetiche. Entrambi i metodi sono abbastanza lenti per i grandi p. Pohlig-Hellman è un miglioramento significativo quando p-1 ha molti fattori. Cioè assumere che

  

p-1 = n r

E allora che Pohlig e Hellman propongono è quello di risolvere l'equazione

  

y ⁿ == (g ⁿ ) ^z   (Mod p).

Se prendiamo i logaritmi alla base g su entrambi i lati, questo è lo stesso di

  

n log _g (y) == log _g (y ⁿ ) == nz (mod p-1).

n può essere diviso fuori, dando

  

log _g (y) == z (r mod).

Quindi x == z (r mod).

Questo è un miglioramento, dal momento che dobbiamo cercare un range 0 .. R-1 per una soluzione di z solo. E ancora: "Baby-passo da gigante-step" può essere utilizzato per migliorare la ricerca per z. Ovviamente, una volta che questa operazione non è ancora una soluzione completa. Cioè si deve ripetere l'algoritmo di cui sopra per ogni fattore primo r di p-1 e quindi di utilizzare il teorema cinese del resto per trovare x dalle soluzioni parziali. Questo funziona bene se p-1 è quadrato libero.

Se p-1 è divisibile per un potere principale poi un'idea simile può essere utilizzato. Per esempio supponiamo che p-1 = m q ^k . Nella prima fase, si calcola z tale che x == z (mod q) come mostrato sopra. Ora vogliamo estendere questo a una soluzione x == z'(q mod ² ). Per esempio. se p-1 = m q ² allora questo significa che dobbiamo trovare z' tali che

  

y ^m == (g ^m ) ^{z '} (mod p).

Dal momento che sappiamo già che z '== z (mod q), z' deve essere nel set {z, z + q, z + 2q, ..., z + (q-1) q}. Ancora una volta potevamo o fare una ricerca esaustiva per z' o migliorare la ricerca con 'baby-passo da gigante-step'. Questa fase viene ripetuta per ogni esponente q, questo è da conoscere x mod q ⁱ abbiamo iterativo derive x mod q ^{i + 1} .

Answer 2

Sono la codifica in su me stesso in questo momento (JAVA). Sto utilizzando Pollard-Rho per trovare i piccoli fattori primi di p-1. Quindi, utilizzando Pohlig-Hellman per risolvere una chiave privata DSA. y = g ^ x. Sto avendo lo stesso problema ..

UPDATE: "Per essere più precisi non capisco come si calcola il seguente:. Ora dividere 7531 da un ^ C0 a ottenere 7531 (a ^ -2) = 6735 mod p"

se si trova l'modInverse di un ^ C0 avrà senso

Saluti