Primi Passi dell'Algoritmo

I primi passi di questo algoritmo sono stati nel cercare di capire quale fosse un sistema per avvicinarmi il più possibile alla soluzione della fattorizzazione.  Forse è stato un caso, o una intuizione, ma sta di fatto che dopo aver compiuto i primi passi nella direzione che ho descritto nella pagina di come funziona l'algoritmo, mi sono ritrovato a un tratto a saper fattorizzare numeri grandissimi, 307 cifre e circa 1023 bit.
La prima reazione è stata quella di confrontarmi con algoritmi conosciuti come Pari/gp, ECM, Sympy , Msieve 153, il meglio del meglio per quanto riguarda la fattorizzazione dei semiprimi.
I primi risultati per metà deludenti e per metà entusiasmanti, mi hanno fatto capire che ero sulla strada giusta. 
Mentre su tutte le riviste che io cercavo in internet sull'argomento fattorizzazione, riportavano la voce che era impossibile fattorizzare semiprimi grandi se non con dei tempi biblici, io mi chiedevo di quali semiprimi parlavano e perché io riuscivo a fattorizzare un semiprimo di 307 cifre in un tempo a dir poco quantistico, meno di un secondo.

La prima stesura del mio algoritmo si basava sul quadrato del semiprimo. Questa però funzionava solo per determinati accoppiamenti e mai su basi dispari.
Per esempio n=(2^505+x)*(2^507+y) con la chiave che veniva estratta dall'intero della radice quadrata di n. x e y potevano assumere un valore massimo di  2^50.
Questo concetto è da ribadire bene perché è la proprietà primaria di questo metodo. x e y potevano assumere un qualsiasi numero da 1 a 2^50 e il prodotto derivante dalla moltiplicazione poteva sempre essere riportato al suo moltiplicando con A=n Mod(rq), B=n-A, MCD(A,B)= (2^505+x)

Questo però mi limitava molto in quanto oltre a 1023 bit mi compariva l'errore di out of memory e poi perché lo si poteva adattare solo alla base 2, nonostante molti di questi semiprimi non venissero risolti da nessun algoritmo conosciuto citato sopra. 

Il secondo passo mi portò a elaborare la radice quadrata come intero. La differenza è che questo tipo di radice quadrata è molto più precisa su numeri grandi, ma alla fine il risultato fu devastante perché non riuscivo più a fattorizzare la stessa quantità di numeri, anzi, molti di quelli che fattorizzavo utilizzando la normale radice SQR(n) non venivano più fattorizzati con ISQR(n)

La soluzione la trovai nel modificare l'intero della radice rendendola imprecisa ISQR(n)-10^5
Questo stratagemma mi fece recuperare tutti i semiprimi che riuscivo a fattorizzare con la normale SQR(n) e mi diede dei risultati inaspettati.
Il primo fu quello di superare i 1024 bit, il secondo di poter fattorizzare anche le basi dispari di 3 e 7 ma con il limite che i due esponenti dovevano essere distanti di 4 come per esempio (3^510+x)*(3^514+y).
Inoltre questo mi dava anche la possibilità di mescolare le basi come per esempio quella di 2 con quella di 3 o quella di 3 con quella di 7.

Era un bel passo avanti, anche perché ora la maggior parte dei miei semiprimi non potevano essere fattorizzati dagli algoritmi conosciuti.

Voglio raccontare un aneddoto che poi mi fece arrivare a quello che è attualmente:
Entusiasmato da questi risultati cercai di contattare qualche matematico, professore, università, forum, per cercare di capire cosa avevo scoperto e come potesse influire sulla fattorizzazione di grandi semiprimi. La risposta fu un totale silenzio e a volte, nei forum, anche molto offensivi che mi accusavano di barare. Un professore in pensione vide la cosa interessante e cominciammo a parlare. Dopo poco però mi disse che non valeva niente perché per fattorizzare i miei semiprimi io dovevo sempre analizzare i due fattori primi. Seguendo le mie indicazione di come analizzavo i due fattori primi, e come il GC57 riusciva a riportare il semiprimo allo stato dei due fattori, lui riusciva sempre a risolvere la fattorizzazione che io gli proponevo anche se gli algoritmi conosciuti non riuscivano a fattorizzarli. Questo era possibile perché le mie indicazione lo portavano a creare un piccolo programma che partendo da una base aumentava l'esponente fino a raggiungere la chiave. In fin dei conti le basi erano poche, 2, 3 ,7 ,4, 8. Anche se mischiavo la base 2 con 3, la chiave si trovava nella base 2, o 3 con 7, la chiave si trovava nella base 3.

Questo mi ha dato un nuovo input e cioè la parte debole di questo algoritmo, inteso come creare semiprimi che solo il GC57 potesse fattorizzarli, era la base.      



  


AI Website Software