Test di primalità e fattorizzazione di Lepore-Santo in logaritmo

P_1_6
Fattorizzazione e test di primalità di Lepore-Santo in al massimo logaritmo di (Y-X)/6
Vi mostrerò l'esempio base cioè la fattorizzazione di due numeri primi perchè reiterando il processo si può fattorizzare qualsiasi tipo di numero.
Ogni numero NR (non muliplo di 2 e di 3 ) diviso sei da come decimali 1666p e 8333p (p sta per periodico) poichè per ogni NR modulo sei si avrà

1/6= 0,1666p

il 2 è divisibile per 2

il 3 divisibile per 3

il 4 divisibile per 2

5/6=0,8333p

il 6 divisibile per 2 e per 3

e ciò equivale a dire che partendo da 1 si deve fare una volta +4 una volta +2 e quindi l’insieme dei numeri non muliplo di 2 e di 3 sarà:

1
1+4=5
5+2=7
7+4=11
11+2=13
13+4=17
17+2=19
19+4=23
23+2=25
25+4=29
29+2=31
…..
…..
ecc.ecc.

quindi si può vedere questo:

5*5; 25+(1*30) ; 25+(2*30); 25+(3*30); ecc.
5*7; 35+(1*30) ; 35+(2*30); 35+(3*30); ecc.
7*7; 49+(1*42); 49+(2*42); ecc. ecc.
7*11; 77+(1*42); 77+(2*42); ecc. ecc.

Da ciò possiamo ricavare le tre equazioni:

X^2+n*(X*6)=NR
X*(X+2)+n(X*6)=NR
X*(X+4)+n(X*6)=NR

dove n=(Y-X)/6 nella prima equazione
n=(Y-X-2)/6 nella seconda equazione
n=(Y-X-4)/6 nella terza equazione

Quindi se troviamo il valore di n troviamo X.

Infine diciamo che ogni numero dispari X, non multiplo di 3 si può scrivere sotto la forma:

X=6h+1 ed X=6h+5

----------------------------------------------------------------------------------

Dividiamo i casi :

un numero NR=X*Y

1) se NR=6K+1 utilizzeremo la prima equazione e cioè X^2+6nX=NR

2) NR=6K+5 dovremmo utilizzare entrambe le equazioni, ma questo caso si rifà al primo caso 1)



Il primo caso 1) si divide in due casi

1.1) X e Y sono entrambi nella forma 6h+1

1.2) X e Y sono entrambi nella forma 6h+5



Dividiamo il caso 1.1) in

1.1.1) h è dispari

1.1.2) h è pari



Dividiamo il caso 1.1.2) in

1.1.2.1) h è pari ed è nella forma 2f con f dispari

1.1.2.2) h è pari ed è nella forma 2f con f pari



Dividiamo il caso 1.2) in

1.2.1) h è dispari

1.2.2) h è pari



Dividiamo il caso 1.2.2) in

1.2.2.1) h è pari ed è nella forma 2f con f dispari

1.2.2.2) h è pari ed è nella forma 2f con f pari



Ve li dimostrerò tutti i casi iniziamo da 1.2)



Prendiamo come esempio NR=6001=17*353

X^2+6nX=6001 dobbiamo testare per n=1 e non da X intero quindi continuiamo

dobbiamo testare quindi la 1) quindi 1.1) e 1.2) quindi 1.1.1) e 1.1.2) e 1.2.1) e 1.2.2) quindi quindi i casi da testare saranno 4*2=8.

Io vi farò vedere solo il caso giusto 1.2) X e Y sono entrambi nella forma 6h+5 e 1.2.2) h è pari e 1.2.2.1) h è pari ed è nella forma 2f con f dispari

Quindi testiamo X=6h+5 con h pari.

sostituiamo ad X , 6h+5 ed avremo:

36h^2 + 60h +25 +6nX=6001

sottraiamo -1 da entrambe le parti e dividiamo tutto per 6

6h^2 + 10h +4 +nX=1000

da ciò si può notare che n è pari poichè abbiamo detto che h è pari , X è dispari e 1000 è pari

quindi dobbiamo dividere n per 2 che significa raddoppiare 6X e avremo

X^2+12nX=6001 dobbiamo testare per n=1 e non da X intero quindi continuiamo

36h^2 + 60h +25 +12nX=6001

sottraiamo -1 da entrambe le parti e dividiamo tutto per 12

3h^2 + 5h +2 +nX=500 quindi n è pari

quindi dobbiamo dividere n per 2 che significa raddoppiare 12X e avremo

X^2+24nX=6001 dobbiamo testare per n=1 e non da X intero quindi continuiamo

36h^2 + 60h +25 +24nX=6001

sottraiamo -1 da entrambe le parti e dividiamo tutto per 24

1,5h^2 + 2,5h + 1 + nX=250 quindi se h è pari con h=2f con f dispari,

segue che n è pari

quindi dobbiamo dividere n per 2 che significa raddoppiare 24X e avremo

X^2+48nX=6001 dobbiamo testare per n=1 e non da X intero quindi continuiamo

36h^2 + 60h +25 +48nX=6001

sottraiamo -1 da entrambe le parti e dividiamo tutto per 48

0,75h^2 + 1,25h + 0,5 + nX=125 quindi l’unico valore può essere h=2 ma continuiamo

quindi n è dispari

quindi dobbiamo sottrarre 1 ad n che significa aggiunger 48X

e poi dobbiamo dividere n per 2 che significa raddoppiare 48X e avremo

X^2+96nX +48X=6001 dobbiamo testare per n=1 e non da X intero quindi continuiamo

ora c'è anche 48X che è uguale a 48*(6h+5)=288h + 240 quindi sostituiamo

36h^2 + 60h +25 +96nX + 288h + 240 =6001

sottraiamo -1 da entrambe le parti e dividiamo tutto per 96

0,375h^2 + 0,625h + 0,25 + nX + 3h + 2,5 =62,5

portiamo il 2,5 dall'altra parte e avremo (questo lo faccio solo per semplificare)

0,375h^2 + 0,625h + 0,25 + nX + 3h =60 qui h può essere soltanto 2 quindi potremmo fermarci ma continuiamo

segue che n è dispari

quindi dobbiamo sottrarre 1 ad n che significa aggiunger 96X

e poi dobbiamo dividere n per 2 che significa raddoppiare 96X e avremo

X^2+192nX + 96 X+ 48X=6001 che per n =1

X^2+336X =6001 darò X=17

quindi abbiamo finito gli altri casi ve li faccio vedere tra qualche giorno.

--------------------------------------------------------------------------------------------------------------------------------------------------------



Alberico Lepore, Ruggiero Santo 02/05/2015
http://howtodecodersa.altervista.org/te ... re-in-log/

Risposte
P_1_6
Ho postato il procedimento corretto.
Potrei avere un vostro parere cortesemente
grazie

Rigel1
Io non mi occupo di queste cose, ma mi aspetterei che l'autore di un nuovo algoritmo di fattorizzazione scrivesse qualcosa del tipo: "Ho implementato questo algoritmo e il prodotto di due primi di 100 cifre viene fattorizzato in 30 sec con un PC da 100 GigaFLOPS", oppure "Il test di primalità per un numero primo da 1000 cifre viene eseguito in 30 sec con un PC...".

P_1_6
io non sono ne un programmatore, ne un matematico, purtroppo.
quindi chiedo conferma della correttezza a voi matematici in quanto se corretto impiegherebbe per un numero di 1000 cifre circa 3000 operazioni al massimo.

P_1_6
Miglioramento dell'algoritmo

dividiamo solo tra pari e dispari (ma anche questa distinzione può essere eliminata) per comodità



vi faccio il solito esempio di 6001 con h pari

vado un po veloce ma sono sicuro di farmi capire

Immaginate un albero binario al primo livello per ogni tipo di pari non cambia niente quindi n in questo caso è pari,
X^2+6nX=6001
6h^2 + 10h +4 +nX=1000 n è pari


al secondo livello per ogni tipo di pari non cambia niente quindi n in questo caso è pari,
X^2+12nX=6001
3h^2 + 5h +2 +nX=500 n è pari se h è pari quindi procediamo in entrambi i casi


al terzo livello si fa la distinzione tra h=2k e k è dispari e h=2k e k è pari
h pari
X^2+24nX=6001
1,5h^2 + 2,5h + 1 + nX=250 n è pari se h=2k e k è dispari ed n è dispari se h=2k e k è pari quindi procediamo in entrambi i casi


dal quarto livello in poi parte il vero e proprio algoritmo si fa la distinzione tra h=2k e k=2f con f pari e n è dispari con h=2k e k=2f con f dispari se il ramo è pieno ovvero non ci sono risultati impossibili allora non è il ramo giusto se il ramo non è pieno cioè ha una soluzione impossibile allora è il ramo giusto
h=2k con k pari
X^2+48nX+24X=6001
0,75h^2 + 1,25h + 0,5 + nX +3h+2,5=125 n è pari con h=2k e k=2f con f pari e n è dispari con h=2k e k=2f con f dispari continuiamo

se avessimo provato n è pari con h=2k e k=2f con f pari e n è dispari con h=2k e k=2f con f dispari in entrambi i casi avremmo avuto soluzioni quindi non è il ramo giusto

h=2k con k dispari
X^2+48nX=6001
0,75h^2 + 1,25h + 0,5 + nX =125 n è dispari con h=2k e k=2f+1 con f pari e n è pari con h=2k e k=2f+1 con f dispari continuiamo

se avessimo provato n è pari con h=2k e k=2f+1 con f dispari n risulterebbe non intero quindi è impossibile quindi questo è il ramo giusto


h=2k e k=2f+1 con f pari
X^2+96nX+24X=6001
0,375h^2 + 0,625h + 0,25 + nX + 1,5h + 1,25 =62,5 n è dispari con h=2k e k=2f+1 e f=2d con d pari e n risulterebbe non intero con h=2k e k=2f+1 e f=2d con d dispari pari quindi abbiamo una soluzione impossibile siamo sul ramo giusto



h=2k con h=2k e k=2f+1 e f=2d con d pari
X^2+192nX + 96 X+ 48X=6001 che per n =1

X^2+336X =6001 darà X=17



1)vedere se un equazione é pari o dispari è molto semplice

basta mettere al posto di k i valori di 1 e 2

al posto di f i valori 1 e 2

e così via

2)dal quarto livello in poi se un ramo ha due sotto rami completi non è il ramo giusto

se un ramo ha un sottoramo impossibile allora è il ramo giusto



Spero non ci siano errori

----------------------------------------------------------------------------------------------------------------------------------------------

Alberico Lepore, Ruggiero Santo 05/05/2015

vict85
Devo dire che faccio fatica a seguire la tua prosa.

Comunque l'unico numero pari primo è 2. Quindi se trovi un numero pari è sufficiente dividere per 2 finché non trovi un numero dispari e usare l'algoritmo su quel numero. Quindi ti puoi anche limitare ad analizzare i soli numeri dispari.

Detto questo non sono un esperto di questi algoritmi e mi viene difficile seguire tante equazioni in modulo scritte senza usare le formule (cosa che ormai non dovresti più fare secondo il [regolamento]3_8[/regolamento]) e con una notazione matematica atipica.

D'accordo che non sei né un matematico né un informatico, ma se ti interessano questo tipo di cose non puoi non imparare sia la matematica discreta e la teoria dei numeri elementare che un linguaggio di programmazione. Internet è pieno di corsi di Python e anche la matematica in questione può essere studiata autonomamente (anche da studenti dei primi anni delle superiori o che non sono andati alle superiori). Uno studente delle medie potrebbe essere un po' piccolo per fare da solo, ma con poco aiuto lo capirebbe tranquillamente.


@ Rigel: FLOPS sta per FLoating point Operations Per Seconds quindi a rigore non si dovrebbero usare per operazioni tra interi (specialmente dato che esistono dei processori come gli AMD FX di ultima generazione che hanno 2 core logici/interi per ogni core per i floating points).

P_1_6
ciao vict85 .
Grazie per la tua risposta.
tu hai perfettamente ragione.Spero di imparare presto.

Se ti va puoi dare un occhiata qui
Test di primalità di Lepore-Santo in O(k)
http://howtodecodersa.altervista.org/te ... nto-in-ok/
e sempre se ti va dirmi che ne pensi
grazie ancora

Rigel1
"vict85":
@ Rigel: FLOPS sta per FLoating point Operations Per Seconds quindi a rigore non si dovrebbero usare per operazioni tra interi (specialmente dato che esistono dei processori come gli AMD FX di ultima generazione che hanno 2 core logici/interi per ogni core per i floating points).


Certo, hai ragione; l'ho usato come sinonimo di "PC con una data potenza".

P_1_6
Ciao ho cercato di scrivere l'algoritmo per la decodifica RSA in O(log). Ora per un programmatore è molto semplice testarlo.
http://howtodecodersa.altervista.org/te ... re-in-log/

gugo82
[xdom="gugo82"]Chiudo.

Cercando in giro per il web si trova lo stesso argomento discusso in vari forum ed, in ogni discussione, sono presenti diverse obiezioni alla validità dell'algoritmo, tutte inevase dall'autore.
Pertanto, la validità matematica dell'algoritmo è da ritenersi dubbia.

Dato che non è la rete (tantomeno il nostro forum, che della rete è un cantuccio infinitesimale), bensì la comunità dei matematici a validare scoperte matematiche, esorto vivamente l'autore di questi post, ovviamente e lecitamente convinto della bontà dei propri risultati, a scrivere un articolo scientifico da sottoporre a peer-review presso una qualsiasi rivista scientifica seria di settore.[/xdom]

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.