Algoritmi sui numeri primi.
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
L'ho corretto e semplificato
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
Ultima modifica di P_1_6 il sabato 26 novembre 2016, 16:21, modificato 1 volta in totale.
Re: Algoritmi sui numeri primi.
A me non se ne apre nemmeno uno.
Edit: come non detto. Mi metteva questa discussione nei "messaggi senza risposta" e vedevo solo il primo post.
Edit: come non detto. Mi metteva questa discussione nei "messaggi senza risposta" e vedevo solo il primo post.
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
Dovrebbe essere una questione di parentesi
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
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
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
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
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
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]
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
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
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
Qualcuno con un computer decente lo potrebbe provare a me da
GNU MP: Cannot allocate memory (size=4)
Annullato (core dump creato)
l'RSA va in input.txt
ho usato gmp 6.1.1
GNU MP: Cannot allocate memory (size=4)
Annullato (core dump creato)
l'RSA va in input.txt
ho usato gmp 6.1.1
Codice: Seleziona tutto
#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,dodici,quattro,a,venticinque,alpha,secinque,cinque;
mpz_init(RSA);
char numero_RSA[10000];/*set this value*/
prendi_numero(numero_RSA);
mpz_init_set_str (RSA, numero_RSA, 10);
//inizio
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_set_str (dodici, "12", 10);
mpz_init_set_str (quattro, "4", 10);
mpz_init(a);
mpz_init(alpha);
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_mom2,dodici,dodici);
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,dodici);
mpz_div(var_mom2,var_mom2,due);
gmp_printf ("\n\n\n\n\n\nA=%Zd \n\n\n\n\n",var_mom2);
mpz_div(var_mom2,var_mom2,sei);
mpz_mul(var_mom2,var_mom2,sei);
mpz_add(alpha,var_mom2,uno);//31
mpz_sub(alpha,alpha,dodici);
while(check!=1){
mpz_add(alpha,alpha,sei);
mpz_add(var_mom3,alpha,dodici);//43
mpz_mul(var_mom2,alpha,var_mom3);//31*43
mpz_sub(var_mom4,var_mom3,sei);//37
mpz_add(var_mom3,var_mom4,dodici);//49
mpz_mul(var_mom3,var_mom3,var_mom4);//37*49
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\n");
}
}
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;
}
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
l'ho modificato
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)
Codice: Seleziona tutto
#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;
}
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
OK credo sia arrivato il momento
Sia N=p*q tutti e tre nella forma 6*h+1
Se G=(N-1)/6 è pari
allora si risolve il sistema
x^2+6*n*x=N
(x-6)^2+6*(n+2)*(x-6)=6*(G-(13*n/2+(x-1)/6))+1
Se G=(N-1)/6 è dispari
allora si risolve il sistema
x^2+6*n*x=N
(x-6)^2+6*(n+2)=6*(G-(n-2)*12)+1
tutto ciò se x!= 7
@Zoff
Sia N=p*q tutti e tre nella forma 6*h+1
Se G=(N-1)/6 è pari
allora si risolve il sistema
x^2+6*n*x=N
(x-6)^2+6*(n+2)*(x-6)=6*(G-(13*n/2+(x-1)/6))+1
Se G=(N-1)/6 è dispari
allora si risolve il sistema
x^2+6*n*x=N
(x-6)^2+6*(n+2)=6*(G-(n-2)*12)+1
tutto ciò se x!= 7
@Zoff
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
ora vi 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<G
se sostituisci in questo sistema una n maggiore alla n di x^2+6*n*x=N
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<G
se sostituisci in questo sistema una n maggiore alla n di x^2+6*n*x=N
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)
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
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
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<G
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
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<G
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
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
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
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
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
@Zoff
scusatemi se sbaglio
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
@Zoff
scusatemi se sbaglio
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
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).
- noel80
- Entusiasta Emergente
- Messaggi: 2240
- Iscrizione: giovedì 11 settembre 2014, 2:49
- Desktop: Gnome w/Tile || KDE
- Distribuzione: Pop!_OS || SteamOS
Re: Algoritmi sui numeri primi.
2017 is not just another prime number : non sapevo dell'esistenza dei sexy prime .
- ubuntumate
- Entusiasta Emergente
- Messaggi: 1180
- Iscrizione: giovedì 28 maggio 2015, 18:18
- Distribuzione: Windows 7
- Sesso: Maschile
- Località: Milano
Re: Algoritmi sui numeri primi.
Buoni, non stuzzicatelo
Software engineers shall participate in lifelong learning regarding the practice of their profession and shall promote an ethical approach to the practice of the profession.
ACM/IEEE Code of ethics.
ACM/IEEE Code of ethics.
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
Quest'inverno ho bruciato nella stufa tutti i miei appunti cartacei
e in questi giorni rivedendo le ultime cose avevo fatto mi è rimasto questo
vedete se vi può essere utile
Sia N=p*q con p e q numeri primi diversi da 2 e 3 dove p=6*a+1 e q=6*b+1 con a e b numeri naturali e con N=6*G+1 dove G è un numero naturale pari
e con x=6*a+1+3*n ecc.ecc.
si ha
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+(x-31)/3=284
che tradotto
x+2*(a-1)*x-(6*(a-1)*a)+(x-6*a)+(x-(6*a+1))/3=284
284-[x^2-(x-6)^2]/6-[[x^2-(x-6)^2]/6-12]-[[x^2-(x-6)^2]/6-24]-[[x^2-(x-6)^2]/6-36]-[[x^2-(x-6)^2]/6-48]-(x-6*a-1)/3=0
e per eliminare la a si ha
284-[x^2-(x-6)^2]/6-[[x^2-(x-6)^2]/6-12]-[[x^2-(x-6)^2]/6-24]-[[x^2-(x-6)^2]/6-36]-[[x^2-(x-6)^2]/6-48]-[[[x^2-(x-6)^2]/6-48]-8]/6=0
che tradotto
284-a*[x^2-(x-6)^2]/6+(6*a*(a-1))-(x-6*a-1)/3=0
dove la famosa n di p^2+6*n*p=N è n=(x-(6*a+1))/3
spero di non aver commesso errori
e in questi giorni rivedendo le ultime cose avevo fatto mi è rimasto questo
vedete se vi può essere utile
Sia N=p*q con p e q numeri primi diversi da 2 e 3 dove p=6*a+1 e q=6*b+1 con a e b numeri naturali e con N=6*G+1 dove G è un numero naturale pari
e con x=6*a+1+3*n ecc.ecc.
si ha
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+(x-31)/3=284
che tradotto
x+2*(a-1)*x-(6*(a-1)*a)+(x-6*a)+(x-(6*a+1))/3=284
284-[x^2-(x-6)^2]/6-[[x^2-(x-6)^2]/6-12]-[[x^2-(x-6)^2]/6-24]-[[x^2-(x-6)^2]/6-36]-[[x^2-(x-6)^2]/6-48]-(x-6*a-1)/3=0
e per eliminare la a si ha
284-[x^2-(x-6)^2]/6-[[x^2-(x-6)^2]/6-12]-[[x^2-(x-6)^2]/6-24]-[[x^2-(x-6)^2]/6-36]-[[x^2-(x-6)^2]/6-48]-[[[x^2-(x-6)^2]/6-48]-8]/6=0
che tradotto
284-a*[x^2-(x-6)^2]/6+(6*a*(a-1))-(x-6*a-1)/3=0
dove la famosa n di p^2+6*n*p=N è n=(x-(6*a+1))/3
spero di non aver commesso errori
- federyco68
- Prode Principiante
- Messaggi: 156
- Iscrizione: domenica 5 giugno 2016, 10:39
- Desktop: linux mint mate 19.2 tina
- Distribuzione: Ubuntu 18.04.4 LTS Gnome
- Sesso: Maschile
- Località: castel volturno
Re: Algoritmi sui numeri primi.
che lingua èèèèè!!!!!!!!!!!!!!P_1_6 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4969830#p4969830][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Quest'inverno ho bruciato nella stufa tutti i miei appunti cartacei
e in questi giorni rivedendo le ultime cose avevo fatto mi è rimasto questo
vedete se vi può essere utile
Sia N=p*q con p e q numeri primi diversi da 2 e 3 dove p=6*a+1 e q=6*b+1 con a e b numeri naturali e con N=6*G+1 dove G è un numero naturale pari
e con x=6*a+1+3*n ecc.ecc.
si ha
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+(x-31)/3=284
che tradotto
x+2*(a-1)*x-(6*(a-1)*a)+(x-6*a)+(x-(6*a+1))/3=284
284-[x^2-(x-6)^2]/6-[[x^2-(x-6)^2]/6-12]-[[x^2-(x-6)^2]/6-24]-[[x^2-(x-6)^2]/6-36]-[[x^2-(x-6)^2]/6-48]-(x-6*a-1)/3=0
e per eliminare la a si ha
284-[x^2-(x-6)^2]/6-[[x^2-(x-6)^2]/6-12]-[[x^2-(x-6)^2]/6-24]-[[x^2-(x-6)^2]/6-36]-[[x^2-(x-6)^2]/6-48]-[[[x^2-(x-6)^2]/6-48]-8]/6=0
che tradotto
284-a*[x^2-(x-6)^2]/6+(6*a*(a-1))-(x-6*a-1)/3=0
dove la famosa n di p^2+6*n*p=N è n=(x-(6*a+1))/3
spero di non aver commesso errori
Calma... ci troviamo in una finestra "insignificabile" rispetto all 'immensità temporale .
Difficilmente replicabile . (Federico Minieri)
Difficilmente replicabile . (Federico Minieri)
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
in effetti manca per N=1705 e G=284
-
- Prode Principiante
- Messaggi: 20
- Iscrizione: giovedì 25 dicembre 2014, 23:01
- Distribuzione: Ubuntu 15.10 i686
Re: Algoritmi sui numeri primi.
Lo so che molti di voi ci sono arrivati.
Io continuo per chi ha bisogno di ulteriori informazioni.
Prendiamo ad esempio il numero N=1705 quindi G=284
che si scrive così
43+2*37+2*31+2*25+2*19+13+4=284
dove 4=[(19+13)-8]/6
e dove 43-13=6*a
Una soluzione è in log * log dando i valori ad a e considerando il 284.
Io continuo per chi ha bisogno di ulteriori informazioni.
Prendiamo ad esempio il numero N=1705 quindi G=284
che si scrive così
43+2*37+2*31+2*25+2*19+13+4=284
dove 4=[(19+13)-8]/6
e dove 43-13=6*a
Una soluzione è in log * log dando i valori ad a e considerando il 284.
Chi c’è in linea
Visualizzano questa sezione: 0 utenti iscritti e 17 ospiti