Algoritmi sui numeri primi.

[P_1_6]

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

[bingel]

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.

[P_1_6]

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

[P_1_6]

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

[P_1_6]

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]

[P_1_6]

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

[P_1_6]

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

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;
}

[P_1_6]

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)

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;
}

[P_1_6]

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

[P_1_6]

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)

[P_1_6]

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

[P_1_6]

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

[P_1_6]

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

[P_1_6]

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).

[noel80]

2017 is not just another prime number : non sapevo dell'esistenza dei sexy prime .

[ubuntumate]

Buoni, non stuzzicatelo

[P_1_6]

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

[federyco68]

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

che lingua èèèèè!!!!!!!!!!!!!!

[P_1_6]

in effetti manca per N=1705 e G=284

[P_1_6]

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.