Che cosa e' un ‘semiprimo’? e' il prodotto di 2 primi?' (sembra di si)
https://it.wikipedia.org/wiki/Numero_semiprimo
ok
Nel tuo codice:
ok la generazione di 2 primi casuali
che cosa serve ‘chiave’?
a=n%chiave e' il resto della divisione con chiave
b=n-a diventa multiplo di chiave
il primo r=gcd(n,b) cerca il massimo comun divisore tra n, prodotto di 2 primi, e chiave (un numero composto). Molto improbabile che trovi qualcosa
MA
il loop non funziona: diciamo che c=chiave, r=n%k (tanto per scrivere di meno), allora
a=u*c+r
b=(v-u)*c
dove c={{7464623, 1}, {89493587, 1}, {21169599731783, 1}, {70638184945051859196179200432823 , 1}
in
r=gcd(a,b)
non stai facendo altro che cercare un u, multiplo di uno dei fattori di r, che per sua natura difficilmente conterrà primi grandi, e dei fattori di (v-u).
Diciamo che lo trovi abbastanza facilmente.
Ora, questo codice che centra con il tuo algoritmo di cui non posti il codice?
---
Per essere sicuro che l'algoritmo che hai trovato faccia quello che ti aspetti che faccia (cioe' fattorizzare semiprimi efficacemente), come minimo devi vedere come aumenta il tempo in base alla dimensione dei primi, e la devi confrontare con l'algoritmo ‘banale’ che testa tutti i numeri da 2 a sqrt(n). SE il comportamento e' lo stesso a meno di un fattore moltiplicativo costante e/o di un termine costante, allora non hai trovato nulla, mi dispiace.
---
Comunque, se cio' dovesse essere vero, cioe' l'algo ha complessita' INFERIORE a sqrt(n) (ad esempio log(x), ma NON lineare, perche' lineare e' MENO EFFICIENTE di sqrt(x))
1) mandi a ‘remengo' l'intera crittografia commerciale MONDIALE in chiave pubblica (basata sul prodotto di 2 primi da 500/1000 cifre l'uno)
2) ti sei guadagnato la Medaglia Field, la MASSIMA onorificenza in ambito matematico
3) se lo vendi al mercato nero, ci puoi guadagnare una quantita' ASSURDA di soldi, molto probabilmente l'equivalente del PIL di uno stato ;-) Ma forse anche di piu'
4) entrerai nella STORIA, costruiranno statue, scuole a tuo nome, pianeti o stelle con il tuo nome, scriveranno libri sulla tua vita, verrai invitato a talk show, donne bellissime ti si getteranno ai tuoi piedi, i grandi del mondo ti inviteranno ai loro buffet, i cattivi piu' cattivi cercheranno di rapirti per avere l'algoritmo in esclusiva (se vuoi le donne bellissime, ti tocca accettare anche il rovescio della medaglia,ma va ancora bene perche' i cattivi piu'cattivi notoriamente sono attornati dalle donne piu' belle) …
---
I matematici sono gli unici umani che, una volta entrati nella storia, ci rimangono per sempre, al contrario di tutte le altre discipline in cui le teorie vengono sostituite da altre.
Quindi valuta bene ;-)
---
Anche se il semiprimo ha 484 bit, quello che conta e' la dimensione del fattore piu' piccolo, che in questo caso 191,
Fattorizzare numeri da 200 bit (10^60) non e' un grande problema con l'hardware odierno. La fattorizzazione di un numero da 200 bit e' stat fatta nel 2005, 18 anni fa!
Passare da 2^200 (10^60) a 2^500 (3*10^150) vuol dire rendere il problema 2^300 (2*10^90) volte piu' complicato, NON solo 300 volte. Si inizia a ragionare ;-)
---
https://it.wikipedia.org/wiki/RSA_Factoring_Challenge
https://it.wikipedia.org/wiki/Numeri_RSA
Fattorizza i rimanenti numeri RSA (visto che manipoli senza problemi numeri da 5000 cifre binarie, 10^1505) e sei “a cavallo” ;-)