Test di primalità e fattorizzazione di Lepore

[Pappappero]

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.

[P_1_6]

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)

Codice:


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



[Pappappero]

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.

[P_1_6]

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

[Pappappero]

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.

[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 (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<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$


$a=(p-1)/6$

[Pappappero]

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.

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