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
Ho scoperto delle nuove cose:
(a) questa tabella è divisa in atomi
(b) funziona come lo snake (il gioco)
(c) se trovi la diagonale hai trovato il tesoro
(a) ogni numero di questa tabella è circondato da numeri e questa circonferenza compreso il numero stesso è ordinata
esempio 1333
è ordinato così 775 925 1075 1147 1333 1519 1591 1813 2035
esempio 91
è ordinato così 91 133 247 325
(b) ogni numero N di questa tabella è raggiungibile da un qualsiasi altro numero di questa tabella
si sceglie un numero e si guarda tutto l'atomo il valore più vicino al numero da cercare N sarà il fulcro del prossimo atomo fino ad arrivare al numero stesso N
esempio N=1333 e partiamo da ad esempio 91
la sequenza di fulcri sarà 91 325 703 1225 1075 1333
esempio 1375 e partiamo ad esempio da 775
la sequenza sarà 775 1333 1519 1225 1375
(c) ogni numero di questa tabella è identificato dalle regole di (b) con una diagonale
esempio 1891
la diagonale sarà 91 325 703 1225 1891
esempio 2035
la diagonale sarà 775 133 2035
esempio 1375
la diagonale sarà 133 403 817 1375
Speranzoso di non aver commesso errori e in una vostra risposta cordialmente vi saluto
Alberico Lepore
Algoritmo
Sia N=p*q con p , q ed N nella forma 6*h+1
Si troverà la fattorizzazione in al massimo logaritmo di [(N - F)/6] dove F è il primo numero dopo la radice quadrata di N nella forma 6*h+1.
Le regole del logaritmo:
scelto un G nell'intervallo [(N - F)/6, (N-1)/6] allora g=6*G+1
Testo se N modulo g = 0
se g*7 > N allora G deve scendere
altrimenti
se g*(g-6) < N allora G deve salire
altrimenti
se {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g+6)}&&
&& {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)}
&& {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte superiore di [(N/g)/6]}+1}*(g+6)}
||
se {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte superiore di [(N/g)/6]}+1}*(g+6)}&&
&& {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)}
&& {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g+6)}
allora G deve scendere
altrimenti
G deve salire
Sia N=p*q con p , q ed N nella forma 6*h+1
Si troverà la fattorizzazione in al massimo logaritmo di [(N - F)/6] dove F è il primo numero dopo la radice quadrata di N nella forma 6*h+1.
Le regole del logaritmo:
scelto un G nell'intervallo [(N - F)/6, (N-1)/6] allora g=6*G+1
Testo se N modulo g = 0
se g*7 > N allora G deve scendere
altrimenti
se g*(g-6) < N allora G deve salire
altrimenti
se {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g+6)}&&
&& {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)}
&& {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte superiore di [(N/g)/6]}+1}*(g+6)}
||
se {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte superiore di [(N/g)/6]}+1}*(g+6)}&&
&& {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g-6)}
&& {N-{6*{parte superiore di [(N/g)/6]}+1}*(g-6)} < {N-{6*{parte inferiore di [(N/g)/6]}+1}*(g+6)}
allora G deve scendere
altrimenti
G deve salire
Ho letto solo l'ultimo post, che mi sembra molto meglio di tutti gli altri che sono incomprensibili (almeno per me).
Se spieghi cosa vuol dire 'deve scendere' e 'deve salire' e fornisci un modo determistico di scegliere $G$, quello che hai scritto nell'ultimo post sembra quasi un algoritmo. Poi c'e' da vedere se funziona e se ha la complessita' che dici.
Se spieghi cosa vuol dire 'deve scendere' e 'deve salire' e fornisci un modo determistico di scegliere $G$, quello che hai scritto nell'ultimo post sembra quasi un algoritmo. Poi c'e' da vedere se funziona e se ha la complessita' che dici.
grazie pappappero
cercherò di spiegarmi meglio (almeno ci provo)
Ennesimo test di fattorizzazione di Lepore in log
Per capire ci scriviamo una tabella dove i valori cerchiati sono i valori G=(N-1)/6
di questa tabella
cioè questa
i numeri di fianco a due cerchiati sono la differenza dei due numeri cerchiati
si deduce facilmente che $n+(8+6*n)*a+6*a*(a-1)=G$
dove a=(x-1)/6 per N=x*y
e n è x^2+6*n*x=N
prendiamo ad esempio il numero N=1705 quindi G=284 dobbiamo trovare il valore 80
una volta trovato 80 allora troveremo 1225=(x-6)^+6*n*(x-6) e 1705=x^2+6*n*x facciamo il sistema e lo fattorizziamo.
Ora viene quello difficile da spiegare (ci provo)
se prendiamo un valore anche di poco più grande di 80 ad esempio 92
vi faccio vedere che succede 92+80+68=240 e dobbiamo fermarci perchè aggiungendo 56 supereremo il 284
quindi n dovrebbe essere n=284-240=44 e a=3
ma sappiamo che n=(G-6*a^2-2a)/(6*a+1)=11,78...
per farle combaciare le due n significa che dovrebbe scendere il 44
che significa che a dovrebbe salire quindi 92 non va bene ed abbiamo bisogno di un valore più basso
un 'avvertenza
con i numeri bassi se scegliamo come nell'esempio al posto di 80, il 68 non si arriverà mai al 284
cercherò di spiegarmi meglio (almeno ci provo)
Ennesimo test di fattorizzazione di Lepore in log
Per capire ci scriviamo una tabella dove i valori cerchiati sono i valori G=(N-1)/6
di questa tabella
cioè questa
i numeri di fianco a due cerchiati sono la differenza dei due numeri cerchiati
si deduce facilmente che $n+(8+6*n)*a+6*a*(a-1)=G$
dove a=(x-1)/6 per N=x*y
e n è x^2+6*n*x=N
prendiamo ad esempio il numero N=1705 quindi G=284 dobbiamo trovare il valore 80
una volta trovato 80 allora troveremo 1225=(x-6)^+6*n*(x-6) e 1705=x^2+6*n*x facciamo il sistema e lo fattorizziamo.
Ora viene quello difficile da spiegare (ci provo)
se prendiamo un valore anche di poco più grande di 80 ad esempio 92
vi faccio vedere che succede 92+80+68=240 e dobbiamo fermarci perchè aggiungendo 56 supereremo il 284
quindi n dovrebbe essere n=284-240=44 e a=3
ma sappiamo che n=(G-6*a^2-2a)/(6*a+1)=11,78...
per farle combaciare le due n significa che dovrebbe scendere il 44
che significa che a dovrebbe salire quindi 92 non va bene ed abbiamo bisogno di un valore più basso
un 'avvertenza
con i numeri bassi se scegliamo come nell'esempio al posto di 80, il 68 non si arriverà mai al 284
Non devi prendere un esempio. Devi scrivere un algoritmo.
Hey c'ho provato ma non so se l'ho scritto bene
Algoritmo di fattorizzazione
Sia N=p*q nella forma N=6*G+1 e p=6*a+1 e q=6b+1
Sia G=(N-1)/6
sia A un numero
Se G è dispari A è nella forma 12*k+2
Se G è pari A è nella forma 12*h+8
A è compreso nell'intervallo [8,G] //il valore G è da rivedere però non fa niente
Scelto un A in [8,G](supponiamo con G pari)
dobbiamo sottrarre a G la somma dei numeri A+(A-12)+(A-24)+(A-36)......
fino ad arrivare all'ultimo numero positivo
il numero di questi numeri sarà la nostra ipotetica a
(siccome ho trovato che A+6=p+q)
facciamo q=A+6-(6*a+1)
Se gli ipotetici p*q == N abbiamo trovato i valori p e q reali
Se gli ipotetici p*q < N dobbiamo far scendere il valore di A
Se gli ipotetici p*q > N dobbiamo far salire il valore di A
Algoritmo di fattorizzazione
Sia N=p*q nella forma N=6*G+1 e p=6*a+1 e q=6b+1
Sia G=(N-1)/6
sia A un numero
Se G è dispari A è nella forma 12*k+2
Se G è pari A è nella forma 12*h+8
A è compreso nell'intervallo [8,G] //il valore G è da rivedere però non fa niente
Scelto un A in [8,G](supponiamo con G pari)
dobbiamo sottrarre a G la somma dei numeri A+(A-12)+(A-24)+(A-36)......
fino ad arrivare all'ultimo numero positivo
il numero di questi numeri sarà la nostra ipotetica a
(siccome ho trovato che A+6=p+q)
facciamo q=A+6-(6*a+1)
Se gli ipotetici p*q == N abbiamo trovato i valori p e q reali
Se gli ipotetici p*q < N dobbiamo far scendere il valore di A
Se gli ipotetici p*q > N dobbiamo far salire il valore di A
Proviamo cosi'.
Input: $N$ della forma $N = pq$ con $p,q \equiv 1 \mod 6$.
Output: $p,q$.
Input: $N$ della forma $N = pq$ con $p,q \equiv 1 \mod 6$.
Output: $p,q$.
1. Definisco $G = (N-1)/6$;
2.
- se $G$ e' dispari, definisco $A$ che sia pari e il piu' vicino possibile a $(G-8)/2$(perche' ho in mente di partire dal centro dell'intervallo...o vuoi partire da un'altra parte? o vuoi fare un algoritmo non deterministico? boh)
- se $G$ e' dispari, definisco $A$ che sia congruo a $2$ modulo $6$ e il piu' vicino possibile a $(G-8)/2$
[/list:u:2y8sviy8]
3 Poi ?
[/list:u:2y8sviy8]
247
G=41
i possibili A sono 14 26 38
li faccio tutti e tre
per il 14
41-14-2
a=2
p=14+6-13=7
p*(6*a+1)=91<247
per il 26
41-26-14
a=2
p=26+6-13
p*(6*a+1)=247=247
per il 38
41-38
a=1
p=38+6-7=37
p*(6*a+1)=259>247
EDIT:Non i preoccupare è tutto regolare
nel caso A=14 come noti c'è un anomalia che si risolve con la teoria
e
nel caso 38 devo ancora scegliere l'intervallo come ti ho già detto
mi spiego meglio vedi sul caso A=14
per il 26
41-26-14
a=2
p=26+6-13
p*(6*a+1)=247=247
vedi il 14 di 41-26-14
bene questo 14=6*n+8 dove n è la n di p^2+6*n*p=247
quindi
vedi
41-14-2
significherebbe 6*n+8=2 cioè n < 0 impossibile
quindi per quanto riguarda l'algoritmo
se G è dispari e si arriva a 2 dobbiamo far salire la A
se G è pari e si arriva a 8 dobbiamo controllare p^2=N e p non è intero far salire la A
per quanto riguarda l'intervallo [8,G] mi prendo un po di tempo per capire meglio
L'intervallo dovrebbe essere questo se non ho commesso errori
[ 8 , (7*(6*parteinterainferioredi((N/7)/6)+1)-1)/6 - (parteinterainferioredi((N/7)/6)-1)]
cioè per il 247 sarà [8,32]
G=41
i possibili A sono 14 26 38
li faccio tutti e tre
per il 14
41-14-2
a=2
p=14+6-13=7
p*(6*a+1)=91<247
per il 26
41-26-14
a=2
p=26+6-13
p*(6*a+1)=247=247
per il 38
41-38
a=1
p=38+6-7=37
p*(6*a+1)=259>247
EDIT:Non i preoccupare è tutto regolare
nel caso A=14 come noti c'è un anomalia che si risolve con la teoria
e
nel caso 38 devo ancora scegliere l'intervallo come ti ho già detto
mi spiego meglio vedi sul caso A=14
per il 26
41-26-14
a=2
p=26+6-13
p*(6*a+1)=247=247
vedi il 14 di 41-26-14
bene questo 14=6*n+8 dove n è la n di p^2+6*n*p=247
quindi
vedi
41-14-2
significherebbe 6*n+8=2 cioè n < 0 impossibile
quindi per quanto riguarda l'algoritmo
se G è dispari e si arriva a 2 dobbiamo far salire la A
se G è pari e si arriva a 8 dobbiamo controllare p^2=N e p non è intero far salire la A
per quanto riguarda l'intervallo [8,G] mi prendo un po di tempo per capire meglio
L'intervallo dovrebbe essere questo se non ho commesso errori
[ 8 , (7*(6*parteinterainferioredi((N/7)/6)+1)-1)/6 - (parteinterainferioredi((N/7)/6)-1)]
cioè per il 247 sarà [8,32]
supponiamo di voler fattorizzare un numero N
G=(N-1)/6
supponiamolo pari quindi A è nella forma A=6h+8
partiamo da 8 e logaritmicamente ci calcoliamo l'ipotetica c
(cioè quante volte dobbiamo fare +12 per arrivare a G )
e controlliamo
(6*a+1)^2+*n*(6*a+1)=N
(6*(a-c-1)+1)^2+*n*(6*(a-c-1)+1)=6*W+1
dove W=G-S
dove S=8*(c+1)+12*(c*(c+1))/2
raddoppiamo il valore di 8 e prendiamo il valore 20
e reiteriamo il procedimento stando attenti a non superare il doppio nelle scelte successive
quindi scegliamo il 32
poi il 56
poi il 104
poi il 200
Questo metodo dovrebbe funzionare al 100%
Esempio N=3397
G=(3397-1)/6=566
per 8 niente
per 20 niente
per 32 niente
vediamo per 56
c=5
S=56*6+6*30=516
W=566-516=50
6*50+1=301
quindi il sistema
(6*a+1)^2+6*n*(6*a+1)=N
(6*(a-5-1)+1)^2+6*n*(6*(a-5-1)+1)=301
Grazie per l'attenzione
G=(N-1)/6
supponiamolo pari quindi A è nella forma A=6h+8
partiamo da 8 e logaritmicamente ci calcoliamo l'ipotetica c
(cioè quante volte dobbiamo fare +12 per arrivare a G )
e controlliamo
(6*a+1)^2+*n*(6*a+1)=N
(6*(a-c-1)+1)^2+*n*(6*(a-c-1)+1)=6*W+1
dove W=G-S
dove S=8*(c+1)+12*(c*(c+1))/2
raddoppiamo il valore di 8 e prendiamo il valore 20
e reiteriamo il procedimento stando attenti a non superare il doppio nelle scelte successive
quindi scegliamo il 32
poi il 56
poi il 104
poi il 200
Questo metodo dovrebbe funzionare al 100%
Esempio N=3397
G=(3397-1)/6=566
per 8 niente
per 20 niente
per 32 niente
vediamo per 56
c=5
S=56*6+6*30=516
W=566-516=50
6*50+1=301
quindi il sistema
(6*a+1)^2+6*n*(6*a+1)=N
(6*(a-5-1)+1)^2+6*n*(6*(a-5-1)+1)=301
Grazie per l'attenzione
Questo metodo non si capisce.
Perche' non prendi il mio post precedente e provi a completare l'algoritmo da li'? O a cambiarlo come vuoi, ma provando a renderlo comprensibile?
Ogni lettera che usi deve avere una definizione. Se fai un ciclo for devi dire da dove a dove. Se usi una while devi dire la condizione per cui si ferma. Un algoritmo e' una cosa precisa e quelli che tu scrivi, cosi' a occhio, non lo sono.
Aggiungere esempi, senza spiegare cosa uno fa, non aiuta.
Perche' non prendi il mio post precedente e provi a completare l'algoritmo da li'? O a cambiarlo come vuoi, ma provando a renderlo comprensibile?
Ogni lettera che usi deve avere una definizione. Se fai un ciclo for devi dire da dove a dove. Se usi una while devi dire la condizione per cui si ferma. Un algoritmo e' una cosa precisa e quelli che tu scrivi, cosi' a occhio, non lo sono.
Aggiungere esempi, senza spiegare cosa uno fa, non aiuta.
l'ho scritto con GMP 6.1.1
il numero da fattorizzare va in un file input.txt nella stessa cartella
non ho ancora scritto per G disparii
bisogna settare settaggio1
A me con numeri grandi da questo errore
GNU MP: Cannot allocate memory (size=4)
il numero da fattorizzare va in un file input.txt nella stessa cartella
non ho ancora scritto per G disparii
bisogna settare settaggio1
A me con numeri grandi da questo errore
GNU MP: Cannot allocate memory (size=4)
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <gmp.h>
int prendi_numero(char in[]);
void verifica_pseudo_a(mpz_t *a, mpz_t pseudo_a,int *check,mpz_t pseudo_A, mpz_t G, mpz_t RSA);
int main(){
mpf_set_default_prec(10000);/*set this value*/
mpz_t RSA,n,G,uno,zero,due,sei,var_mom1,var_mom2,var_mom3,var_mom4,var_mom5,var_mom6,dodici,quattro,a,venticinque,alpha,secinque,cinque,settaggio1,gamma,beta;
mpz_init(RSA);
char numero_RSA[10000];/*set this value*/
prendi_numero(numero_RSA);
mpz_init_set_str (RSA, numero_RSA, 10);
//inizio
/*
IMPORTANTE Impostare settaggio1 con ipotetico (q-p)/6
*/
mpz_init_set_str (settaggio1, "500", 10);
mpz_init(n);
mpz_init(G);
mpz_init_set_str (uno, "1", 10);
mpz_init_set_str (zero, "0", 10);
mpz_init_set_str (due, "2", 10);
mpz_init_set_str (sei, "6", 10);
mpz_init(var_mom1);
mpz_init(var_mom2);
mpz_init(var_mom3);
mpz_init(var_mom4);
mpz_init(var_mom5);
mpz_init(var_mom6);
mpz_init_set_str (dodici, "12", 10);
mpz_init_set_str (quattro, "4", 10);
mpz_init(a);
mpz_init(alpha);
mpz_init(beta);
mpz_init(gamma);
mpz_init(secinque);
mpz_init_set_str (cinque, "5", 10);
int check;
mpz_init_set_str (venticinque, "25", 10);
mpz_mod(secinque,RSA,sei);
if(mpz_cmp(secinque,cinque)==0){//se RSA modulo sei uguale a cinque
int i;
scanf("%d",&i);
mpz_mul(RSA,RSA,cinque);
}
//mpz_mul(RSA,RSA,venticinque);//se RSA modulo sei è uguale ad uno e p e w sono nella forma 6*a+5 (però non lo sappaiamo apriori)
mpz_sub(G,RSA,uno);
mpz_div(G,G,sei);
mpz_mod(var_mom1,G,due);
if(mpz_cmp(var_mom1,zero)==0){
mpz_mul(var_mom5,sei,settaggio1);
mpz_mul(var_mom2,var_mom5,var_mom5);
mpz_mul(var_mom3,quattro,RSA);
mpz_add(var_mom2,var_mom2,var_mom3);
mpz_sqrt(var_mom2,var_mom2);
mpz_sub(var_mom2,var_mom2,var_mom5);
mpz_div(var_mom2,var_mom2,due);
mpz_div(var_mom2,var_mom2,sei);
mpz_mul(var_mom2,var_mom2,sei);
mpz_add(alpha,var_mom2,uno);//31
gmp_printf ("\n\n\n\n\n\nalpha=%Zd \n\n\n\n\n",alpha);
mpz_mul(var_mom5,alpha,alpha);
mpz_mul(var_mom6,settaggio1,alpha);
mpz_mul(var_mom6,var_mom6,sei);
mpz_add(gamma,var_mom5,var_mom6);
mpz_div(beta,gamma,alpha);//101
gmp_printf ("\n\n\n\n\n\nbeta=%Zd \n\n\n\n\n",beta);
mpz_sub(alpha,alpha,dodici);
mpz_sub(beta,beta,dodici);
while(check!=1){
mpz_add(alpha,alpha,sei);
mpz_add(beta,beta,sei);
mpz_mul(var_mom2,alpha,beta);//31*101
mpz_add(var_mom4,alpha,sei);//37
mpz_add(var_mom3,beta,sei);//107
mpz_mul(var_mom3,var_mom3,var_mom4);//37*107
mpz_sub(var_mom2,var_mom3,var_mom2);
mpz_div(var_mom2,var_mom2,sei);
gmp_printf ("\n\n\n\n\n\nA=%Zd \n\n\n\n\n",var_mom2);
verifica_pseudo_a(&a, uno,&check,var_mom2,G,RSA);
//gmp_printf ("\n\n\n\n\n\nX=%Zd \n\n\n\n\n",a);
}
}else{
printf("\nNONONONONNO Ancora non scrivo (N-1)/6=dispari\n");
}
gmp_printf ("\n\n\n\n\n\nX=%Zd \n\n\n\n\n",a);
}
void verifica_pseudo_a(mpz_t *a, mpz_t pseudo_a,int *check,mpz_t pseudo_A, mpz_t G, mpz_t RSA){
mpz_t var_mom1,var_mom2,var_mom3,sei,due,n,otto,uno,S,W,trentasei,settantadue,duecentosedici,dodici,var_mom4,var_mom5,quattro,zero;
mpz_init(var_mom1);
mpz_init(var_mom2);
mpz_init(var_mom3);
mpz_init_set_str (sei, "6", 10);
mpz_init_set_str (due, "2", 10);
mpz_init(n);
mpz_init_set_str (otto, "8", 10);
mpz_init_set_str (uno, "1", 10);
mpz_init(S);
mpz_init(W);
mpz_init_set_str (trentasei, "36", 10);
mpz_init_set_str (settantadue, "72", 10);
mpz_init_set_str (duecentosedici, "216", 10);
mpz_init_set_str (dodici, "12", 10);
mpz_init(var_mom4);
mpz_init_set_str (zero, "0", 10);
mpz_init(var_mom5);
mpz_init_set_str (quattro, "4", 10);
mpz_sub(n,pseudo_A,otto);
mpz_div(n,n,sei);//n
mpz_mul(var_mom1,pseudo_a,pseudo_a);
mpz_mul(var_mom1,var_mom1,sei);//6a^2
mpz_mul(var_mom2,pseudo_a,n);
mpz_mul(var_mom2,var_mom2,sei);//6an
mpz_mul(var_mom3,pseudo_a,due);//2a
mpz_add(var_mom1,var_mom1,n);
mpz_add(var_mom1,var_mom1,var_mom2);
mpz_add(var_mom1,var_mom1,var_mom3);
//gmp_printf ("\nmom1=%Zd G=%Zd\n",var_mom1,G);
if(mpz_cmp (var_mom1,G)==0){
mpz_set(*a,pseudo_a);
*check=1;
return;
}
/*
W=G-S
dove S=8*(c)+12*(c*(c-1))/2*/
/*if(mpz_cmp (pseudo_a,zero)==0){
return;
}*/
//gmp_printf ("\na=%Zd A=%Zd\n",pseudo_a,pseudo_A);
mpz_sub(var_mom1,pseudo_a,uno);//a-1
mpz_mul(var_mom2,pseudo_a,pseudo_A);
mpz_mul(var_mom3,pseudo_a,var_mom1);
mpz_mul(var_mom3,var_mom3,sei);
mpz_add(S,var_mom2,var_mom3);
mpz_sub(var_mom1,G,S);
mpz_mul(var_mom1,var_mom1,sei);
mpz_add(W,var_mom1,uno);
//gmp_printf ("\nW=%Zd\n",W);
if(mpz_cmp (pseudo_A,G)>0){
//int i;
//scanf("%d",&i);
return;
}
//-216*c*a^2+(6*RSA-6*W+216*c^2-72*c)*a+(RSA-W+36*c^2-12*c-36*G*c)=0
mpz_mul(var_mom1,duecentosedici,pseudo_a);
mpz_sub(var_mom1,zero,var_mom1);//termine a^2
mpz_mul(var_mom2,sei,RSA);
mpz_mul(var_mom3,sei,W);
mpz_sub(var_mom2,var_mom2,var_mom3);
mpz_mul(var_mom3,pseudo_a,pseudo_a);
mpz_mul(var_mom3,var_mom3,duecentosedici);
mpz_add(var_mom2,var_mom2,var_mom3);
mpz_mul(var_mom3,settantadue,pseudo_a);
mpz_sub(var_mom2,var_mom2,var_mom3);//termine a
mpz_sub(var_mom3,RSA,W);
mpz_mul(var_mom4,pseudo_a,pseudo_a);
mpz_mul(var_mom4,var_mom4,trentasei);
mpz_add(var_mom3,var_mom3,var_mom4);
mpz_mul(var_mom4,dodici,pseudo_a);
mpz_sub(var_mom3,var_mom3,var_mom4);
mpz_mul(var_mom4,trentasei,G);
mpz_mul(var_mom4,var_mom4,pseudo_a);
mpz_sub(var_mom3,var_mom3,var_mom4);// termine
//mpz_sub(var_mom3,zero,var_mom3);
//risoluzione equazione
mpz_mul(var_mom4,var_mom2,var_mom2);
mpz_mul(var_mom5,quattro,var_mom1);
mpz_mul(var_mom5,var_mom5,var_mom3);
mpz_sub(var_mom4,var_mom4,var_mom5);//sqrt
if(mpz_cmp (var_mom4,zero)>0){//printf("TRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRrr");
mpz_sqrt(var_mom4,var_mom4);//printf("CVVVVVVVVVVVVVVVVVVVVVVVVVv");
mpz_sub(var_mom4,var_mom4,var_mom2);
mpz_mul(var_mom5,due,var_mom1);
mpz_div(var_mom4,var_mom4,var_mom5);
mpz_mul(var_mom4,var_mom4,sei);
mpz_add(var_mom4,var_mom4,uno);
mpz_mod(var_mom5,RSA,var_mom4);
if(mpz_cmp (var_mom5,zero)==0){
mpz_set(*a,var_mom4);
*check=1;
}
}
//gmp_printf ("\n%Zd *a^2 %Zd * a %Zd =0\n",var_mom1,var_mom2,var_mom3);
}
int prendi_numero(char in[]){
char decimale[1000];
int numero_di_cifre_decimali=0;
FILE *fp;
int i=0;
fp = fopen("input.txt", "r");
if (fp==NULL){
printf("\nImpossibile aprire file\n");
system("PAUSE");
exit(1);
}
while(!feof(fp)){
fscanf(fp,"%s",decimale);
}
fclose(fp);
numero_di_cifre_decimali=strlen(decimale)-1;
while(i<=numero_di_cifre_decimali){
in[i]=decimale[i];
i++;
}
return numero_di_cifre_decimali;
}
Non e' comprensibile a una persona che (come me) sa poco o nulla di programmazione.
Io non capisco proprio l'algoritmo che stai cercando di usare. Non lo stai spiegando. Se non fossimo a pagina 4 del thread, sembrerebbe un troll grosso come una casa.
Io non capisco proprio l'algoritmo che stai cercando di usare. Non lo stai spiegando. Se non fossimo a pagina 4 del thread, sembrerebbe un troll grosso come una casa.
scusami pappapero ora ti mostro come si fattorizza in logaritmo
sia $N=p*q$ tutti e tre nella forma $6*h+1$
ti mostro solo il caso in cui $G=(N-1)/6$ è pari
se sostituisci in questo sistema una $n$ inferiore alla $n$ di $x^2+6*n*x=N$
allora $k
allora $k>G$
se sostituisci in questo sistema una $n$ uguale alla $n$ di $x^2+6*n*x=N$
allora $k=G$
il sistema è di quattroequazioni ed è questo:
$A^2-12*A-12*G=2*N-84*n+12*Z-10$
$Z=24+[50*(n/2-1)+24*(n/2-1)*(n/2-2)]$
$K=n+((A-12)+(6*n+8))*a/2 $
$n=(G-6*a^2-2*a)/(6*a+1)$
-----------------------------------------------------------------------------------------------------------------
EDIT
Forse è meglio utilizzare questo sistema
(A-12)*(G+A)-G*A=4+12*[Z+x*(x-1)/6+(6*n+1)*((x-1)/6-1)] ,
Z=24+50*(n/2-1)+(n/2-1)*(n/2-2)*12 ,
x^2+6*n*x=N ,
K=n+((A-12)+(6*n+8))*a/2,
n=(G-6*a^2-2*a)/(6*a+1)
sia $N=p*q$ tutti e tre nella forma $6*h+1$
ti mostro solo il caso in cui $G=(N-1)/6$ è pari
se sostituisci in questo sistema una $n$ inferiore alla $n$ di $x^2+6*n*x=N$
allora $k
allora $k>G$
se sostituisci in questo sistema una $n$ uguale alla $n$ di $x^2+6*n*x=N$
allora $k=G$
il sistema è di quattroequazioni ed è questo:
$A^2-12*A-12*G=2*N-84*n+12*Z-10$
$Z=24+[50*(n/2-1)+24*(n/2-1)*(n/2-2)]$
$K=n+((A-12)+(6*n+8))*a/2 $
$n=(G-6*a^2-2*a)/(6*a+1)$
-----------------------------------------------------------------------------------------------------------------
EDIT
Forse è meglio utilizzare questo sistema
(A-12)*(G+A)-G*A=4+12*[Z+x*(x-1)/6+(6*n+1)*((x-1)/6-1)] ,
Z=24+50*(n/2-1)+(n/2-1)*(n/2-2)*12 ,
x^2+6*n*x=N ,
K=n+((A-12)+(6*n+8))*a/2,
n=(G-6*a^2-2*a)/(6*a+1)
Ti torna che se non dici chi e' $x$ nel quarto, quinto e sesto rigo del tuo post (e non dici chi e' $k$ e che cosa ci fai), quello che scrivi ha poco senso?
Il sistema sotto non ha senso proprio perche' non si sa chi sono $A$, $a$, $Z$ e probabilmente anche qualcos'altro.
Le cose vanno dette in ordine. L'unico post vagamente comprensibile e' quello prima del mio primo post in questo thread.
Il sistema sotto non ha senso proprio perche' non si sa chi sono $A$, $a$, $Z$ e probabilmente anche qualcos'altro.
Le cose vanno dette in ordine. L'unico post vagamente comprensibile e' quello prima del mio primo post in questo thread.
cercherò di spiegarmi meglio (almeno ci provo)
Ennesimo test di fattorizzazione di Lepore in log
Sia N=p*q con N,p e q nella forma 6*h+1
Per capire ci scriviamo una tabella dove i valori cerchiati sono i valori G=(N-1)/6
di questa tabella
cioè questa
i numeri (che chiameremo A) di fianco a due cerchiati sono la differenza dei due numeri cerchiati
si deduce facilmente che n+(8+6*n)*a+6*a*(a-1)=G oppure G= n+((B-12)+(6*n+8))*a/2
dove B=A+12
dove a=(p-1)/6
e n è p^2+6*n*p=N
Osserviamo per G pari (tutti i numeri non divisibili per 2 o 3 sono riconducibili a questo N=p*q con N,p e q nella forma 6*h+1 con G pari)
B^2-12B-36*n^2+-4*N+2+34=0
sotituendo n=(G-6*a^2-2*a)/(6*a+1)
si avrà B^2-12B-36*[(G-6*a^2-2*a)/(6*a+1)]^2+-4*N+2+34=0
scegliendo un a calcoleremo B quindi A=B-12 e prendiamo il primo A nella forma 12*C+8
quindi ci andiamo a calcolare G-A-(A-12)-(A-24)-(A-36).....
fino ad arrivare all'ultimo sottrazione per cui l'espressione è maggiore di zero
se il numero delle sottrazioni è minore dell'a che abbiamo scelto allora dobbiamo scegliere una a superiore
se il numero delle sottrazioni è maggiore dell'a che abbiamo scelto allora dobbiamo scegliere una a inferiore
se il numero delle sottrazioni è uguale all'a che abbiamo scelto allora siamo giunti al termine
esempio N=56653
G=9442
B^2-12*B-36*[(9442-6*a^2-2*a)/(6*a+1)]^2-4*56653+36=0 , a=31 -> B=495,... -> A=476
G-476-464-452-440-428-416...........
hey meglio se lo facciamo così
{[(A-(a-1)*12)+(A)]*a/2+(A-(a-1)*12-8)/6}
{[(476-30*12)+(476)]*31/2+18}=9192
{[(476-31*12)+(476)]*32/2+16}=9294
la nostra a deve scendere
B^2-12*B-36*[(9442-6*a^2-2*a)/(6*a+1)]^2-4*56653+36=0 , a=29 ->B=504,... ->A=488
{[(488-28*12)+(488)]*29/2+24}=9304
{[(488-29*12)+(488)]*30/2+22}=9442==G (possiamo fermarci)
però vediamo il caso a=28
B^2-12*B-36*[(9442-6*a^2-2*a)/(6*a+1)]^2-4*56653+36=0 , a=28 ->B=510 -> A=500
{[(500-27*12)+(500)]*28/2+28}=9492>G
la nostra a deve salire
quindi dovremmo provare per 30 che è il nostro a
------------------------------------------------------------------------------------------
EDIT:
P.s. Quando dobbiamo valutare se scendere o salire la nostra a dobbiamo assicurarci che l'A che stiamo valutando non sia l'A giusta se fosse l'A giusta l'algoritmo termine
-----------------------------------------------------------------------------------------------
EDIT:
P.s.2. dimenticavo una cosa per me ovvia ma per chi legge no
se il valore (A-(a-1)*12)<0 significa che la a scelta deve salire
Ennesimo test di fattorizzazione di Lepore in log
Sia N=p*q con N,p e q nella forma 6*h+1
Per capire ci scriviamo una tabella dove i valori cerchiati sono i valori G=(N-1)/6
di questa tabella
cioè questa
i numeri (che chiameremo A) di fianco a due cerchiati sono la differenza dei due numeri cerchiati
si deduce facilmente che n+(8+6*n)*a+6*a*(a-1)=G oppure G= n+((B-12)+(6*n+8))*a/2
dove B=A+12
dove a=(p-1)/6
e n è p^2+6*n*p=N
Osserviamo per G pari (tutti i numeri non divisibili per 2 o 3 sono riconducibili a questo N=p*q con N,p e q nella forma 6*h+1 con G pari)
B^2-12B-36*n^2+-4*N+2+34=0
sotituendo n=(G-6*a^2-2*a)/(6*a+1)
si avrà B^2-12B-36*[(G-6*a^2-2*a)/(6*a+1)]^2+-4*N+2+34=0
scegliendo un a calcoleremo B quindi A=B-12 e prendiamo il primo A nella forma 12*C+8
quindi ci andiamo a calcolare G-A-(A-12)-(A-24)-(A-36).....
fino ad arrivare all'ultimo sottrazione per cui l'espressione è maggiore di zero
se il numero delle sottrazioni è minore dell'a che abbiamo scelto allora dobbiamo scegliere una a superiore
se il numero delle sottrazioni è maggiore dell'a che abbiamo scelto allora dobbiamo scegliere una a inferiore
se il numero delle sottrazioni è uguale all'a che abbiamo scelto allora siamo giunti al termine
esempio N=56653
G=9442
B^2-12*B-36*[(9442-6*a^2-2*a)/(6*a+1)]^2-4*56653+36=0 , a=31 -> B=495,... -> A=476
G-476-464-452-440-428-416...........
hey meglio se lo facciamo così
{[(A-(a-1)*12)+(A)]*a/2+(A-(a-1)*12-8)/6}
{[(476-30*12)+(476)]*31/2+18}=9192
{[(476-31*12)+(476)]*32/2+16}=9294
la nostra a deve scendere
B^2-12*B-36*[(9442-6*a^2-2*a)/(6*a+1)]^2-4*56653+36=0 , a=29 ->B=504,... ->A=488
{[(488-28*12)+(488)]*29/2+24}=9304
{[(488-29*12)+(488)]*30/2+22}=9442==G (possiamo fermarci)
però vediamo il caso a=28
B^2-12*B-36*[(9442-6*a^2-2*a)/(6*a+1)]^2-4*56653+36=0 , a=28 ->B=510 -> A=500
{[(500-27*12)+(500)]*28/2+28}=9492>G
la nostra a deve salire
quindi dovremmo provare per 30 che è il nostro a
------------------------------------------------------------------------------------------
EDIT:
P.s. Quando dobbiamo valutare se scendere o salire la nostra a dobbiamo assicurarci che l'A che stiamo valutando non sia l'A giusta se fosse l'A giusta l'algoritmo termine
-----------------------------------------------------------------------------------------------
EDIT:
P.s.2. dimenticavo una cosa per me ovvia ma per chi legge no
se il valore (A-(a-1)*12)<0 significa che la a scelta deve salire
fattorizzazione di N=p*q dove N,p,q sono nella forma 6*h+1
con G pari
G=[2*(A+6a-5)-24*(a-2)]*(a-1)/2+[7*(6*(a-(G-6*a^2-2*a)/(6*a+1))+1)-1]/6
(A+12)^2-12*(A+12)-36*[(G-6*a^2-2*a)/(6*a+1)]^2+-4N+2+34=0
G=(N-1)/6
a=(p-1)/6
-----------------------------------------------------------
EDIT
quando non funziona quello di sopra provare
G=[2*(A+6a-5)-24*(a-(G-6*a^2-2*a)/(6*a+1)-2)]*(a-(G-6*a^2-2*a)/(6*a+1)-2)+{{[6*(a-(G-6*a^2-2*a)/(6*a+1))+1]^2}-1}/6
(A+12)^2-12*(A+12)-36*[(G-6*a^2-2*a)/(6*a+1)]^2-4*N+2+34=0
con G pari
G=[2*(A+6a-5)-24*(a-2)]*(a-1)/2+[7*(6*(a-(G-6*a^2-2*a)/(6*a+1))+1)-1]/6
(A+12)^2-12*(A+12)-36*[(G-6*a^2-2*a)/(6*a+1)]^2+-4N+2+34=0
G=(N-1)/6
a=(p-1)/6
-----------------------------------------------------------
EDIT
quando non funziona quello di sopra provare
G=[2*(A+6a-5)-24*(a-(G-6*a^2-2*a)/(6*a+1)-2)]*(a-(G-6*a^2-2*a)/(6*a+1)-2)+{{[6*(a-(G-6*a^2-2*a)/(6*a+1))+1]^2}-1}/6
(A+12)^2-12*(A+12)-36*[(G-6*a^2-2*a)/(6*a+1)]^2-4*N+2+34=0
fattorizzazione di $N=p*q$ dove $N$,$p$,$q$ sono nella forma $6*h+1$
con $G$ pari e $n>4$
$G*(A-12)-(G-A)*A=4+12*{5+(6*n*(n-1)+n-[36+(60+(n/2-4)*24+60 )*(n/2-3)/2])+[(6*n+20)+((6*n+20)+((x-1)/6-3)*12)]*((x-1)/6-2)/2}$
$n=(G-6*a^2-2*a)/(6*a+1)$
$(A+12)^2-12*(A+12)-36*n^2+-4*N+2+34=0$
$G=(N-1)/6$
$a=(p-1)/6$
con $G$ pari e $n>4$
$G*(A-12)-(G-A)*A=4+12*{5+(6*n*(n-1)+n-[36+(60+(n/2-4)*24+60 )*(n/2-3)/2])+[(6*n+20)+((6*n+20)+((x-1)/6-3)*12)]*((x-1)/6-2)/2}$
$n=(G-6*a^2-2*a)/(6*a+1)$
$(A+12)^2-12*(A+12)-36*n^2+-4*N+2+34=0$
$G=(N-1)/6$
$a=(p-1)/6$
Sono piacevolmente sorpreso da questo tentativo (devo dire riuscito) nell'usare finalmente un po' di tex, che rende certamente tutto piu' leggibile.
Se ora spieghi anche che sono questi conti, forse si riesce a capire cosa vuoi fare.
Se ora spieghi anche che sono questi conti, forse si riesce a capire cosa vuoi fare.
Come si usano:
N=56653
A^2-4*56653-36*n^2+72*n+24*(6*a+1)-36=0 , A^2+12*A-36*n^2-4*56653+36=0 , n=2 -> a=38,5.. A=470,... -> a=38 A=464
9442-K= n+(A+(6*n+8))*a/2 , a=38 ,n=2 ,A=464 ->K=244
A+12-K=232
232=n+(2*(6*n+8)+12*(m/2-1))/2*m/2-(m+n) , n=2 -> m=10,5... ->m=12
n=n+m=14
reiteriamo
A^2-4*56653-36*n^2+72*n+24*(6*a+1)-36=0 , A^2+12*A-36*n^2-4*56653+36=0 , n=14 -> a=33,11 A=477,39 -> a=32 A=476
9442-K= n+(A+(6*n+8))*a/2 , a=33 ,n=16 ,A=476 ->K=56
A+12-K=432
432=n+(2*(6*n+8)+12*(m/2-1))/2*m/2-(m+n) , n=14 ->m=8
n=n+m=22 che è la nostra n di p^2+6*n*p=56653
Vi ho fatto vedere il metodo lineare
Ora vediamo quello logaritmico (almeno mi sembra)
supponiamo n=24 (**caso speciale in quanto A=488 che è il nostro A)
A^2-4*56653-36*n^2+72*n+24*(6*a+1)-36=0 , A^2+12*A-36*n^2-4*56653+36=0 , n=24 -> a=29 ,A=488
9442-K= n+(A+(6*n+8))*a/2 , n=24 , a=29 ,A=488 ->K=138
A+12-K=362
362=n+(2*(6*n+8)+12*(m/2-1))/2*m/2-(m+n) , n=24 -> m=4,5 ->m=6
n=n+m=30
reiteriamo
A^2-4*56653-36*n^2+72*n+24*(6*a+1)-36=0 , A^2+12*A-36*n^2-4*56653+36=0 , n=30 ->A=500 ,a=27
9442-K= n+(A+(6*n+8))*a/2 , n=30 , A=500 ,a=27 ->K=124
A+12-K=388
388=n+(2*(6*n+8)+12*(m/2-1))/2*m/2-(m+n) , n=30 ->m=4,03 ->m=6
n=n+m=36
reiteriamo
A^2-4*56653-36*n^2+72*n+24*(6*a+1)-36=0 , A^2+12*A-36*n^2-4*56653+36=0 , n=36 -> A=512 ,a=25
9442-K= n+(A+(6*n+8))*a/2 , n=36 , A=512 ,a=25 ->K=206
Ora osservate i K sono discendenti fino al nostro valore e ascendenti dopo il nostro valore (tranne nel caso speciale).
N=56653
A^2-4*56653-36*n^2+72*n+24*(6*a+1)-36=0 , A^2+12*A-36*n^2-4*56653+36=0 , n=2 -> a=38,5.. A=470,... -> a=38 A=464
9442-K= n+(A+(6*n+8))*a/2 , a=38 ,n=2 ,A=464 ->K=244
A+12-K=232
232=n+(2*(6*n+8)+12*(m/2-1))/2*m/2-(m+n) , n=2 -> m=10,5... ->m=12
n=n+m=14
reiteriamo
A^2-4*56653-36*n^2+72*n+24*(6*a+1)-36=0 , A^2+12*A-36*n^2-4*56653+36=0 , n=14 -> a=33,11 A=477,39 -> a=32 A=476
9442-K= n+(A+(6*n+8))*a/2 , a=33 ,n=16 ,A=476 ->K=56
A+12-K=432
432=n+(2*(6*n+8)+12*(m/2-1))/2*m/2-(m+n) , n=14 ->m=8
n=n+m=22 che è la nostra n di p^2+6*n*p=56653
Vi ho fatto vedere il metodo lineare
Ora vediamo quello logaritmico (almeno mi sembra)
supponiamo n=24 (**caso speciale in quanto A=488 che è il nostro A)
A^2-4*56653-36*n^2+72*n+24*(6*a+1)-36=0 , A^2+12*A-36*n^2-4*56653+36=0 , n=24 -> a=29 ,A=488
9442-K= n+(A+(6*n+8))*a/2 , n=24 , a=29 ,A=488 ->K=138
A+12-K=362
362=n+(2*(6*n+8)+12*(m/2-1))/2*m/2-(m+n) , n=24 -> m=4,5 ->m=6
n=n+m=30
reiteriamo
A^2-4*56653-36*n^2+72*n+24*(6*a+1)-36=0 , A^2+12*A-36*n^2-4*56653+36=0 , n=30 ->A=500 ,a=27
9442-K= n+(A+(6*n+8))*a/2 , n=30 , A=500 ,a=27 ->K=124
A+12-K=388
388=n+(2*(6*n+8)+12*(m/2-1))/2*m/2-(m+n) , n=30 ->m=4,03 ->m=6
n=n+m=36
reiteriamo
A^2-4*56653-36*n^2+72*n+24*(6*a+1)-36=0 , A^2+12*A-36*n^2-4*56653+36=0 , n=36 -> A=512 ,a=25
9442-K= n+(A+(6*n+8))*a/2 , n=36 , A=512 ,a=25 ->K=206
Ora osservate i K sono discendenti fino al nostro valore e ascendenti dopo il nostro valore (tranne nel caso speciale).
Fattorizzazione in tempi logaritmici (se funziona)
N numero prodotto di due primi che siano nella forma 6*h+1 con h naturale
che chiameremo p e q cioè p*q=N
Ogni numro N di questo tipo si può scrivere nella forma 6*H+1
con H naturale
Sia G=(N-1)/6
allora G si scrive in questa forma [ora non mi so spiegare bene quindi ti mostrerò mezzo esempio e mezza teoria]
Se p=6*a+1=31 ad esempio
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=G
dove 30=6*a e x-3*n=6*a+1=p dove n =[(x-(6*a+1-6))+(x-(6*a+1))-8]/6=[(x-24)+(x-30)-8]/6
quindi mi sembra se non sbaglio qualcosa che dovrebbe essere questa
x+2*(a-1)*x-(6*(a-1)*a)+(x-6*a)+(x-(6*a+1))/3=G [non ne sono sicuro ma questo non è importante perchè con un po di attenzione si trova]
quindi per N=1705 ad esempio si avrà
43+2*37+2*31+2*25+2*19+13+4=284
Si deve notare una cosa che
se scegliamo un numero iniziale maggiore di 43 la potenziale a è minore della vera a se non si vuole superare il 284
se scegliamo un numero iniziale minore di 43 la potenziale a è maggiore della vera a se non si vuole superare il 284
Scegliendo 6*a=30 si ha p=31 quindi a=5
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=284
quindi x=43 e n=4 43-3*4=31
Scegliendo 6*a=24 si ha p=25 quindi a=4
x+2*(x-6)+2*(x-12)+2*(x-18)+(x-24)+[(x-18)+(x-24)-8]/6=284
quindi x=233/5=46,6 e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 43
43+2*37+2*31+2*25+19+6= 254 quindi per arrivare a 284 dovrebbe crescere la a
Scegliendo 6*a=18 si ha p=19 quindi a=3
x+2*(x-6)+2*(x-12)+(x-18)+[(x-12)+(x-18)-8]/6=284
quindi x=1033/19=54,... e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 49
49+2*43+2*37+31+10= 250 quindi per arrivare a 284 dovrebbe crescere la a
(questo caso lo mostro per completezza in quanto 43 > sqrt(1705) )
Scegliendo 6*a=42
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+2*(x-36)+(x-42)+[(x-36)+(x-42)-8]/6=284
quindi x=1777/43=41,... quindi 37 segue n negativa quindi la a deve diminuire
Scegliendo 6*a=36 si ha p=37 quindi a=6
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+(x-36)+[(x-30)+(x-36)-8]/6=284
quindi x=1537/37=41,... e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 37
37+2*31+2*25+2*19+2*13+2*7+1+0=228 quindi per arrivare a 284 dovrebbe crescere la a ma la a non può crescere quindi di conseguenza deve crescere il 37 ma per far crescere il 37 la a deve diminuire
potrebbe verificarsi altri due casi
guardiamo questa sequenza senza pensare più a quello di prima
43+2*37+2*31+2*25+19+6=254
se il 43 è più basso del valore reale e la potenziale a non è maggiore della vera a quindi a deve salire
e poi c'è questo caso qui
se il 43 è più basso del valore reale e la potenziale a è maggiore della vera a quindi a DOVREBBE SCENDERE ma non ho capito perchè?
Speranzoso in un vostro aiuto cordialmente vi saluto
N numero prodotto di due primi che siano nella forma 6*h+1 con h naturale
che chiameremo p e q cioè p*q=N
Ogni numro N di questo tipo si può scrivere nella forma 6*H+1
con H naturale
Sia G=(N-1)/6
allora G si scrive in questa forma [ora non mi so spiegare bene quindi ti mostrerò mezzo esempio e mezza teoria]
Se p=6*a+1=31 ad esempio
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=G
dove 30=6*a e x-3*n=6*a+1=p dove n =[(x-(6*a+1-6))+(x-(6*a+1))-8]/6=[(x-24)+(x-30)-8]/6
quindi mi sembra se non sbaglio qualcosa che dovrebbe essere questa
x+2*(a-1)*x-(6*(a-1)*a)+(x-6*a)+(x-(6*a+1))/3=G [non ne sono sicuro ma questo non è importante perchè con un po di attenzione si trova]
quindi per N=1705 ad esempio si avrà
43+2*37+2*31+2*25+2*19+13+4=284
Si deve notare una cosa che
se scegliamo un numero iniziale maggiore di 43 la potenziale a è minore della vera a se non si vuole superare il 284
se scegliamo un numero iniziale minore di 43 la potenziale a è maggiore della vera a se non si vuole superare il 284
Scegliendo 6*a=30 si ha p=31 quindi a=5
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=284
quindi x=43 e n=4 43-3*4=31
Scegliendo 6*a=24 si ha p=25 quindi a=4
x+2*(x-6)+2*(x-12)+2*(x-18)+(x-24)+[(x-18)+(x-24)-8]/6=284
quindi x=233/5=46,6 e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 43
43+2*37+2*31+2*25+19+6= 254 quindi per arrivare a 284 dovrebbe crescere la a
Scegliendo 6*a=18 si ha p=19 quindi a=3
x+2*(x-6)+2*(x-12)+(x-18)+[(x-12)+(x-18)-8]/6=284
quindi x=1033/19=54,... e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 49
49+2*43+2*37+31+10= 250 quindi per arrivare a 284 dovrebbe crescere la a
(questo caso lo mostro per completezza in quanto 43 > sqrt(1705) )
Scegliendo 6*a=42
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+2*(x-36)+(x-42)+[(x-36)+(x-42)-8]/6=284
quindi x=1777/43=41,... quindi 37 segue n negativa quindi la a deve diminuire
Scegliendo 6*a=36 si ha p=37 quindi a=6
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+(x-36)+[(x-30)+(x-36)-8]/6=284
quindi x=1537/37=41,... e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 37
37+2*31+2*25+2*19+2*13+2*7+1+0=228 quindi per arrivare a 284 dovrebbe crescere la a ma la a non può crescere quindi di conseguenza deve crescere il 37 ma per far crescere il 37 la a deve diminuire
potrebbe verificarsi altri due casi
guardiamo questa sequenza senza pensare più a quello di prima
43+2*37+2*31+2*25+19+6=254
se il 43 è più basso del valore reale e la potenziale a non è maggiore della vera a quindi a deve salire
e poi c'è questo caso qui
se il 43 è più basso del valore reale e la potenziale a è maggiore della vera a quindi a DOVREBBE SCENDERE ma non ho capito perchè?
Speranzoso in un vostro aiuto cordialmente vi saluto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo