Test di primalità e fattorizzazione di Lepore
Farò vedere come fattorizzare un numero RSA composto da due primi X , Y ma questo algoritmo è facilmente generalizzabile.
Ve lo spiegherà con un esempio:
Fattorizziamo 247
$X*100-247=(X-3)*100+53 $
$(X-3)*100+53-247=(X-5)*100+06$
$(X-5)*100+06-247=(X-8)*100+59$
$(X-8)*100+59-247=(X-10)*100+12$
$(X-10)*100+12-247=(X-13)*100+65$
$(X-13)*100+65-247=(X-15)*100+18$
$(X-15)*100+18-247=(X-18)*100+71$
$(X-18)*100+71-247=(X-20)*100+24$
Ora osserviamo la sequenza:
$0-53-06-59-12-65-18-71$
come potete notare si muove di $53$ in $53$ eliminando la prima cifra dei numjeri a $3$ cifre se compare
quindi basta fare
(53*2)mod(100)*(prima cifra di 247 cioè 2)
se il risultato di questa moltiplicazione $+53$ fosse minore di $47$ allora si dovrebbe fare (47-moltiplicazione)/53
se è maggiore come in questo caso allora moltiplicazione+53 è fattorizzabile da $X$
e tenendo presente le volte che impiego $53$ cioè si giunge a
$(X-10)*100+12-247=(X-13)*100+65$
Esempio $247$
{{[(int)(100/53)]+1}*53}mod(100)=6
6*2+53=65
Ora vediamo un altro esempio del altro caso $1891$
{{[(int)(1000/109)]+1}*109}mod(1000)=90
(int)(891-90)/109=7
7*109+90=853 (che non si trova l'equazione)
6*109+90=744 OK
Se mi date un numero RSA relativamente basso ve lo fattorizzo a mano
Ve lo spiegherà con un esempio:
Fattorizziamo 247
$X*100-247=(X-3)*100+53 $
$(X-3)*100+53-247=(X-5)*100+06$
$(X-5)*100+06-247=(X-8)*100+59$
$(X-8)*100+59-247=(X-10)*100+12$
$(X-10)*100+12-247=(X-13)*100+65$
$(X-13)*100+65-247=(X-15)*100+18$
$(X-15)*100+18-247=(X-18)*100+71$
$(X-18)*100+71-247=(X-20)*100+24$
Ora osserviamo la sequenza:
$0-53-06-59-12-65-18-71$
come potete notare si muove di $53$ in $53$ eliminando la prima cifra dei numjeri a $3$ cifre se compare
quindi basta fare
(53*2)mod(100)*(prima cifra di 247 cioè 2)
se il risultato di questa moltiplicazione $+53$ fosse minore di $47$ allora si dovrebbe fare (47-moltiplicazione)/53
se è maggiore come in questo caso allora moltiplicazione+53 è fattorizzabile da $X$
e tenendo presente le volte che impiego $53$ cioè si giunge a
$(X-10)*100+12-247=(X-13)*100+65$
Esempio $247$
{{[(int)(100/53)]+1}*53}mod(100)=6
6*2+53=65
Ora vediamo un altro esempio del altro caso $1891$
{{[(int)(1000/109)]+1}*109}mod(1000)=90
(int)(891-90)/109=7
7*109+90=853 (che non si trova l'equazione)
6*109+90=744 OK
Se mi date un numero RSA relativamente basso ve lo fattorizzo a mano
Risposte
Algoritmo per la fattorizzazione in tempi logaritmici
Sia $N=p*q$ dove $N=6*G+1$ e $p=6*a+1$ e $q=6*b+1$ con $G$ pari
$a$,$b$,$G$ numeri naturali
$1
Calcolare:
$a=[6*F-sqrt(6)*sqrt(6*F^2+2*F-G)]/6$
Se $[(12*F-4)-(a-1)*12-8]/6 == (284-6*a^2-2*a)/(6*a+1)$ allora a è la nostra a
Se $[(12*F-4)-(a-1)*12-8]/6 < (284-6*a^2-2*a)/(6*a+1)$ allora F deve scendere
altrimenti $F$ deve salire
P.s. L'ho scritto solo nella forma [ $N=p*q$ dove $N=6*G+1$ e $p=6*a+1$ e $q=6*b+1$ con $G$ pari] ma tutti gli altri casi sono simili
EDIT:HO modificato
Sia $N=p*q$ dove $N=6*G+1$ e $p=6*a+1$ e $q=6*b+1$ con $G$ pari
$a$,$b$,$G$ numeri naturali
$1
Calcolare:
$a=[6*F-sqrt(6)*sqrt(6*F^2+2*F-G)]/6$
Se $[(12*F-4)-(a-1)*12-8]/6 == (284-6*a^2-2*a)/(6*a+1)$ allora a è la nostra a
Se $[(12*F-4)-(a-1)*12-8]/6 < (284-6*a^2-2*a)/(6*a+1)$ allora F deve scendere
altrimenti $F$ deve salire
P.s. L'ho scritto solo nella forma [ $N=p*q$ dove $N=6*G+1$ e $p=6*a+1$ e $q=6*b+1$ con $G$ pari] ma tutti gli altri casi sono simili
EDIT:HO modificato
una cosa che non c'entra quasi niente con quanto detto prima
sia $N=(6*a+1)*(6*b+1)=x*y$
se $x$ o $y$ sono vicini ad un numero $2^k$
allora
$[x-(x-2^k)]*y=N-(x-2^k)*y=(y)*[2^k]$
con $(x-2^k)$ dispari
e ugualmente si fa per $y$
Esempi
$x*y=1045$
$(x-3)*y=1045-3*y, (1045-3*y)/(2^4)=y$
$x=19$ ed $y=55$
$x*y=30096631$
$(x-15)*y=1045-15*y, (30096631-15*y)/(2^12)=y$
$x=4111$ ed $y=7321$
Questa è una cosa vecchia o nuova?
sia $N=(6*a+1)*(6*b+1)=x*y$
se $x$ o $y$ sono vicini ad un numero $2^k$
allora
$[x-(x-2^k)]*y=N-(x-2^k)*y=(y)*[2^k]$
con $(x-2^k)$ dispari
e ugualmente si fa per $y$
Esempi
$x*y=1045$
$(x-3)*y=1045-3*y, (1045-3*y)/(2^4)=y$
$x=19$ ed $y=55$
$x*y=30096631$
$(x-15)*y=1045-15*y, (30096631-15*y)/(2^12)=y$
$x=4111$ ed $y=7321$
Questa è una cosa vecchia o nuova?
Hey
per piacere mi date qualche feedback
Lepore Factorization O(log)
https://www.academia.edu/34557040/Lepor ... ion_O_log_
per piacere mi date qualche feedback
Lepore Factorization O(log)
https://www.academia.edu/34557040/Lepor ... ion_O_log_
Non si capisce. Non ci sono spiegazioni. Solo un po' di numeri tirati li'. L'unica cosa che sembra generale e' la frase all'inizio, ma non c'e' dimostrazione.
Ne ho scritto un'altro che dovrebbe essere k*log_3(n)
https://www.academia.edu/34595630/6_Fat ... _di_Lepore
sarei felice di piegartelo passo passo se mi fai delle domande
https://www.academia.edu/34595630/6_Fat ... _di_Lepore
sarei felice di piegartelo passo passo se mi fai delle domande
Guarda, onestamente appena c'e' la tabella sopra la meta' della prima pagina, non si capisce cosa succede, come scrivi quella tabella o cosa voglia dire.
Ma lasciamo perdere quella per un secondo. Puoi riportare una dimostrazione della prima affermazione che fai? Il primissimo paragrafo, sulla somma di numeri dispari consecutivi. Magari e' facile, ma e' proprio scrivendo bene le dimostrazioni delle cose facili che si imparano a scrivere le dimostrazioni anche delle cose difficili. Quindi ti consiglio di provare a scriverla: non un esempio, non un conto che puo' essere convincente per te ma non per tutti; ti consiglio di scrivere una dimostrazione completa di quello che affermi nel primo paragrafo.
Ma lasciamo perdere quella per un secondo. Puoi riportare una dimostrazione della prima affermazione che fai? Il primissimo paragrafo, sulla somma di numeri dispari consecutivi. Magari e' facile, ma e' proprio scrivendo bene le dimostrazioni delle cose facili che si imparano a scrivere le dimostrazioni anche delle cose difficili. Quindi ti consiglio di provare a scriverla: non un esempio, non un conto che puo' essere convincente per te ma non per tutti; ti consiglio di scrivere una dimostrazione completa di quello che affermi nel primo paragrafo.
Ripeto: e' proprio scrivendo bene le dimostrazioni delle cose facili che si impara a scrivere quelle difficili. In questo documento ci sono delle x e delle y che non si capisce cosa sono, le uguaglianze non sono motivate e in generale qualche parola in piu' (oltre all'uso del termine "Definizione" per le definizioni e non per enunciati con dimostrazione) aiuterebbe.
tu hai ragione io non sono tanto pratico ora provo a spiegare
questa che è quella che serve per la fattorizzazione
Definizione 2
Ogni numero fattorizzabile $N=p*q$ si scrive come somma di numeri dispari consecutivi positivi da $p+q-1$ a $(q-p)+1$
Dimostrazione
$N=((y+1)/2)^2-((x-1)/2)^2=((p+q-1+1)/2)^2-(((q-p)+1 -1)/2)^2=p*q$
Sia N un numero che si scrive come somma di numeri dispari $((y+1)/2)^2-((x-1)/2)^2$
il centro della distanza tra $y$ ed $x$ lo chiamiamo q e la distanza $y-x$ la chiamiamo $2*p-2$
quindi la riscriviamo così $((p+q-1+1)/2)^2-(((q-p)+1 -1)/2)^2$ e quindi andrà da $p+q-1$ a $(q-p)+1$
e quindi così $p*q$
questa che è quella che serve per la fattorizzazione
Definizione 2
Ogni numero fattorizzabile $N=p*q$ si scrive come somma di numeri dispari consecutivi positivi da $p+q-1$ a $(q-p)+1$
Dimostrazione
$N=((y+1)/2)^2-((x-1)/2)^2=((p+q-1+1)/2)^2-(((q-p)+1 -1)/2)^2=p*q$
Sia N un numero che si scrive come somma di numeri dispari $((y+1)/2)^2-((x-1)/2)^2$
il centro della distanza tra $y$ ed $x$ lo chiamiamo q e la distanza $y-x$ la chiamiamo $2*p-2$
quindi la riscriviamo così $((p+q-1+1)/2)^2-(((q-p)+1 -1)/2)^2$ e quindi andrà da $p+q-1$ a $(q-p)+1$
e quindi così $p*q$
Riporto integralmente il paper "Trasformazione del problema della fattorizzazione in un gioco" (per chi non vuole loggarsi ad Academia) dove ogni funzione F,G,H che rispetti queste regole fattorizza in tempi logaritmici
Trasformazione del problema della fattorizzazione in un gioco
Sia T la tabella di due colonne dove nella prima colonna ci saranno gli elementi ai, pari partendo da 2 e nella seconda i numeri naturali bi, partendo da 2.
quindi si avrà
2*2
4*3
6*4
8*5
10*6
12*7
14*8
16*9
18*10
20*11
22*12
24*13
ecc.ecc.
Trovare una delle tre funzione F(ai,bi) ,G(ai,bi) e H(ai,bi)
tali che:
F(ai,bi) passi alla coppia (aj,bj) dove j =< i/2
G(ai,bi) passi all'elemento (aj) , ricordo pari, dove j =< i/2
H(ai,bi) passi all'elemento (bj) , ricordo naturale, dove j =< i/2
Ognuna di questa funzioni applicate alla coppia (ai,bi) e alla coppia (ak,bk) , con k naturale , si possa ripetere solo una volta
Se F(ai,bi)=F(ak,bk)=(am,bm) non esiste F(ap,bp)=(am,bm)
Se G(ai,bi)=G(ak,bk)=(am) non esiste G(ap,bp)=(am)
Se H(ai,bi)=H(ak,bk)=(bm) non esiste H(ap,bp)=(bm)
con i != k !=p
Se si trova una sola delle tre funzioni il problema della fattorizzazione è risolto
Alberico Lepore 23 Settembre 2017
contact twitter @albericolep
Trasformazione del problema della fattorizzazione in un gioco
Sia T la tabella di due colonne dove nella prima colonna ci saranno gli elementi ai, pari partendo da 2 e nella seconda i numeri naturali bi, partendo da 2.
quindi si avrà
2*2
4*3
6*4
8*5
10*6
12*7
14*8
16*9
18*10
20*11
22*12
24*13
ecc.ecc.
Trovare una delle tre funzione F(ai,bi) ,G(ai,bi) e H(ai,bi)
tali che:
F(ai,bi) passi alla coppia (aj,bj) dove j =< i/2
G(ai,bi) passi all'elemento (aj) , ricordo pari, dove j =< i/2
H(ai,bi) passi all'elemento (bj) , ricordo naturale, dove j =< i/2
Ognuna di questa funzioni applicate alla coppia (ai,bi) e alla coppia (ak,bk) , con k naturale , si possa ripetere solo una volta
Se F(ai,bi)=F(ak,bk)=(am,bm) non esiste F(ap,bp)=(am,bm)
Se G(ai,bi)=G(ak,bk)=(am) non esiste G(ap,bp)=(am)
Se H(ai,bi)=H(ak,bk)=(bm) non esiste H(ap,bp)=(bm)
con i != k !=p
Se si trova una sola delle tre funzioni il problema della fattorizzazione è risolto
Alberico Lepore 23 Settembre 2017
contact twitter @albericolep
"P_1_6":
il centro della distanza tra $y$ ed $x$ lo chiamiamo q e la distanza $y-x$ la chiamiamo $2*p-2$
Per precisione questa parte della dimostrazione è così
il centro della distanza tra $y$ ed $x$ lo chiamiamo q e la distanza $y-x$ la chiamiamo $(2*p-2)/2$
Riguardo alla "Trasformazione del problema della fattorizzazione in un gioco"
qualcuno ha trovato una qualsiasi equazione di una qualsiasi di quelle equazioni?
io c'ho riprovato O([log_9(N)]^3)
https://www.academia.edu/35412746/Test_ ... log_9_N_3_
che ne pensate?
https://www.academia.edu/35412746/Test_ ... log_9_N_3_
che ne pensate?
20 points for naming something after yourself. (E.g., talking about the "The Evans Field Equation" when your name happens to be Evans.)(click).
Considerato poi che (guardando sul tuo profilo di academia) hai ben nove documenti dove algoritmi, crivelli e cazzimme portano il tuo nome, direi che siamo ad un invidiabile totale di 180 punti sulla scala Baez. Credo che solo affermando che la terra è a forma di banana dritta faresti di più.
Poi mi chiedo che utilità c'è a mettere queste cose su academia (che è un sito completamente truffa, la cui funzione è solo quella di spammare [strike]caz[/strike] email inutili, ma che in teoria dovrebbe servire ad aggregare la comunità accademica)?
Se è per questo ne ho fatto un altro
13° Primality test and factorization of Lepore
https://www.academia.edu/35431868/13_Pr ... _of_Lepore
13° Primality test and factorization of Lepore
https://www.academia.edu/35431868/13_Pr ... _of_Lepore
Bingo, siamo a 200 punti!
Hey @killing_buddha è una passione che ho non capisco che fastidio ti da?
Comunque il mio spirito pacifista non mi permette di contraccambiare il tuo astio , anzi, vorrei farti mio amico e vorrei chiederti una cosa se la sai?
Dato un numero n ho trovato un algoritmo che è un albero sei-nario cioè ha sei rami e ad ogni livello fa la radice quadrata di n.
Qual'è la sua complessità computazionale?
peace and love
Comunque il mio spirito pacifista non mi permette di contraccambiare il tuo astio , anzi, vorrei farti mio amico e vorrei chiederti una cosa se la sai?
Dato un numero n ho trovato un algoritmo che è un albero sei-nario cioè ha sei rami e ad ogni livello fa la radice quadrata di n.
Qual'è la sua complessità computazionale?
peace and love
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo