Test di primalità e fattorizzazione di Lepore

[P_1_6]

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

[P_1_6]

Hey amici potreste dare uno sguardo?
Che ne pensate?

Testing m, r, s, t, v, z,

n-m=1
m-r=1
r-s=1
s-t=1
t-v=1
v-z=1
etc.etc.

[P_1_6]

ragazzi qualcuno che lo implementi c'è?
E' in O(log_2())

[P_1_6]

Adesso dovrebbe essere corretto

[P_1_6]

Algoritmo di Natale
17° Test di primalità e fattorizzazione di Lepore

[P_1_6]

mi dispiace aver sbagliato.
il tempo impiegato è 2^x dove x è la profondità dell'albero.
x dipende da come è composto il numero e non dalla dimensione delle cifre

[P_1_6]

Questa è la volta buona

https://www.academia.edu/36782326/Fatto ... 4_O_log_n_

Che ne pensate?