Dunque se ricordo bene nei logaritmi discreti si usa un "adattamento" dell'algoritmo che individua un gruppo ciclico
relativo ad una certa base modulare.... non e' uguale all'algoritmo usato per la fattorizzazione, ma il nocciolo
e' sempre l'individuazione di un gruppo ciclico, cosa che permette di evitare la memorizzazione degli elementi gia' setacciati...
relativo ad una certa base modulare.... non e' uguale all'algoritmo usato per la fattorizzazione, ma il nocciolo
e' sempre l'individuazione di un gruppo ciclico, cosa che permette di evitare la memorizzazione degli elementi gia' setacciati...
Allora, riguardando bene:
nella scelta dei parametri a' e b' necessari per passare da un elemento
Y = aP + bQ al successivo elemento Y'= a'P + b'Q
si usa effettivamente una specie di quadrato (ogni elemento Y viene raddoppiato in Y+Y=2Y , almeno se si trova in una certa parte dello spazio, il che equivale ad elevare alla seconda). La scelta dei parametri (a',b') è ovviamente deterministica ma soprattutto dipende solo dai valori (a,b) dell'elemento precedente.
Quindi si simula solo la classica passeggiata casuale nello spazio di tutti gli elementi della curva.
Si può quindi non tenere traccia di tutti gli elementi Y=aP+bQ generati poichè si sa che a un certo punto si deve entrare in un "sottogruppo" ciclico della curva ellittica (la parte chiusa della lettera rho, anche se non è propriamente un sottogruppo nel senso matematico del termine; non appena si genera una collisione gli elementi per forza iniziano a ripetersi a causa del modo univoco con cui viene generato un elemento a partire dal precedente).
L'entrata nel ciclo (o la sua "chiusura", se si immagina visivamente la lettera rho greca) è causata quindi da una prima collisione (vedi paradosso dei compleanni, che avviene in media dopo rad(n) passi), prima collisione però (e qui c'è il punto importante) che non è necessario che sia rilevata (quindi non c'è necessità di memorizzare enormi montagne di dati!). A partire da quella prima collisione si genera quindi (a causa del metodo deterministico) sempre la stessa sequenza di elementi (che formano appunto un ciclo); da notare che il ciclo è una sottosequenza del percorso effettuato per arrivare alla prima collisione, quindi il ciclo stesso non è costituito da più di rad(n) punti.
Per rilevare una qualsiasi ripetizione tra due elementi (percorrendo il ciclo si deve tornare ogni volta sugli stessi elementi, non serve individuare il primo elemento che si ripete, quello che ha chiuso il ciclo!) è sufficiente usare un buffer con pochissimi dati in memoria; i dati vengono aggiornati di tanto in tanto mediante un algoritmo che non impatta in maniera sostanziale sul lavoro computazionale complessivo fino a che non si realizza una collisione anche all'interno del buffer di memoria (collisione che deve arrivare per forza quando si è dentro un ciclo, si registra così una collisione utilizzabile dal punto di vista pratico per ricavare la chiave privata).
L'algoritmo di rilevazione della collisione all'interno del buffer nel caso migliore trova la collisione appena si è entrati nel ciclo, nel caso peggiore impiega un numero di iterazioni ulteriori pari alla lunghezza del ciclo stesso
L'algoritmo è il seguente (tratto da https://maths-people.anu.edu.au/~brent/pd/rpb231.pdf):
Quote
2.1.3 Floyd’s Cycle-finding Algorithm
In order to minimise the storage requirement, a collision-detection algorithm can be applied with a
small penalty in the running time. Collision-detection algorithms do not exploit the group structure and are
generic. In Pollard’s paper, Floyd’s algorithm is applied. It compares each pair of Yi and Y2i for i > 1.
Floyd’s algorithm is based on the following fact.
Theorem 2.3 (Knuth (1997)). For a periodic se-quence Y0, Y1, Y2 · · ·, there exists an i > 0 such that
Yi = Y2i and the smallest such i lies in the range µ <= i <= µ + λ.
Floyd’s algorithm uses only a small constant amount of storage. The best running-time requires µ
iterations and the worst takes µ + λ iterations.
In order to minimise the storage requirement, a collision-detection algorithm can be applied with a
small penalty in the running time. Collision-detection algorithms do not exploit the group structure and are
generic. In Pollard’s paper, Floyd’s algorithm is applied. It compares each pair of Yi and Y2i for i > 1.
Floyd’s algorithm is based on the following fact.
Theorem 2.3 (Knuth (1997)). For a periodic se-quence Y0, Y1, Y2 · · ·, there exists an i > 0 such that
Yi = Y2i and the smallest such i lies in the range µ <= i <= µ + λ.
Floyd’s algorithm uses only a small constant amount of storage. The best running-time requires µ
iterations and the worst takes µ + λ iterations.
