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]

Ci sono altri casi vi mostro degli esempi:

1457
(543*2)mod(1000)=86
(int)1000/86=11
11*86-543=403

2867
(133*8)mod(1000)=64
64+8*133=1128

[P_1_6]

Cercherò di generalizzare ciò che ho trovato così che altri possano ripartire da ciò che ho trovato
Per fattorizzare ad esempio $45459487$ si usa questo metodo:

$x*10000000-(((4554134539)/4540513)*45459487)=(4554134539-4540000000)$
https://www.wolframalpha.com/input/?i=x ... 0000000%29

l'unica incognita è questo numero $4554134539$

ma sappiamo che è maggiore di $4540000000$ ed è diviso da $4540513$

quindi $4540000000/4540513=999,.....$

$4540513*1000=....$
$4540513*1001=.....$
$4540513*1002=....$
$4540513*1003=......$

quindi vediamo gli esempi precedenti come diventerebbero

$247$
https://www.wolframalpha.com/input/?i=x ... 265-200%29
$1891$
https://www.wolframalpha.com/input/?i=x ... 44-1000%29
$1457$
https://www.wolframalpha.com/input/?i=X ... 88-1000%29
$2867$
https://www.wolframalpha.com/input/?i=X ... 93-2000%29

Così ho voluto generalizzare un metodo

[P_1_6]

Riprendendo il primo e secondo post per il numero $45459487$
si avrà

$454*3621539-359*4540513=14134539$

ma come ci calcoliamo il $359$?

io lo calcolo approsimativamente così (ma sicuramente si può trovare preciso con un po di impegno)

$Z=(454*3621539)/4540513$

https://www.wolframalpha.com/input/?i=Z ... %2F4540513

quindi $362--$

[P_1_6]

Ma da dove esce questo $454$

$45459487+4540513=50000000$

$10000000$ numero di cifre del numero da fattorizzare

$(Z*5)*10000000=Z*(50000000)$

$(Z*5-454)*10000000=(Z*(50000000)-4540000000)$

$(Z*5-454)*10000000=(Z*(45459487+4540513)-4540000000)$

$(Z*5-454)*10000000-(Z*45459487)=(Z*4540513-4540000000)$

$x=1003*5-454$

[P_1_6]

Non è importante il $454$ ma la forma di $X$ che è $X=5A+C$ e dal crivello di lepore possiamo dire che $X$ deve essere anche $1$

quindi $C$ è nella forma $5n-1$

Scegliamo ad esempio $459$


$459*3621539-K*4540513=4540513*Z-4590000000$

quindi $(459*3621539)/4540513=366$

quindi non sapendo dove andare proviamo $365$ e $367$

dopo $364$ e $368$

dopo $363$ e $369$

arrivando $373$

$459*3621539-373*4540513=4540513*Z-4590000000$

quindi si ha $Z=1004$

$X=5*1004-459=4561$

Ci resta da stabilire da che numero in poi possiamo scegliere il numero

-------------------------------------------------------------------------------------------------------
EDIT

Ho capito

[P_1_6]

In più possiamo osservare

$(459*3621539)mod(4540513)=458643$

$459*3621539-K*4540513=4540513*n+458643$

per $n=-7$ si ha $K=373$


$(454*3621539)mod(4540513)=513000$

$454*3621539-K*4540513=4540513*n+513000$

per $n=3$ si ha $K=359$

Ora si possono osservare una miriade di procedimenti

[P_1_6]

Vediamo un metodo per fattorizzare un numero

Vediamo tutti i procedimenti da fare per fattorizzare $45459487=p*q$

La prima cifra $4$ + $1$ ci da la forma di $p$ cioè $p=5Z-C$

imponiamo $5Z-C=1$ e avremo la forma di $C$ ovvero $5m-1$

togliamo la prima cifra al numero da fattorizzare e cioè $5459487$ e facciamo $10000000-5459487=4540513$

poi $4540513* [(Intero)(10000000/4540513+1)]=13621539$

poi $13621539-10000000=3621539$

quindi $C*3621539-K*4540513=4540513*n+458643$

la $n$ può assumere in questo caso valori da $0$ a $10$ poichè

$p*10000000-(Z*45459487)=4540513*n+458643$

infatti $45459487/4540513=10,....$

quindi andremo a provare tutti i valori di $n$ possibili

nel nostro caso $n=3$

andando a mettere in $C*3621539-K*4540513=4540513*n+(C*3621539)mod(4540513)$

$((C*3621539-(C*3621539)mod(4540513))/4540513=(K+n)$

i valori possibili di $C$ vediamo che $K+n$ si muove di $4$ in $4$ e che $(K+n)mod(4)=2$

quindi $K+n$ lo scriviamo come $4s-2$


analogamente andando a mettere in $4540513*n+(C*3621539)mod(4540513)=(Z)*4540513-C*10000000$

i valori possibili di $C$ vediamo che $Z$ si muove di $11$ in $11$ e che $(Z)mod(11)=2$

quindi $Z$ lo scriviamo come $11t+2$

Ho notato che $s=m=t$ (Questo pezzo potrebbe non essere giusto ancora non lo provo)

Quindi possiamo procedere così

$C*3621539-K*4540513=4540513*n+(C*3621539)mod(4540513)$

$(11*s+2)*4540513-(5*s-1)*10000000=3*4540513 $

$s=100,....$

e ovviamente scalando si arriva a $s=91$

quindi $p=5Z-C=55s+10-5s+1=50s+11=4561$

------------------------------------------------------------------------------------------------------------------------------------
EDIT:

Questo numero $(C*3621539)mod(4540513)$ è di 7 cifre

se becchiamo le prime 2 cifre avremo

$(11*s+2)*4540513-(5*s-1)*10000000=3*4540513+500000$

quindi $s=91,....$

quindi troveremo il nostro s in al massimo $45*11=495$ in effetti lo troveremo a $5*11=55$

l'$11$ ricordate sono i possibili valori di $n$



Qual'è la complessità computazionale di questo algoritmo?


-----------------------------------------------------------------------------------------------------------------------------------
EDIT
Per questo numero

$140089267639071478002348819284711337427$

si avrà questa soluzione

$(3*X+646278519063201834)*59910732360928521997651180715288662573-(2*X-1)*100000000000000000000000000000000000000=30000000000000000000000000000000000000$

in $30*3=90$ da osservare che $n=0$

dovrebbe essere al massimo

$59*3=177$

$3$ è il valore di n che può assumere valori $0$,$1$,$2$

[P_1_6]

andando a mettere in $C*3621539-K*4540513=4540513*n+(C*3621539)mod(4540513)$

$((C*3621539-(C*3621539)mod(4540513))/4540513=(K+n)$

i valori possibili di $C$ vediamo che $K+n$ si muove di $4$ in $4$ e che $(K+n)mod(4)=2$

quindi $K+n$ lo scriviamo come $4s-2$

analogamente andando a mettere in $4540513*n+(C*3621539)mod(4540513)=(Z)*4540513-C*10000000$

i valori possibili di $C$ vediamo che $Z$ si muove di $11$ in $11$ e che $(Z)mod(11)=2$

quindi $Z$ lo scriviamo come $11t+2$

questi due pezzi non sono esatti.
Esatto è questo
i valori possibili di $C=5t-1$ vediamo che $Z$ si muove di $11$ in $11$
quindi $Z$ lo scriviamo come $11t+(Z-11t)=11t+v$
$v$ purtroppo a un minimo e un massimo non è costante

[P_1_6]

Questa è una nuova idea per la fattorizzazione in $log$:
Allora l'idea è che un numero $n=p*q$ e $n$ ha $Cn$ cifre e $p$ $Cp$ cifre inserite nel algoritmo di Euclide per il calcolo del massimo comun divisore in questo modo
$Euclide[ p*(10^(Cn)) , n]$ ad un certo punto le $p$ cifre davanti scompaiono quindi scompariranno in $[log[ 2] ]$
Ora è $p*100000000-K(45459487)=$ ad un numero che è minore di di $99999999 $($9$ $Cn$ volte)
(per un certo $K$)
quindi le $Cp$ cifre iniziali saranno uguali a zero quindi sarà p-p=0 il secondo p è in chiaro

Ma come lo troviamo $K$ giusto

Esempio

$45459487$

$X*100000000 - 10030*45459487=X*100000000-455958654610=(X-4560)*100000000+41345390$

$141345390-45459487=95885903$

$X*100000000 - 10031*45459487=X*100000000-456004114097=(X-4561)*100000000+95885903$

$95885903-45459487=50426416$

$X*100000000 - 10032*45459487=X*100000000-456049573584=(X-4561)*100000000+50426416$

$50426416-45459487=04966929$

$X*100000000 - 10033*45459487=X*100000000-456095033971=(X-4561)*100000000+04966929$

$104966929-45459487=59507442 [DIVERSO1]$

$X*100000000 - 10034*45459487=X*100000000 -456140492558=(X-4562)*100000000+8675052 [DIVERSO1]$

$108675052-14047955=94627097 [DIVERSO2]$

$X*100000000 - 10035*45459487=X*100000000 -456185952045=(X-4562)*100000000+14047955 [DIVERSO2]$

Si può ben notare il logaritmo in base 2

Qualcuno gentilmente mi risponde?
-------------------------------------------------------------------------------------------------------------
EDIT:

8675052 [DIVERSO1]

Putroppo li c'è un errore di calcolo