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
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
1457
(543*2)mod(1000)=86
(int)1000/86=11
11*86-543=403
2867
(133*8)mod(1000)=64
64+8*133=1128
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
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
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--$
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--$
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$
$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$
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
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
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
$(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
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$
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$
"P_1_6":
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
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
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
Ho pensato a questa soluzione però non so risolvere questo sistema
$X*10000000-Z*45459487=3*4540513+500000$
${(INTERO)[100000000/(Z*10+3)]} *X=45459487$
per $(INTERO)$ intendo parte intera
qualcuno potrebbe darmi una mano
EDIT
l'ho risolta ma non porta a niente
$4836929/(10*Z+3)$
ma ho un'altra idea di trovare il fattore una cifra alla volta
ora non ho tempo ma riflettete su questo
$X*10000000−Z*45459487=3*4540513+500000$
$(X*10000000−Z*45459487)/100=X*(100000-(1000000/(Z*10+3))*Z+1)$
ho fatto tutti questi calcoli per portare un numero all'ultimo 1 che è un approssimazione
l'idea sembra buona
$X*10000000-Z*45459487=3*4540513+500000$
${(INTERO)[100000000/(Z*10+3)]} *X=45459487$
per $(INTERO)$ intendo parte intera
qualcuno potrebbe darmi una mano
EDIT
l'ho risolta ma non porta a niente
$4836929/(10*Z+3)$
ma ho un'altra idea di trovare il fattore una cifra alla volta
ora non ho tempo ma riflettete su questo
$X*10000000−Z*45459487=3*4540513+500000$
$(X*10000000−Z*45459487)/100=X*(100000-(1000000/(Z*10+3))*Z+1)$
ho fatto tutti questi calcoli per portare un numero all'ultimo 1 che è un approssimazione
l'idea sembra buona
Per chi ha seguito il post e non
siamo giunti quà
$p*10^7-Z*45459487=$
ora conoscendo il numero delle cifre di $p$
e conoscendo che $p>4545$
possiamo dedurre
$p*10^7 - 45459487*(10^3)=$un numero qualsiasii
$(+-p+-H)+$il restante ricordate
$H$ e $p$ sono uguali
FINE
EDIT:
Ovviamente non è la fine la fine è questa
$p*10^7 - 45459487*(10^3)=$un numero qualsiasii
dobbiamo conoscre di quante cifre è la differenza
e agire una o più cifre alla volta
EDIT
per fattorizzare un numero n impiego al massimo
[2^al numero delle cifre di sqrt(n)]
è un buon risultato ?
siamo giunti quà
$p*10^7-Z*45459487=$
ora conoscendo il numero delle cifre di $p$
e conoscendo che $p>4545$
possiamo dedurre
$p*10^7 - 45459487*(10^3)=$un numero qualsiasii
$(+-p+-H)+$il restante ricordate
$H$ e $p$ sono uguali
FINE
EDIT:
Ovviamente non è la fine la fine è questa
$p*10^7 - 45459487*(10^3)=$un numero qualsiasii
dobbiamo conoscre di quante cifre è la differenza
$H$ e $p$ sono uguali
e agire una o più cifre alla volta
EDIT
per fattorizzare un numero n impiego al massimo
[2^al numero delle cifre di sqrt(n)]
è un buon risultato ?
Test di primalità e fattorizzazione di Lepore
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-Cp)) , n] ad un certo punto le Cp cifre davanti scompaiono quindi scompariranno.
Quindi avremo un albero binario che avrà come radice p*(10^(Cn-Cp))-n=A
non sapendo se n>A
al primo livello lato destro avremo
da un lato p*(10^(Cn-Cp))-2n=B
e al primo livello lato sinistro
n-A=C
al secondo livello partendo da destra avremo
p*(10^(Cn-Cp))-3n=D
n-B
n-2A
A-C
e così via
Dal fatto che ogni risultato del algoritmo di Euclide è maggiore di 0 possiamo stabilire valori massimi e valori minimi per p e scegliere la strada giusta,
in più per scegliere la quantità di strada giusta si usa la tecnica della ricerca binaria
In questo esempio non percorrerò tutte le strade perchè faccio tutto a mano
ma è per spiegare il metodo
ESEMPIO
20737
massimo per p =sqrt(20737)=144,.....
minimo=1
Livello 0
p*10^3-20737=(p-21)*10^3+263 si testa 20737 modulo 21 == 0
siccome p-21>0 avremo
massimo = 144,...
minimo =21
Livello 1 lato sinisro
20737-[(p-21)*10^3+263]=(-p+41)*10^3+474 si testa 20737 modulo 41 == 0
siccome -p+41>0
massimo=41
minimo =21
Livello 2 lato sinistro figlio del 1 livello lato sinistro
[(p-21)*10^3+263]-(-p+41)*10^3+474=(2p-63)*10^3+789 63/2 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]
Livello 2 lato destro figlio del 1 livello lato sinistro
20737-2*[(p-21)*10^3+263]=(-2p+62)*10^3+211 si testa 20737 modulo (62/2) == 0
massimo =31
minimo = 21
Livello 3 lato sinistro figlio del 2 livello lato destro figlio del 1 livello lato sinistro
[(p-21)*10^3+263]-[(-2p+62)*10^3+211]=(3p-93)*10^3+52
massimo 31
minimo 31
[STRADA CHIUSA]
Livello 3 lato destro figlio del 2 livello lato destro figlio del 1 livello lato sinistro
20737-3*[(p-21)*10^3+263]=(-3p+82)*10+948 82/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]
[qui vi farò vedere la ricerca binaria che non vi ho fatto vedere fino ad adesso per non confondervi]
[vi farò vedere che al 5 livello non è buona la strada mentre fino al 4 si]
Livello 4 lato destro figlio di tutti destri
p*10^3-4*20737=(p-83)*10^3+052 si testa 20737 modulo 83 == 0
massimo 144
minimo 83
Livello 5 lato destro figlio di tutti destri
p*10^3-5*20737=(p-104)+315 si testa 20737 modulo 104 == 0
massimo 144
minimo 104
Livello 6 lato sinistro figlio di tutti destri
20737-[(p-104)*10^3+315]=(-p+124)*10^3+422 si testa 20737 modulo 124 == 0
massimo =124
minimo =104
Livello 7 lato sinistro figlio del livello 6 lato sinistro figlio di tutti destri
(p-104)*10^3+315-[(-p+124)*10^3+422]=(2p-229)*10^3+893 229/2 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]
Livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
20737-2*[(p-104)*10^3+315]=(-2p+228)*10^3+107 si testa 20737 modulo 114 == 0
massimo =114
minimo =104
Livello 8 lato sinistro figlio del livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
[(p-104)*10^3+315]-[(-2p+228)*10^3+107]=(3p-332)*10^3+208 332/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]
Livello 8 lato destro figlio del livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
20737-3*[(p-104)*10^3+315]=(-3p+331)*10^3+792 331/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]
Livello 5 lato sinistro
ecc.ecc
La strada giusta che troveremo è quetsa
20737-3*[(p-83)*10^3+052]=(-3p+269)*1000+581
(p-83)*10^3+052-2*[(-3p+269)*10^10^3+581]=(7p-623)+890 si testa 20737 modulo 623/7=89 ==0 e va bene
Perchè usare la ricerca binaria?
Perchè si potrebbe verificare questo
Esempio
45459487
45610000-45459487=150513
45459487/150513=302
Con i numeri piccoli non si vede la velocità del algoritmo
Che complessità ha questo algoritmo?
Ovviamente c'è da moltiplicare la complessità che mi direte per il numero di cifre di sqrt(n) in quanto non sappiamo il fattore di quante cifre è
P.s. Spero di non aver commesso errori
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-Cp)) , n] ad un certo punto le Cp cifre davanti scompaiono quindi scompariranno.
Quindi avremo un albero binario che avrà come radice p*(10^(Cn-Cp))-n=A
non sapendo se n>A
al primo livello lato destro avremo
da un lato p*(10^(Cn-Cp))-2n=B
e al primo livello lato sinistro
n-A=C
al secondo livello partendo da destra avremo
p*(10^(Cn-Cp))-3n=D
n-B
n-2A
A-C
e così via
Dal fatto che ogni risultato del algoritmo di Euclide è maggiore di 0 possiamo stabilire valori massimi e valori minimi per p e scegliere la strada giusta,
in più per scegliere la quantità di strada giusta si usa la tecnica della ricerca binaria
In questo esempio non percorrerò tutte le strade perchè faccio tutto a mano
ma è per spiegare il metodo
ESEMPIO
20737
massimo per p =sqrt(20737)=144,.....
minimo=1
Livello 0
p*10^3-20737=(p-21)*10^3+263 si testa 20737 modulo 21 == 0
siccome p-21>0 avremo
massimo = 144,...
minimo =21
Livello 1 lato sinisro
20737-[(p-21)*10^3+263]=(-p+41)*10^3+474 si testa 20737 modulo 41 == 0
siccome -p+41>0
massimo=41
minimo =21
Livello 2 lato sinistro figlio del 1 livello lato sinistro
[(p-21)*10^3+263]-(-p+41)*10^3+474=(2p-63)*10^3+789 63/2 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]
Livello 2 lato destro figlio del 1 livello lato sinistro
20737-2*[(p-21)*10^3+263]=(-2p+62)*10^3+211 si testa 20737 modulo (62/2) == 0
massimo =31
minimo = 21
Livello 3 lato sinistro figlio del 2 livello lato destro figlio del 1 livello lato sinistro
[(p-21)*10^3+263]-[(-2p+62)*10^3+211]=(3p-93)*10^3+52
massimo 31
minimo 31
[STRADA CHIUSA]
Livello 3 lato destro figlio del 2 livello lato destro figlio del 1 livello lato sinistro
20737-3*[(p-21)*10^3+263]=(-3p+82)*10+948 82/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]
[qui vi farò vedere la ricerca binaria che non vi ho fatto vedere fino ad adesso per non confondervi]
[vi farò vedere che al 5 livello non è buona la strada mentre fino al 4 si]
Livello 4 lato destro figlio di tutti destri
p*10^3-4*20737=(p-83)*10^3+052 si testa 20737 modulo 83 == 0
massimo 144
minimo 83
Livello 5 lato destro figlio di tutti destri
p*10^3-5*20737=(p-104)+315 si testa 20737 modulo 104 == 0
massimo 144
minimo 104
Livello 6 lato sinistro figlio di tutti destri
20737-[(p-104)*10^3+315]=(-p+124)*10^3+422 si testa 20737 modulo 124 == 0
massimo =124
minimo =104
Livello 7 lato sinistro figlio del livello 6 lato sinistro figlio di tutti destri
(p-104)*10^3+315-[(-p+124)*10^3+422]=(2p-229)*10^3+893 229/2 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]
Livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
20737-2*[(p-104)*10^3+315]=(-2p+228)*10^3+107 si testa 20737 modulo 114 == 0
massimo =114
minimo =104
Livello 8 lato sinistro figlio del livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
[(p-104)*10^3+315]-[(-2p+228)*10^3+107]=(3p-332)*10^3+208 332/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]
Livello 8 lato destro figlio del livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
20737-3*[(p-104)*10^3+315]=(-3p+331)*10^3+792 331/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]
Livello 5 lato sinistro
ecc.ecc
La strada giusta che troveremo è quetsa
20737-3*[(p-83)*10^3+052]=(-3p+269)*1000+581
(p-83)*10^3+052-2*[(-3p+269)*10^10^3+581]=(7p-623)+890 si testa 20737 modulo 623/7=89 ==0 e va bene
Perchè usare la ricerca binaria?
Perchè si potrebbe verificare questo
Esempio
45459487
45610000-45459487=150513
45459487/150513=302
Con i numeri piccoli non si vede la velocità del algoritmo
Che complessità ha questo algoritmo?
Ovviamente c'è da moltiplicare la complessità che mi direte per il numero di cifre di sqrt(n) in quanto non sappiamo il fattore di quante cifre è
P.s. Spero di non aver commesso errori
"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 +500000 $
$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$
guardare
$(11*s+2)*4540513-(5*s-1)*10000000=3*4540513+500000$
vi ricordate che il problema era individurae il $2$
bene se la dentro superiamo il $2$ si avrà che p supera la radice quadrata
infatti
$(11*s+3)*4540513-(5*s-1)*10000000=3*4540513+500000$
$s=174,77$
$p=5Z-C=55s+15-5s+1=50s+16=8754,.....$
quindi avremo il nostro bel logaritmo
Vi prego datemi conferma.
"P_1_6":
-----------------------------------------------------------------------------------------------------------------------------------
EDIT
Per questo numero
$140089267639071478002348819284711337427$
si avrà questa soluzione
$(3*X+646278519063201834)*59910732360928521997651180715288662573-(2*X-1)*100000000000000000000000000000000000000=30000000000000000000000000000000000000$
Ho notato che questo valore $646278519063201834$ cresce costantemente quindi sostituendo in $C=(2*X-1)$ ad esempio il
valore $10^19$ si avrà $169150018022750097$ quindi avremo
$(3*X+|169150018022750097*(2*X-1)/(10^18)|+2)*59910732360928521997651180715288662573−(2*X−1)⋅10^38=((2*X-1)*19821464721857043995302361430577325146)mod (59910732360928521997651180715288662573)$
Per $|169150018022750097*(2*X-1)/(10^18)|$ intendo la parte intera
che non so risolvere
quindi se sapete risolvere questa equazione avrete la fattorizzazzione in un tempo costante $O(K)$
EDIT:
ho modificato
EDIT 2:
si potrebbe anche approssimare facendo crescere il 10^19 e il 10^18 ad esempio portandoli a 10^100 e 10^99
ma purtroppo non riesco a fare questi calcoli con gli strumenti che ho
Edit 3:
Dopo l'aiuto di http://math.stackexchange.com/users/1827/ross-millikan che mi ha detto che quella non si poteva risolvere sono giunto qui
$(3*X+\lfloor 169150018022750097*(2*X−1)/10^18 \rfloor+2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
EDIT4
Per la soluzione guardare
viewtopic.php?f=26&t=164206
EDIT5:
non guardare EDIT3 e per il numero $45459487$ grazie al aiuto EDIT4
ho scoperto una nuova cosa
$(11*x+(x-8)/83+1)$ qua dentro il $+1$ varia di poco in generale
quindi risolvendo questa
$(11*x+(x-8)/83+1)*4540513-(5*x-1)*10^7=3*4540513+((5*x-1)*3621539)-((\lfloor((5*x-1)*3621539)/(4540513)\rfloor)*4540513)$
si ha la soluzione
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 $5s-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=n*4540513+(C*3621539)mod(4540513)$
la $n$ può assumere in questo caso valori da $0$ a $10$ poichè
$p*10000000-(Z*45459487)=4540513*n+(C*3621539)mod(4540513)$
infatti $45459487/4540513=10,....$
quindi andremo a provare tutti i valori di $n$ possibili
nel nostro caso $n=3$ (ma non lo sappiamo)
in più si puo notare che $(C*3621539)mod(4540513) < 4540513$
quindi prendendo le prime $2$ cifre andremo da $0$ a $45$
quindi $46$
ma non spaventatevi da $11*46$ in quanto è costante di ordine per ogni numero
infatti se $11$ diventa $12$ diminuisce di una cifra l altro
andando a mettere in $(Z)*4540513-C*10000000=4540513*n+(C*3621539)mod(4540513)$
i valori possibili di $C$ vediamo che $Z$ si muove di $11$ in $11$
quindi $Z$ lo scriviamo come $11s+Y$ e $C=5s-1$
Quindi quando siamo nel nostro caso cioè
$(11*s+Y)*4540513-(5*s-1)*10000000=3*4540513+500000$
avremo
$(11*s+Y)*4540513-(5*s-1)*10000000=3*4540513+((5s-1)*3621539)mod(4540513)$
andando a sostituire un numero al posto di $5s-1$ ad esempio $10^20$
quindi si avrà $Y=239431095120749572$
quindi si avrà
$(11*x+\lfloor239431095120749572*(5*x-1)/10^20\rfloor+1)*4540513-(5*x-1)*10^7=3*4540513+500000$
Con la spiegazione di piercammello che riporto integralmente
*******************************************************************************************
ok allora vediamo insieme come risolverla, ma solo per darti spunti in merito alla parte intera.
Vediamo di calcolare prima la quantità entro l'operatore "parte intera" e cioè:
$239431095120749572*(5*x-1)/(10^{20})$
la divisione tra $239431095120749572$ e $(10^{20})$
da come risultato il decimale:
$0.00239431095120749$
quindi l'espressione diventa:
$239431095120749572*(5*x-1)/(10^{20})= 0.00239431095120749*(5*x-1)$
con altro passaggio abbiamo:
$0.0119715547560375*x - 0.00239431095120749$
vogliamo per adesso tenerci solo tre cifre significative per evitare di rendere illeggibile il topic?
Ed allora scriviamo
$0.0120 *x - 0.00239$
che in notazione esponenziale diventa:
$1.2e-3*x-2.39e-4$
Il secondo numero noterai che è di un ordine di grandezza inferiore rispetto al coefficiente della $x$
Cerchiamo adesso di capire la parte intera che sarà per forza di cosa un numero naturale.
Finchè il risultato di questa espressione di mantiene inferiore ad 1 (ma comunque maggiore di zero) allora la sua parte intera sarà banalmente 0 (sempre se non assume valore negativo. Ricorda che la parte intera di $-1.25$ non è $-1$ bensi $-2$)
Lasciamo perdere per adesso la questione dei valori negativi ed occupiamoci dei positivi.
Per poter portare quel $0.0120$ ad un numero maggiore di 1 occorre che $x$ sia del'ordine del $10^2$ cioe un centinaio o giù di li.
Ma noi non possiamo andarci per tentativi e quindi forse ci conviene impostare una uguaglianza per capire per quale valore di $x$ scatta altro intero
$0.0120 *x - 0.00239=1$
che risolta ci da:
$x=(1+ 0.00239)/0.0120 =83.73$
Ma ci serve anche capire quando vale $x$ per cui si va nei negativi. Quindi
$0.0120 *x - 0.00239=0$
da cui:
$x= 0.00239/0.0120 =0.2$
Questo significa che per $0.2<=x<83.73$
l'espressione $0.0119715547560375*x - 0.00239431095120749$, da come risultato zero.
*********************************************************************************************
Siccome $sqrt(45459487)$ è il massimo valore per $p$ e $p$ e nella forma $5*Z-C$ dobbiamo dividere per $5$
e siccome $c=5*s-1$ dobbiamo sottrarre $1$ e dividere per $5$ il tutto per avere il massimo valore per $s$
$((sqrt(45459487)/5)-1)/5=269$
quindi l'intervallo per $s$ è $[0,269]$
$269/83,...=3$
quindi avremo quattro possibili valori per $Y$ e cioè $0,1,2,3$
che sono troppi
quindi sostituiamo $x=10^18$ in
$(11*x+Y)*4540513-(5*x-1)*10^7-3*4540513=((5*x-1)*3621539)mod(4540513)$
e avremo $Y=11971554756037480$
$(11*x+\lfloor11971554756037480*(5*x-1)/10^18\rfloor-3)*4540513-(5*x-1)*10^7=3*4540513+500000$
si avrà la soluzione $91.2392$
ci rimane da capire quel $-3$
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 $5s-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=n*4540513+(C*3621539)mod(4540513)$
la $n$ può assumere in questo caso valori da $0$ a $10$ poichè
$p*10000000-(Z*45459487)=4540513*n+(C*3621539)mod(4540513)$
infatti $45459487/4540513=10,....$
quindi andremo a provare tutti i valori di $n$ possibili
nel nostro caso $n=3$ (ma non lo sappiamo)
in più si puo notare che $(C*3621539)mod(4540513) < 4540513$
quindi prendendo le prime $2$ cifre andremo da $0$ a $45$
quindi $46$
ma non spaventatevi da $11*46$ in quanto è costante di ordine per ogni numero
infatti se $11$ diventa $12$ diminuisce di una cifra l altro
andando a mettere in $(Z)*4540513-C*10000000=4540513*n+(C*3621539)mod(4540513)$
i valori possibili di $C$ vediamo che $Z$ si muove di $11$ in $11$
quindi $Z$ lo scriviamo come $11s+Y$ e $C=5s-1$
Quindi quando siamo nel nostro caso cioè
$(11*s+Y)*4540513-(5*s-1)*10000000=3*4540513+500000$
avremo
$(11*s+Y)*4540513-(5*s-1)*10000000=3*4540513+((5s-1)*3621539)mod(4540513)$
andando a sostituire un numero al posto di $5s-1$ ad esempio $10^20$
quindi si avrà $Y=239431095120749572$
quindi si avrà
$(11*x+\lfloor239431095120749572*(5*x-1)/10^20\rfloor+1)*4540513-(5*x-1)*10^7=3*4540513+500000$
Con la spiegazione di piercammello che riporto integralmente
*******************************************************************************************
ok allora vediamo insieme come risolverla, ma solo per darti spunti in merito alla parte intera.
Vediamo di calcolare prima la quantità entro l'operatore "parte intera" e cioè:
$239431095120749572*(5*x-1)/(10^{20})$
la divisione tra $239431095120749572$ e $(10^{20})$
da come risultato il decimale:
$0.00239431095120749$
quindi l'espressione diventa:
$239431095120749572*(5*x-1)/(10^{20})= 0.00239431095120749*(5*x-1)$
con altro passaggio abbiamo:
$0.0119715547560375*x - 0.00239431095120749$
vogliamo per adesso tenerci solo tre cifre significative per evitare di rendere illeggibile il topic?
Ed allora scriviamo
$0.0120 *x - 0.00239$
che in notazione esponenziale diventa:
$1.2e-3*x-2.39e-4$
Il secondo numero noterai che è di un ordine di grandezza inferiore rispetto al coefficiente della $x$
Cerchiamo adesso di capire la parte intera che sarà per forza di cosa un numero naturale.
Finchè il risultato di questa espressione di mantiene inferiore ad 1 (ma comunque maggiore di zero) allora la sua parte intera sarà banalmente 0 (sempre se non assume valore negativo. Ricorda che la parte intera di $-1.25$ non è $-1$ bensi $-2$)
Lasciamo perdere per adesso la questione dei valori negativi ed occupiamoci dei positivi.
Per poter portare quel $0.0120$ ad un numero maggiore di 1 occorre che $x$ sia del'ordine del $10^2$ cioe un centinaio o giù di li.
Ma noi non possiamo andarci per tentativi e quindi forse ci conviene impostare una uguaglianza per capire per quale valore di $x$ scatta altro intero
$0.0120 *x - 0.00239=1$
che risolta ci da:
$x=(1+ 0.00239)/0.0120 =83.73$
Ma ci serve anche capire quando vale $x$ per cui si va nei negativi. Quindi
$0.0120 *x - 0.00239=0$
da cui:
$x= 0.00239/0.0120 =0.2$
Questo significa che per $0.2<=x<83.73$
l'espressione $0.0119715547560375*x - 0.00239431095120749$, da come risultato zero.
*********************************************************************************************
Siccome $sqrt(45459487)$ è il massimo valore per $p$ e $p$ e nella forma $5*Z-C$ dobbiamo dividere per $5$
e siccome $c=5*s-1$ dobbiamo sottrarre $1$ e dividere per $5$ il tutto per avere il massimo valore per $s$
$((sqrt(45459487)/5)-1)/5=269$
quindi l'intervallo per $s$ è $[0,269]$
$269/83,...=3$
quindi avremo quattro possibili valori per $Y$ e cioè $0,1,2,3$
che sono troppi
quindi sostituiamo $x=10^18$ in
$(11*x+Y)*4540513-(5*x-1)*10^7-3*4540513=((5*x-1)*3621539)mod(4540513)$
e avremo $Y=11971554756037480$
$(11*x+\lfloor11971554756037480*(5*x-1)/10^18\rfloor-3)*4540513-(5*x-1)*10^7=3*4540513+500000$
si avrà la soluzione $91.2392$
ci rimane da capire quel $-3$
"P_1_6":
-----------------------------------------------------------------------------------------------------------------------------------
EDIT
Per questo numero
$140089267639071478002348819284711337427$
si avrà questa soluzione
$(3*X+646278519063201834)*59910732360928521997651180715288662573-(2*X-1)*100000000000000000000000000000000000000=30000000000000000000000000000000000000$
ho notato grazie a piercammello che guardando le variazioni di valore di $X$ si può arrivare alla soluzione di questo numero
in $1665$ step per una costante
io ho approssimato perchè non so calcolare la variabile nel modulo
dovremmo vedere le soluzioni di questa
$(3*X+1)*59910732360928521997651180715288662573−(2*X−1)*10^38=((2*X-1)*19821464721857043995302361430577325146)mod (59910732360928521997651180715288662573)$
e confrontarla con la soluzione di questa
$(3*X+1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
e scegliere quella del modulo
comunque vi faccio vedere con le approssimazioni
$(3*X+1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=6.4097096706$
$(3*X+2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=9.3656656075$
$9.3656656075 - 6.4097096706 =2.9559559369$
$(3*X+2.9559559369*1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=12.191429235$
$(3*X+2.9559559369*2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=20.92910735$
$20.92910735 - 12.191429235 =8.737678115$
$(3*X+2.9559559369*8.737678115*1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=79.8007$
$(3*X+2.9559559369*8.737678115*2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=156.148$
$156.148 - 79.8007 = 76.3473$
$(3*X+2.9559559369*8.737678115*76.3473*1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=5832.34$
$(3*X+2.9559559369*8.737678115*76.3473*2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=11661.2$
$11661.2 - 5832.34 =5828.68$
$(3*X+2.9559559369*8.737678115*76.3473*5828.68*1)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=33974720.577844091$
$(3*X+2.9559559369*8.737678115*76.3473*5828.68*2)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=67949437.701934449$
$67949437.701934449 - 33974720.577844091 =33974717.124090358$
$(3*X+2.9559559369*8.737678115*76.3473*5828.68*33974717.124090358*1655)*59910732360928521997651180715288662573−(2*X−1)*10^38=3*10^37$
$X=1910335723060541440$
Quello che cercavamo è $1910370825311646108$
Se avessimo usato il modulo le due combacerebbero
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$
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=n*4540513+(C*3621539)mod(4540513)$
la $n$ può assumere in questo caso valori da $0$ a $10$ poichè
$p*10000000-(Z*45459487)=4540513*n+(C*3621539)mod(4540513)$
infatti $45459487/4540513=10,....$
quindi andremo a provare tutti i valori di $n$ possibili
nel nostro caso $n=3$ (ma non lo sappiamo)
in più si puo notare che $(C*3621539)mod(4540513) < 4540513$
quindi prendendo le prime $2$ cifre andremo da $0$ a $45$
quindi $46$
ma non spaventatevi da $11*46$ in quanto è costante di ordine per ogni numero
infatti se $11$ diventa $12$ diminuisce di una cifra l altro
quindi $(Z)*4540513-C*10000000=4540513*n+(C*3621539)mod(4540513)$
quindi quando ci troviamo nel caso $n =3$ e le prime due cifre di cui vi parlavo sono 05
ci troveremo la sequenza che si ripete , i salti e proveremo per tutti i salti
viewtopic.php?f=26&t=164364
in questo caso c'è un salto nell'intervallo $[0,1348]$ ma noi troveremo i nostri valori prima del primo e unico salto
abbiamo quasi finito ci manca un'ultima cosa
\begin{equation}
\begin{cases}
Z*4540513-(D*84+5+29)*10^7-3*4540513=((D*84+5+29)*3621539)mod(4540513)
\\
[3*4540513+(((D*84+5+29)*3621539)mod(4540513) ) ]mod (5*Z-(D*84+5+29))=0
\end{cases}
\end{equation}
risolto questo si ha la fattorizzazione di 45459487
che è $(5*Z-(D*84+5+29))$
$Z=1003$
$D=5$
qualcuno gentilmente mi aiuta a risolverla
EDIT: ho modificato
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$
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=n*4540513+(C*3621539)mod(4540513)$
la $n$ può assumere in questo caso valori da $0$ a $10$ poichè
$p*10000000-(Z*45459487)=4540513*n+(C*3621539)mod(4540513)$
infatti $45459487/4540513=10,....$
quindi andremo a provare tutti i valori di $n$ possibili
nel nostro caso $n=3$ (ma non lo sappiamo)
in più si puo notare che $(C*3621539)mod(4540513) < 4540513$
quindi prendendo le prime $2$ cifre andremo da $0$ a $45$
quindi $46$
ma non spaventatevi da $11*46$ in quanto è costante di ordine per ogni numero
infatti se $11$ diventa $12$ diminuisce di una cifra l altro
quindi $(Z)*4540513-C*10000000=4540513*n+(C*3621539)mod(4540513)$
quindi quando ci troviamo nel caso $n =3$ e le prime due cifre di cui vi parlavo sono 05
ci troveremo la sequenza che si ripete , i salti e proveremo per tutti i salti
viewtopic.php?f=26&t=164364
in questo caso c'è un salto nell'intervallo $[0,1348]$ ma noi troveremo i nostri valori prima del primo e unico salto
abbiamo quasi finito ci manca un'ultima cosa
\begin{equation}
\begin{cases}
Z*4540513-(D*84+5+29)*10^7-3*4540513=((D*84+5+29)*3621539)mod(4540513)
\\
[3*4540513+(((D*84+5+29)*3621539)mod(4540513) ) ]mod (5*Z-(D*84+5+29))=0
\end{cases}
\end{equation}
risolto questo si ha la fattorizzazione di 45459487
che è $(5*Z-(D*84+5+29))$
$Z=1003$
$D=5$
qualcuno gentilmente mi aiuta a risolverla
EDIT: ho modificato
Ulteriori passi in avanti
Abbiamo visto il caso $(6a+1)*(6b+1)=6*G+1$
Ora vedremo $(6a+5)*(6b+1)=6*G+5$
dove andremoa trovarci $q$ anzichè $p$
$1489999*890003=1326103579997$
$q=2Z-C$
$A= 673896420003 $
$B= 347792840006 $
$n =1$
$m 67$
quando ci troviamo nel caso
$n=1$
e le prime due cifre sono $27$ quindi l'intervallo è
$[270000000000 , 280000000000]$
quindi dobbiamo vedere
\begin{equation}
\begin{cases}
(347792840006*X) mod (673896420003)>270000000000
\\
(347792840006*X) mod (673896420003)<280000000000
\end{cases}
\end{equation}
Ho notato che si ripete sempre la stessa sequenza anche del salto
la sequenza è $31;31;31;31;31;31;31;31;31;31;31;31;498$
però ovviamente la prima volta ha un $31$ in meno (il primo) sostituito da $119$
come si può osservare
vediamo la sequenza completa
inizialmente è $4;2;2$
ora vi mostro
$4$
successivamente $2$
successivamente $2$
poi si ripete sempre $4;2;2$; fino a $694607$
dove inizierà a ripetersi $1;2;2;2$
$1$
$2$
$2$
$2$
e quindi si ripeterà $1;2;2;2$; fino al prossimo salto dei salti
quindi il nostro valore sarà $11*12*31+7*498+4*529=9694$
ora bisognerebbe sapere la posizione del nostro $C$ nella sequenza ma siccome non la conosciamo dovremo provare per tutti i posti della sequenza
fino ad arrivare alla posizione giusta che ho segnato con gli asterischi
quindi il nostro valore sarà
$5*12*31+3*498+2*529=4412$
quindi avremo $(X-4412-694607)/9694=D$
nel nostro caso $D=6$
si ricostruisce il solito sistema che ancora non so risolvere
e si trovano le soluzioni
$C=757183$
$Z=1123591$
P.s. le sequenze si possono trovare in tempi logaritmici
P.s.2.se c'è un metodo matematico per trovare quelle sequenze gentilmente qualcuno me lo indichi
Abbiamo visto il caso $(6a+1)*(6b+1)=6*G+1$
Ora vedremo $(6a+5)*(6b+1)=6*G+5$
dove andremoa trovarci $q$ anzichè $p$
$1489999*890003=1326103579997$
$q=2Z-C$
$A= 673896420003 $
$B= 347792840006 $
$n =1$
$m 67$
quando ci troviamo nel caso
$n=1$
e le prime due cifre sono $27$ quindi l'intervallo è
$[270000000000 , 280000000000]$
quindi dobbiamo vedere
\begin{equation}
\begin{cases}
(347792840006*X) mod (673896420003)>270000000000
\\
(347792840006*X) mod (673896420003)<280000000000
\end{cases}
\end{equation}
Ho notato che si ripete sempre la stessa sequenza anche del salto
la sequenza è $31;31;31;31;31;31;31;31;31;31;31;31;498$
però ovviamente la prima volta ha un $31$ in meno (il primo) sostituito da $119$
come si può osservare
vediamo la sequenza completa
inizialmente è $4;2;2$
ora vi mostro
$4$
valore=279666340531 i=119 salto=119 valore=278901660669 i=150 salto=31 valore=278136980807 i=181 salto=31 valore=277372300945 i=212 salto=31 valore=276607621083 i=243 salto=31 valore=275842941221 i=274 salto=31 valore=275078261359 i=305 salto=31 valore=274313581497 i=336 salto=31 valore=273548901635 i=367 salto=31 valore=272784221773 i=398 salto=31 valore=272019541911 i=429 salto=31 valore=271254862049 i=460 salto=31 valore=270490182187 i=491 salto=31 valore=279944564404 i=989 salto=498 valore=279179884542 i=1020 salto=31 valore=278415204680 i=1051 salto=31 valore=277650524818 i=1082 salto=31 valore=276885844956 i=1113 salto=31 valore=276121165094 i=1144 salto=31 valore=275356485232 i=1175 salto=31 valore=274591805370 i=1206 salto=31 valore=273827125508 i=1237 salto=31 valore=273062445646 i=1268 salto=31 valore=272297765784 i=1299 salto=31 valore=271533085922 i=1330 salto=31 valore=270768406060 i=1361 salto=31 valore=270003726198 i=1392 salto=31 valore=279458108415 i=1890 salto=498 valore=278693428553 i=1921 salto=31 valore=277928748691 i=1952 salto=31 valore=277164068829 i=1983 salto=31 valore=276399388967 i=2014 salto=31 valore=275634709105 i=2045 salto=31 valore=274870029243 i=2076 salto=31 valore=274105349381 i=2107 salto=31 valore=273340669519 i=2138 salto=31 valore=272575989657 i=2169 salto=31 valore=271811309795 i=2200 salto=31 valore=271046629933 i=2231 salto=31 valore=270281950071 i=2262 salto=31 valore=279736332288 i=2760 salto=498 valore=278971652426 i=2791 salto=31 valore=278206972564 i=2822 salto=31 valore=277442292702 i=2853 salto=31 valore=276677612840 i=2884 salto=31 valore=275912932978 i=2915 salto=31 valore=275148253116 i=2946 salto=31 valore=274383573254 i=2977 salto=31 valore=273618893392 i=3008 salto=31 valore=272854213530 i=3039 salto=31 valore=272089533668 i=3070 salto=31 valore=271324853806 i=3101 salto=31 valore=270560173944 i=3132 salto=31 valore=279249876299 i=3661 salto=529
successivamente $2$
valore=278485196437 i=3692 salto=31 valore=277720516575 i=3723 salto=31 valore=276955836713 i=3754 salto=31 valore=276191156851 i=3785 salto=31 valore=275426476989 i=3816 salto=31 valore=274661797127 i=3847 salto=31 valore=273897117265 i=3878 salto=31 valore=273132437403 i=3909 salto=31 valore=272367757541 i=3940 salto=31 valore=271603077679 i=3971 salto=31 valore=270838397817 i=4002 salto=31 valore=270073717955 i=4033 salto=31 valore=279528100172 i=4531 salto=498 valore=278763420310 i=4562 salto=31 valore=277998740448 i=4593 salto=31 valore=277234060586 i=4624 salto=31 valore=276469380724 i=4655 salto=31 valore=275704700862 i=4686 salto=31 valore=274940021000 i=4717 salto=31 valore=274175341138 i=4748 salto=31 valore=273410661276 i=4779 salto=31 valore=272645981414 i=4810 salto=31 valore=271881301552 i=4841 salto=31 valore=271116621690 i=4872 salto=31 valore=270351941828 i=4903 salto=31 valore=279806324045 i=5401 salto=498 valore=279041644183 i=5432 salto=31 valore=278276964321 i=5463 salto=31 valore=277512284459 i=5494 salto=31 valore=276747604597 i=5525 salto=31 valore=275982924735 i=5556 salto=31 valore=275218244873 i=5587 salto=31 valore=274453565011 i=5618 salto=31 valore=273688885149 i=5649 salto=31 valore=272924205287 i=5680 salto=31 valore=272159525425 i=5711 salto=31 valore=271394845563 i=5742 salto=31 valore=270630165701 i=5773 salto=31 valore=279319868056 i=6302 salto=529
successivamente $2$
valore=278555188194 i=6333 salto=31 valore=277790508332 i=6364 salto=31 valore=277025828470 i=6395 salto=31 valore=276261148608 i=6426 salto=31 valore=275496468746 i=6457 salto=31 valore=274731788884 i=6488 salto=31 valore=273967109022 i=6519 salto=31 valore=273202429160 i=6550 salto=31 valore=272437749298 i=6581 salto=31 valore=271673069436 i=6612 salto=31 valore=270908389574 i=6643 salto=31 valore=270143709712 i=6674 salto=31 valore=279598091929 i=7172 salto=498 valore=278833412067 i=7203 salto=31 valore=278068732205 i=7234 salto=31 valore=277304052343 i=7265 salto=31 valore=276539372481 i=7296 salto=31 valore=275774692619 i=7327 salto=31 valore=275010012757 i=7358 salto=31 valore=274245332895 i=7389 salto=31 valore=273480653033 i=7420 salto=31 valore=272715973171 i=7451 salto=31 valore=271951293309 i=7482 salto=31 valore=271186613447 i=7513 salto=31 valore=270421933585 i=7544 salto=31 valore=279876315802 i=8042 salto=498 valore=279111635940 i=8073 salto=31 valore=278346956078 i=8104 salto=31 valore=277582276216 i=8135 salto=31 valore=276817596354 i=8166 salto=31 valore=276052916492 i=8197 salto=31 valore=275288236630 i=8228 salto=31 valore=274523556768 i=8259 salto=31 valore=273758876906 i=8290 salto=31 valore=272994197044 i=8321 salto=31 valore=272229517182 i=8352 salto=31 valore=271464837320 i=8383 salto=31 valore=270700157458 i=8414 salto=31 valore=279389859813 i=8943 salto=529
poi si ripete sempre $4;2;2$; fino a $694607$
dove inizierà a ripetersi $1;2;2;2$
$1$
valore=278678952199 i=694607 salto=31 valore=277914272337 i=694638 salto=31 valore=277149592475 i=694669 salto=31 valore=276384912613 i=694700 salto=31 valore=275620232751 i=694731 salto=31 valore=274855552889 i=694762 salto=31 valore=274090873027 i=694793 salto=31 valore=273326193165 i=694824 salto=31 valore=272561513303 i=694855 salto=31 valore=271796833441 i=694886 salto=31 valore=271032153579 i=694917 salto=31 valore=270267473717 i=694948 salto=31 valore=279721855934 i=695446 salto=498 valore=278957176072 i=695477 salto=31 valore=278192496210 i=695508 salto=31 valore=277427816348 i=695539 salto=31 valore=276663136486 i=695570 salto=31 valore=275898456624 i=695601 salto=31 valore=275133776762 i=695632 salto=31 valore=274369096900 i=695663 salto=31 valore=273604417038 i=695694 salto=31 valore=272839737176 i=695725 salto=31 valore=272075057314 i=695756 salto=31 valore=271310377452 i=695787 salto=31 valore=270545697590 i=695818 salto=31 valore=279235399945 i=696347 salto=529
$2$
valore=278470720083 i=696378 salto=31 valore=277706040221 i=696409 salto=31 valore=276941360359 i=696440 salto=31 valore=276176680497 i=696471 salto=31 valore=275412000635 i=696502 salto=31 valore=274647320773 i=696533 salto=31 valore=273882640911 i=696564 salto=31 valore=273117961049 i=696595 salto=31 valore=272353281187 i=696626 salto=31 valore=271588601325 i=696657 salto=31 valore=270823921463 i=696688 salto=31 valore=270059241601 i=696719 salto=31 valore=279513623818 i=697217 salto=498 valore=278748943956 i=697248 salto=31 valore=277984264094 i=697279 salto=31 valore=277219584232 i=697310 salto=31 valore=276454904370 i=697341 salto=31 valore=275690224508 i=697372 salto=31 valore=274925544646 i=697403 salto=31 valore=274160864784 i=697434 salto=31 valore=273396184922 i=697465 salto=31 valore=272631505060 i=697496 salto=31 valore=271866825198 i=697527 salto=31 valore=271102145336 i=697558 salto=31 valore=270337465474 i=697589 salto=31 valore=279791847691 i=698087 salto=498 valore=279027167829 i=698118 salto=31 valore=278262487967 i=698149 salto=31 valore=277497808105 i=698180 salto=31 valore=276733128243 i=698211 salto=31 valore=275968448381 i=698242 salto=31 valore=275203768519 i=698273 salto=31 valore=274439088657 i=698304 salto=31 valore=273674408795 i=698335 salto=31 valore=272909728933 i=698366 salto=31 valore=272145049071 i=698397 salto=31 valore=271380369209 i=698428 salto=31 valore=270615689347 i=698459 salto=31 valore=279305391702 i=698988 salto=529
$2$
valore=278540711840 i=699019 salto=31 valore=277776031978 i=699050 salto=31 valore=277011352116 i=699081 salto=31 valore=276246672254 i=699112 salto=31 valore=275481992392 i=699143 salto=31 valore=274717312530 i=699174 salto=31 valore=273952632668 i=699205 salto=31 valore=273187952806 i=699236 salto=31 valore=272423272944 i=699267 salto=31 valore=271658593082 i=699298 salto=31 valore=270893913220 i=699329 salto=31 valore=270129233358 i=699360 salto=31 valore=279583615575 i=699858 salto=498 valore=278818935713 i=699889 salto=31 valore=278054255851 i=699920 salto=31 valore=277289575989 i=699951 salto=31 valore=276524896127 i=699982 salto=31 valore=275760216265 i=700013 salto=31 valore=274995536403 i=700044 salto=31 valore=274230856541 i=700075 salto=31 valore=273466176679 i=700106 salto=31 valore=272701496817 i=700137 salto=31 valore=271936816955 i=700168 salto=31 valore=271172137093 i=700199 salto=31 valore=270407457231 i=700230 salto=31 valore=279861839448 i=700728 salto=498 valore=279097159586 i=700759 salto=31 valore=278332479724 i=700790 salto=31 valore=277567799862 i=700821 salto=31 valore=276803120000 i=700852 salto=31 valore=276038440138 i=700883 salto=31 valore=275273760276 i=700914 salto=31 valore=274509080414 i=700945 salto=31 valore=273744400552 i=700976 salto=31 valore=272979720690 i=701007 salto=31 valore=272215040828 i=701038 salto=31 valore=271450360966 i=701069 salto=31 valore=270685681104 i=701100 salto=31 valore=279375383459 i=701629 salto=529
$2$
valore=278610703597 i=701660 salto=31 valore=277846023735 i=701691 salto=31 valore=277081343873 i=701722 salto=31 valore=276316664011 i=701753 salto=31 valore=275551984149 i=701784 salto=31 valore=274787304287 i=701815 salto=31 valore=274022624425 i=701846 salto=31 valore=273257944563 i=701877 salto=31 valore=272493264701 i=701908 salto=31 valore=271728584839 i=701939 salto=31 valore=270963904977 i=701970 salto=31 valore=270199225115 i=702001 salto=31 valore=279653607332 i=702499 salto=498 valore=278888927470 i=702530 salto=31 valore=278124247608 i=702561 salto=31 valore=277359567746 i=702592 salto=31 valore=276594887884 i=702623 salto=31 valore=275830208022 i=702654 salto=31 valore=275065528160 i=702685 salto=31 valore=274300848298 i=702716 salto=31 valore=273536168436 i=702747 salto=31 valore=272771488574 i=702778 salto=31 valore=272006808712 i=702809 salto=31 valore=271242128850 i=702840 salto=31 valore=270477448988 i=702871 salto=31 valore=279931831205 i=703369 salto=498 valore=279167151343 i=703400 salto=31 valore=278402471481 i=703431 salto=31 valore=277637791619 i=703462 salto=31 valore=276873111757 i=703493 salto=31 valore=276108431895 i=703524 salto=31 valore=275343752033 i=703555 salto=31 valore=274579072171 i=703586 salto=31 valore=273814392309 i=703617 salto=31 valore=273049712447 i=703648 salto=31 valore=272285032585 i=703679 salto=31 valore=271520352723 i=703710 salto=31 valore=270755672861 i=703741 salto=31 valore=279445375216 i=704270 salto=529
e quindi si ripeterà $1;2;2;2$; fino al prossimo salto dei salti
quindi il nostro valore sarà $11*12*31+7*498+4*529=9694$
ora bisognerebbe sapere la posizione del nostro $C$ nella sequenza ma siccome non la conosciamo dovremo provare per tutti i posti della sequenza
fino ad arrivare alla posizione giusta che ho segnato con gli asterischi
valore=278689411129 i=752771 salto=31 valore=277924731267 i=752802 salto=31 valore=277160051405 i=752833 salto=31 valore=276395371543 i=752864 salto=31 valore=275630691681 i=752895 salto=31 valore=274866011819 i=752926 salto=31 valore=274101331957 i=752957 salto=31 valore=273336652095 i=752988 salto=31 valore=272571972233 i=753019 salto=31 valore=271807292371 i=753050 salto=31 valore=271042612509 i=753081 salto=31 valore=270277932647 i=753112 salto=31 valore=279732314864 i=753610 salto=498 valore=278967635002 i=753641 salto=31 valore=278202955140 i=753672 salto=31 valore=277438275278 i=753703 salto=31 valore=276673595416 i=753734 salto=31 valore=275908915554 i=753765 salto=31 valore=275144235692 i=753796 salto=31 valore=274379555830 i=753827 salto=31 valore=273614875968 i=753858 salto=31 valore=272850196106 i=753889 salto=31 valore=272085516244 i=753920 salto=31 valore=271320836382 i=753951 salto=31 valore=270556156520 i=753982 salto=31 valore=279245858875 i=754511 salto=529 valore=278481179013 i=754542 salto=31 valore=277716499151 i=754573 salto=31 valore=276951819289 i=754604 salto=31 valore=276187139427 i=754635 salto=31 valore=275422459565 i=754666 salto=31 valore=274657779703 i=754697 salto=31 valore=273893099841 i=754728 salto=31 valore=273128419979 i=754759 salto=31 valore=272363740117 i=754790 salto=31 valore=271599060255 i=754821 salto=31 valore=270834380393 i=754852 salto=31 valore=270069700531 i=754883 salto=31 valore=279524082748 i=755381 salto=498 valore=278759402886 i=755412 salto=31 valore=277994723024 i=755443 salto=31 valore=277230043162 i=755474 salto=31 valore=276465363300 i=755505 salto=31 valore=275700683438 i=755536 salto=31 valore=274936003576 i=755567 salto=31 valore=274171323714 i=755598 salto=31 valore=273406643852 i=755629 salto=31 valore=272641963990 i=755660 salto=31 valore=271877284128 i=755691 salto=31 valore=271112604266 i=755722 salto=31 valore=270347924404 i=755753 salto=31 valore=279802306621 i=756251 salto=498 valore=279037626759 i=756282 salto=31 valore=278272946897 i=756313 salto=31 valore=277508267035 i=756344 salto=31 valore=276743587173 i=756375 salto=31 valore=275978907311 i=756406 salto=31 valore=275214227449 i=756437 salto=31 valore=274449547587 i=756468 salto=31 valore=273684867725 i=756499 salto=31 valore=272920187863 i=756530 salto=31 valore=272155508001 i=756561 salto=31 valore=271390828139 i=756592 salto=31 valore=270626148277 i=756623 salto=31 valore=279315850632 i=757152 salto=529 valore=278551170770 i=757183 *****************************************************
quindi il nostro valore sarà
$5*12*31+3*498+2*529=4412$
quindi avremo $(X-4412-694607)/9694=D$
nel nostro caso $D=6$
si ricostruisce il solito sistema che ancora non so risolvere
e si trovano le soluzioni
$C=757183$
$Z=1123591$
P.s. le sequenze si possono trovare in tempi logaritmici
P.s.2.se c'è un metodo matematico per trovare quelle sequenze gentilmente qualcuno me lo indichi
Mi è venuto in mente un altro algoritmo di fattorizzazione.
Ora ve lo mostro:
Ragioniamo su un numero $N=p*q$ prodotto di due primi nella forma $p=6a+1$ e $q=6b+1$
segue che $N=36ab+6a+6b+1$
riscriviamo
$N-1=36ab+6*(a+b)$
quindi $r=(N-1)mod (36)$
quindi $6*(a+b)=K*36+r$
quindi facendo variare il K abbiamo un primo metodo per fattorizzare
Esempio:
$N=101461$
$101460 mod 36 =12$
$6*(a+b)=18*36+12$
dove abbiamo fatto variare il $K$ da $0$ a $18$ quindi $19$ cicli
Ma procediamo
eravamo rimasti
$N=36ab+6a+6b+1$
$6*(a+b)=K*36+r$
quindi ci calcoliamo $a*b$
$a*b=[N-1-(K*36+r)]/36$
quindi
$a*b=(N-1-r)/36-K$
quindi
imponiamo
$a*b=(N-1-r)/36$
perchè $K$ è molto più piccolo di $a*b$
facendo il sistema
$N=36ab+6a+6b+1$
$a*b=(N-1-r)/36$
e partendo dal massimo valore di $(N-1-r)/36$ e che il sistema non abbia soluzioni con parte immaginaria
scalando di una unità
Ve lo spiego con un esempio
Esempio:
$N=101461$
$101460 mod 36 =12$
$6*(a+b)=K*36+12$
$a*b=(N-1-r)/36=2818$
Facciamo il sistema:
$101461=36ab+6a+6b+1$
$a*b=2818$
ed esce la parte immaginaria come si può vedere
https://www.wolframalpha.com/input/?i=1 ... %3D%3D2818
il primo valore valido è da testare senza che nelle soluzioni ci sia la parte immaginaria è 2800
$101461=36ab+6a+6b+1$
$a*b=2800$
https://www.wolframalpha.com/input/?i=1 ... a*b%3D2800
che ci dà la soluzione ma non lasciatevi ingannare, vi mostro un altro esempio dove non è così rapido
Esempio
N=71054743
$71054742 mod 36 = 30$
$a*b=(71054743-1-30)/36=1973742$
quindi il nostro sistema
$71054743=36ab+6a+6b+1$
$a*b=1973742$
https://www.wolframalpha.com/input/?i=a ... ,+(6*a%2B1)*(6*b%2B1)%3D71054743
come si vede abbiamo la parte immaginaria
il primo valore valido è 1973274
$71054743=36ab+6a+6b+1$
$a*b=1973274$
https://www.wolframalpha.com/input/?i=a ... ,+(6*a%2B1)*(6*b%2B1)%3D71054743
Quindi facendo variarare
$1973274$
$1973273$
$1973272$
......
......
arriveremo a $1973268$
$71054743=36ab+6a+6b+1$
$a*b=1973268$
infatti
https://www.wolframalpha.com/input/?i=a ... ,+(6*a%2B1)*(6*b%2B1)%3D71054743
Gentilmente vi chiedo qual'è la complessità computazionale di questo algoritmo?
sperando di non aver commesso errori
Ora ve lo mostro:
Ragioniamo su un numero $N=p*q$ prodotto di due primi nella forma $p=6a+1$ e $q=6b+1$
segue che $N=36ab+6a+6b+1$
riscriviamo
$N-1=36ab+6*(a+b)$
quindi $r=(N-1)mod (36)$
quindi $6*(a+b)=K*36+r$
quindi facendo variare il K abbiamo un primo metodo per fattorizzare
Esempio:
$N=101461$
$101460 mod 36 =12$
$6*(a+b)=18*36+12$
dove abbiamo fatto variare il $K$ da $0$ a $18$ quindi $19$ cicli
Ma procediamo
eravamo rimasti
$N=36ab+6a+6b+1$
$6*(a+b)=K*36+r$
quindi ci calcoliamo $a*b$
$a*b=[N-1-(K*36+r)]/36$
quindi
$a*b=(N-1-r)/36-K$
quindi
imponiamo
$a*b=(N-1-r)/36$
perchè $K$ è molto più piccolo di $a*b$
facendo il sistema
$N=36ab+6a+6b+1$
$a*b=(N-1-r)/36$
e partendo dal massimo valore di $(N-1-r)/36$ e che il sistema non abbia soluzioni con parte immaginaria
scalando di una unità
Ve lo spiego con un esempio
Esempio:
$N=101461$
$101460 mod 36 =12$
$6*(a+b)=K*36+12$
$a*b=(N-1-r)/36=2818$
Facciamo il sistema:
$101461=36ab+6a+6b+1$
$a*b=2818$
ed esce la parte immaginaria come si può vedere
https://www.wolframalpha.com/input/?i=1 ... %3D%3D2818
il primo valore valido è da testare senza che nelle soluzioni ci sia la parte immaginaria è 2800
$101461=36ab+6a+6b+1$
$a*b=2800$
https://www.wolframalpha.com/input/?i=1 ... a*b%3D2800
che ci dà la soluzione ma non lasciatevi ingannare, vi mostro un altro esempio dove non è così rapido
Esempio
N=71054743
$71054742 mod 36 = 30$
$a*b=(71054743-1-30)/36=1973742$
quindi il nostro sistema
$71054743=36ab+6a+6b+1$
$a*b=1973742$
https://www.wolframalpha.com/input/?i=a ... ,+(6*a%2B1)*(6*b%2B1)%3D71054743
come si vede abbiamo la parte immaginaria
il primo valore valido è 1973274
$71054743=36ab+6a+6b+1$
$a*b=1973274$
https://www.wolframalpha.com/input/?i=a ... ,+(6*a%2B1)*(6*b%2B1)%3D71054743
Quindi facendo variarare
$1973274$
$1973273$
$1973272$
......
......
arriveremo a $1973268$
$71054743=36ab+6a+6b+1$
$a*b=1973268$
infatti
https://www.wolframalpha.com/input/?i=a ... ,+(6*a%2B1)*(6*b%2B1)%3D71054743
Gentilmente vi chiedo qual'è la complessità computazionale di questo algoritmo?
sperando di non aver commesso errori
Test di primalità e fattorizzazione di Lepore (ultimo)
Eravamo rimasti qui
Definizione
Tutti i numeri NR escluso i multipli di 2 e di 3 si scrivono nella forma 6h+1 e 6h+5.
Dimostrazione
NR modulo 6 =1 -> 6h+1
NR modulo 6 =2 -> è multiplo di 2
NR modulo 6 =3 -> è multiplo di 3
NR modulo 6 =4 -> è multiplo di 2
NR modulo 6 =5 -> 6h+1
NR modulo 6 =0 -> è multiplo di 2 e di 3
Lemma
Quindi partendo da 1 e facendo +2 e +4 si ha
1 5 7 11 13 17 19 23 25 29 ecc.ecc.
Definizione
Ogni numero NR escluso i multipli di 2 e di 3 si scrivono nella forma
1) X^2+6nX=NR
2) X^2+6nX+2X=NR
3) X^2+6nX+4X=NR
Dimostrazione
Dal lemma segue direttamente
1) X(X+6n)=NR
2) X(X+6n+2)=NR
3) X(X+6n+4)=NR
In più si può osservare che:
(6h+1)*(6k+1)=6G+1
(6h+5)*(6k+5)=6G+1
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5
----------------------------------------------------------------------------------------
Da ciò si può dedurre che risolvendo (6h+1)*(6k+1)=6G+1
si possano risolvere gli altri tre casi
questi
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5
moltiplicando per 5
e questo
(6h+5)*(6k+5)=6G+1
moltiplicando per 25
utilizzo questo per non scrivere quattro algoritmi diversi ma uno solo
----------------------------------------------------------------------------------
Per capire il ragionamento ci scriviamo in una tabella tutti gli NR generati da
X^2+6nX=NR
con x che parte da 1 e fa +6
cioè 1 7 13 19 35 31 37 43 ecc. ecc
e con n che parte da 1 e fa +1
cioè 1 2 3 4 5 6 ecc. ecc.
come in questa immagione
Supponiamo che il nostro NR sia 703=19*37
sqrt(703)=26,.....
quindi i possibili valori di q andranno da 31 a 703
mettiamoci più bassi e scegliamo 31 e analizziamo la sua diagonale come nell'immagine
vediamo che 775>703 e 589<703 quindi testiamo il 19 che è il nostro p
ma vediamo come muoverci se non lo becchiamo subito
scegliamo 931=19*43
sqrt(931)=30,.....
vediamo sempre più bassi e scegliamo 31 si può notare che il 775<931 quindi dobbiamo salire
quindi saliamo direttamente e scegliamo il 37 e vediamo che 1147>931 e 925<931 quindi testiamo il 25 che non è il nostro numero
quindi dovremo scendere e vedere il 31 che ci dice ma già lo abbiamo visto quindi passiamo a 43 che ci identifica proprio il 931
Ora vediamo più alti che succede
NR=589
prendiamo 43 e vediamo che 559<589 e 817>589 testiamo 13 e scendiamo
prendiamo 37 e 481<589 e 703>589 testiamo il 19 e scendiamo
prendiamo 31 che ci identifica proprio il 789
Ah dimenticavo per trovare i valori sulle diagonali
ad esempio l'incrocio 37 con 13 si fa 37*13=481
logaritmicamente ci troviamo i valori sulla diagonale
e logaritmicamente scendiamo e saliamo
Speranzoso di non aver commesso errori e in una vostra risposta cordialmente vi saluto
Alberico Lepore
Eravamo rimasti qui
Definizione
Tutti i numeri NR escluso i multipli di 2 e di 3 si scrivono nella forma 6h+1 e 6h+5.
Dimostrazione
NR modulo 6 =1 -> 6h+1
NR modulo 6 =2 -> è multiplo di 2
NR modulo 6 =3 -> è multiplo di 3
NR modulo 6 =4 -> è multiplo di 2
NR modulo 6 =5 -> 6h+1
NR modulo 6 =0 -> è multiplo di 2 e di 3
Lemma
Quindi partendo da 1 e facendo +2 e +4 si ha
1 5 7 11 13 17 19 23 25 29 ecc.ecc.
Definizione
Ogni numero NR escluso i multipli di 2 e di 3 si scrivono nella forma
1) X^2+6nX=NR
2) X^2+6nX+2X=NR
3) X^2+6nX+4X=NR
Dimostrazione
Dal lemma segue direttamente
1) X(X+6n)=NR
2) X(X+6n+2)=NR
3) X(X+6n+4)=NR
In più si può osservare che:
(6h+1)*(6k+1)=6G+1
(6h+5)*(6k+5)=6G+1
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5
----------------------------------------------------------------------------------------
Da ciò si può dedurre che risolvendo (6h+1)*(6k+1)=6G+1
si possano risolvere gli altri tre casi
questi
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5
moltiplicando per 5
e questo
(6h+5)*(6k+5)=6G+1
moltiplicando per 25
utilizzo questo per non scrivere quattro algoritmi diversi ma uno solo
----------------------------------------------------------------------------------
Per capire il ragionamento ci scriviamo in una tabella tutti gli NR generati da
X^2+6nX=NR
con x che parte da 1 e fa +6
cioè 1 7 13 19 35 31 37 43 ecc. ecc
e con n che parte da 1 e fa +1
cioè 1 2 3 4 5 6 ecc. ecc.
come in questa immagione
Supponiamo che il nostro NR sia 703=19*37
sqrt(703)=26,.....
quindi i possibili valori di q andranno da 31 a 703
mettiamoci più bassi e scegliamo 31 e analizziamo la sua diagonale come nell'immagine
vediamo che 775>703 e 589<703 quindi testiamo il 19 che è il nostro p
ma vediamo come muoverci se non lo becchiamo subito
scegliamo 931=19*43
sqrt(931)=30,.....
vediamo sempre più bassi e scegliamo 31 si può notare che il 775<931 quindi dobbiamo salire
quindi saliamo direttamente e scegliamo il 37 e vediamo che 1147>931 e 925<931 quindi testiamo il 25 che non è il nostro numero
quindi dovremo scendere e vedere il 31 che ci dice ma già lo abbiamo visto quindi passiamo a 43 che ci identifica proprio il 931
Ora vediamo più alti che succede
NR=589
prendiamo 43 e vediamo che 559<589 e 817>589 testiamo 13 e scendiamo
prendiamo 37 e 481<589 e 703>589 testiamo il 19 e scendiamo
prendiamo 31 che ci identifica proprio il 789
Ah dimenticavo per trovare i valori sulle diagonali
ad esempio l'incrocio 37 con 13 si fa 37*13=481
logaritmicamente ci troviamo i valori sulla diagonale
e logaritmicamente scendiamo e saliamo
Speranzoso di non aver commesso errori e in una vostra risposta cordialmente vi saluto
Alberico Lepore
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo