Intanto devo (dobbiamo) scusarmi con il nostro “amico/nemico/semplice conoscente” (come dicevano in una vignetta di Sturmtruppen) @claugoit, perche e' statto trattato “male” ingiustamente. Diciamo che la colpa e' 50/50, perche' ci ha messo anche del suo ;-).
Ma passiamo oltre.
Partento dall'assunto che fattorizzare semiprimi grossi “GENERICI” al momento non e' “praticamente possibile” (NON che sia IMPOSSIBILE, serve solo TEMPO!!!!), il suo approccio funziona per UN SOLO motivo: parte da un'APPROSSIMAZIONE del fattore da cercare (la “chiave”) cosa che un normale algoritmo di fattorizzazione non fa (e quindi sta' UN SACCO DI TEMPO).
Ci ho messo un po', la teoria dei numeri la masticavo 30+ anni fa, ma tutto sommato forse non serve andare troppo lontano.
Vediamo un po' come potrebbe essere andata.
Siano ‘p’ e ‘q’ due primi, e ‘k’ quella che viene chiamata ‘chiave’. Mentre ‘p’ e ‘q’ devono essere, appunto, ‘primi’, su ‘k’ non c'e' nessuna particolare restrizione: puo' essere un numero qualsiasi (intero, positivo).
Vengono fatti i seguenti passi:
n=p*q
a=n % k = r
b=n - a = n - r
per comodita' usero' ‘r’ al posto di ‘a’.
Nel ciclo vengono fatte le seguenti operazioni:
g = gcd(a,b)
if g != 1: break;
a = a + k
b = b - k
SE ‘g’ e' diverso da 1, ‘g’ e' un fattore di ‘n’, FINE, ALTRIMENTI si incrementa ‘a’ di ‘k’ e si decrementa ‘b’ di ‘k’
Ora riscriviamo ‘a’ e ‘b’ usando ‘r’ all'interno del loop, dove ‘i’ e' l'i-ma iterazione del ciclo
a = r + i*k
b = n - r - i*k = n - (r + i*k) = n - a
Quindi il GCD diventa:
g = gcd(a, b) = gcd(a, n - a)
dovremmo avere che ‘g’ divide ‘a’ e ‘n-a’, ma poiche' per dividere ‘n-a’ deve poter dividere SIA ‘n’ CHE ‘a’ nello stesso momento, e sappiamo gia' che divide ‘a’, NECCESSARIAMENTE ‘g’ dovra' essere uno dei fattori di ‘n’.
E fin qui non ci piove ;-)
Quindi, tutto quello che ci serve e' trovare un ‘g’ che divida ‘a’.
Ma come e' calcolato ‘a’?
a = n % k
cioe' e' il resto della divisione di ‘n’ con ‘k’, CIOE' ‘n’ puo' essere espresso come
n = k*(n//k) + n%k = k*s + r
('//' divisione intera in Python), con ‘s’ il valore INTERO della divisione di ‘n’ con ‘k’
E QUANTO VALE ‘a’ nel ciclo?
a = i*k + r
QUINDI quando ‘i’ sara' uguale a ‘s’, avremmo che ‘a’ sara' uguale a ‘n’.
-----
Dove sta' il problema? Sta nel fatto che il procedimento funziona per QUALUNQUE semiprimo e QUALUNQUE ‘chiave’, c'e' SOLO da iterare abbastanza volte.
SE uno genera una ‘chiave’ gia' sufficientemente vicina ad uno dei fattori, va da se che lo trova in brevissimo tempo.
-----
Secondo me, partendo dall'ASSIOMA che @claugoit sia “onesto”, nel senso che ha sviluppato il suo lavoro in modo “serio”, da qualche parte sta facendo un ERRORE FONDAMENTALE: in qualche modo si sta' portando dietro l'informazione SPECIFICA sui fattori, e quindi, quando genera la chiave, la genera, SENZA accorgersene, VICINA ad uno di loro.
-----
Tra l'altro, ho provato a modificare la chiave, aggiungendo 1, 10, 100, 1000, ed il sistema continua a funzionare senza problemi (ovviamente ;-) ), l'unica cosa che succede e' che a mano a mano che la chiave si “”allontana"" dal fattore, i tempi di calcolo aumentano (perche' aumentano il numero di iterazioni da fare) e se si allontana abbastanza, possono essere necessari PIU' di 10_000_000 iterazioni e quindi il sistema non trova soluzione.