Raúl Merino on Fri, 30 Dec 2005 00:22:29 +0100

 FW: Problems programming C and pari together

```

Hi!
I try to make a program to compute primes between 2^508 and 2^512.
To do it, i use c with pari.
I have a problem when i do the next comparasion:

while(itos(geq((GEN) primers[a], stoi(0)))==1);

In theory (I don't know if i make it good) primers[a] is a vector. I
use the function cgetg to get memory for the variable primers[a].

I put all the program in the newt sentences and then i put the
program in the language for the calculator gp.
The problem is in the function construccio_primers.

#include<stdio.h
#include<math.h
#include<stdlib.h
#include <process.h
#include "pari.h"

void fdescomposicio(int min_bits, int epsi);

void construccio_primers(int minbits, int maxposlongitud, int
nombrepgrans);
int comprovar_primeritat (int L, int f, GEN aux_pari);

int nombrepgrans, maxposlloc, maxd, f;
int descomposicio[100];
int *llocprimers;
GEN p, primers, v;

int main (void)
{
int epsi, minbits;

srand (getpid());
pari_init(32000000, 30000);

printf("Aquest programa dona claus de 512 bits.\n");
printf("A partir de quin valor vols comprovar si un nombre es
primer?\n");
scanf("%d",&minbits);
printf("Per calcular un primer li restes un epsilon i, despres, el
factoritzem en primers petits.\n");
printf("Quin epsilon (enter i positiu) vols agafar?\n");
scanf("%d", &epsi);

fdescomposicio(minbits, epsi);

construccio_primers(minbits, maxd, nombrepgrans);

return 0;

}

void fdescomposicio(int minbits, int epsi)
{
int k, s, j, i, repetit, longitud;
int auxllocprimers[100];

for(k=0; k<100; k++)	descomposicio[k]=0;
for(k=0; k<100; k++)	auxllocprimers[k]=0;
descomposicio[0]=500;
s=0;
i=1;

for(k=0;k<100; k++)
{
if(descomposicio[k]minbits)
{
longitud=descomposicio[k]-epsi;

while(longitudminbits)
{
descomposicio[i]=rand()%(longitud-1)+1;
longitud=longitud-descomposicio[i];
i++;
}

descomposicio[i]=longitud;
i++;
}

repetit=0;
for(j=0; j<100; j++)
{
if(auxllocprimers[j]==i)	repetit=1;
}

if(repetit==0)
{
auxllocprimers[s]=i;
s++;
}
}

maxd=0;
nombrepgrans=0;
maxposlloc=0;

for(k=0;k<100; k++)
{
if(descomposicio[k]!=0)	maxd++;
if(descomposicio[k]minbits)	nombrepgrans++;
}

for(k=0; k<100; k++)
{
if(auxllocprimers[k]!=0)	maxposlloc++;
}

llocprimers =(int *)calloc(maxposlloc+1, sizeof(int));

for(k=0; k<maxposlloc;k++)
{
llocprimers[k]=auxllocprimers[maxposlloc-k-1];
}

printf("Descomposicio\n");
for(k=0; k<maxd; k++)	printf("%d\t",descomposicio[k]);
printf("\n\nlloc dels primers\n");
//llocprimers[maxposlloc-1]=2;
for(k=0; k<maxposlloc; k++)	printf("%d\t", llocprimers[k]);
printf("\n\n");
printf("nombrepgrans = %d\n", nombrepgrans);
printf("max = %d\n", maxd);

return;
}

void construccio_primers(int minbits, int maxposlongitud, int
nombrepgrans)
{
int L, control, posicio_aux, controlgrans, elevado_aux,
control_primeritat;
int a, k, q, var, j, r;

//reservem memòria per les variables del PARI
aux_pari=cgeti(DEFAULTPREC);
p=cgeti(BITS_IN_LONG);
j_aux=cgeti(BITS_IN_LONG);
min_bits=cgeti(DEFAULTPREC);
primers=cgetg(100, t_INT);
for(k=1; k<100; k++)	primers[k]=lgeti(BITS_IN_LONG);
aux_pari=stoi((long) 2);
min_bits=stoi((long) min_bits);

//primers is a vector who have components <=2^512
//p is a integer <2^512

f=1;
control=(int) f;
for(a=0; a<=maxposlloc-2; a++)
{

if(a!=1)	maxposlongitud=posicio_aux;

while(itos(geq((GEN) primers[a], stoi(0)))==1);
{
posicio_aux=maxposlongitud;
control=f;
L=llocprimers[a]-llocprimers[a+1] + 1;
v = cgetg(L+1, t_INT);
for(k=1; k<L+1; k++)	v[k]=lgeti(BITS_IN_LONG);

for(r=1; r<=L-1; r++)
{
//if(equalui((long) descomposicio[posicio_aux],(GEN)
min_bits)<=0)
if(itos(glt(stoi(descomposicio[posicio_aux]),(GEN)
min_bits))==1)
{
elevado = (GEN) gpowgs((GEN) aux_pari, (long)
descomposicio[posicio_aux]);
}
//if(absi_cmp(stoi((long) descomposicio[posicio_aux]),(GEN)
min_bits)0)
if(itos(ggt(stoi(descomposicio[posicio_aux]), (GEN)
min_bits))==1)
{
for(q=1; q<=posicio_aux; q++)
{
if(absi_cmp(stoi((long)descomposicio[q]),(GEN) min_bits)0)
{
controlgrans++;
}
}

var= nombrepgrans-controlgrans+1;
gaffect((GEN) v[r], (GEN) primers[var]);
controlgrans=0;
}

posicio_aux --;
}

for(j=64; j<=16384;j++)
{
j_aux=stoi((long) j);
if(f==control)
{
gaffect((GEN) v[L], (GEN)nextprime(j_aux));
gaffect((GEN) j, (GEN) v[L]);
gaffsg((long) 2, (GEN) p);

for(k=1; k<=L; k++)		gaffect((GEN) p, (GEN) gmul((GEN) p,(GEN)
v[k]));
control_primeritat=comprovar_primeritat (L, f, aux_pari);
if(control_primeritat==1)	 printf("p és = %s", GENtostr(p));
}
}
}*/
}

return;

}

void construccio_primers(GEN descomposicio, GEN llocprimers, int
minbits, int maxposlloc, int maxposlongitud, int nombrepgrans)
{
int L, control, posicio_aux, controlgrans;
int a, k, q, var, j, r;
GEN primers, v, elevado, aux_pari, min_bits, p, j_aux;
pari_init(32000000, 30000);
aux_pari=cgeti((long) 10);
p=cgeti((long) 100);
j_aux=cgeti((long) 100);
min_bits=cgeti((long) 10);
primers=cgetg(100, t_INT);
for(k=1; k<100; k++)	primers[k]=lgeti((long) 100);
aux_pari=stoi((long) 2);
min_bits=stoi((long) min_bits);
BITS_IN_LONG

f=1;
control=(int) f;
for(a=0; a<=maxposlloc-2; a++)
{
if(a!=1)	maxposlongitud=posicio_aux;

while((int) equalis(primers[a], (long) 0)==0)
{
posicio_aux=maxposlongitud;
control=f;
L=llocprimers[a]-llocprimers[a+1] + 1;
v = cgetg(L+1, t_INT);
for(k=1; k<L+1; k++)	v[k]=lgeti((long) 100);

for(r=1; r<=L-1; r++)
{
if(absi_cmp((GEN)descomposicio[posicio_aux],(GEN) min_bits)<=0)
{
```
elevado = (GEN) gpowgi((GEN) aux_pari, (GEN) descomposicio[posicio_aux]);
```					gaddz((GEN) randomi(elevado),(GEN) elevado,(GEN) v[r]);
}
if(absi_cmp((GEN)descomposicio[posicio_aux],(GEN) min_bits)0)
{
for(q=1; q<=posicio_aux; q++)
{
if(absi_cmp((GEN)descomposicio[q],(GEN) min_bits)0)
{
controlgrans++;
}
}

var= nombrepgrans-controlgrans+1;
gaffect((GEN) v[r], (GEN) primers[var]);
controlgrans=0;
}

posicio_aux --;
}

for(j=64; j<=16384;j++)
{
j_aux=stoi((long) j);
if(f==control)
{
gaffect((GEN) v[L], (GEN)nextprime(j_aux));
gaffect((GEN) j, (GEN) v[L]);
gaffsg((long) 2, (GEN) p);

for(k=1; k<=L; k++)		gaffect((GEN) p, (GEN) gmul((GEN) p,(GEN) v[k]));
comprovar_primeritat(p, primers, v, L, f, aux_pari);
}
}
}
}

return;

}

int comprovar_primeritat (int L, int f, GEN aux_pari)
{
//g, aux son punteros
//f,v son punteros que estaran en este programa y en el principal
int i, t, repetit, z;
GEN g, aux, aux_pari2, aux_pari3;

//reservem memoria per g i aux
g=cgeti((long) 100);
aux=cgeti((long) 100);
aux_pari2=cgeti((long) 10);
aux_pari3=cgeti((long) 10);
aux_pari2=stoi((long) -1);
aux_pari3=stoi((long) 1);

//isprime segun manual user's, no existe en libpari.pdf
if(isprime((GEN) p) == 1)
{
i=0;
while(i<15)
{
gaffect((GEN) stoi((long) (rand()%(itos(p)-3))+2), (GEN) g);
gaffect((GEN) aux, (GEN) gmodulcp(g,p));
gaffect((GEN) aux, (GEN) gpow((GEN) aux,(GEN) gdivexact((GEN)
gaddgs((GEN) p, (long) -1), (GEN) aux_pari), (long) 1));

if(itos(geq((GEN) aux, (GEN) gmodulcp(aux_pari2,p)))==1)
{
t=1;
while(itos(geq((GEN) aux, (GEN) gmodulcp(aux_pari3,p)))==0)
{
gaffect((GEN) aux, (GEN) gmodulcp((GEN) g,(GEN) p));
```
gaffect((GEN) aux, (GEN) gpow((GEN) aux,(GEN) gdivexact((GEN)gaddgs((GEN)p,(long)-1), (GEN) v[t]), (long) 1));
```					t++;
if(t==L+1 && itos(geq((GEN) aux, (GEN) gmodulcp(aux_pari3,p)))==0)
{
repetit=0;
for(z=1; z<=f; z++)
{
if(itos(geq((GEN) p, (GEN) primers[z]))==1)
{
repetit=1;
}
}

if(repetit==0)
{
gaffect((GEN) primers[f], (GEN) p);
f++;
return 1;
}

break;
}
}

if(t==L+1)	break;
}
i++;
}
}

return 0;
}

The program for the calculator is:
f=1;
cota_inf=2^508;
cota_sup=cota_inf*16;
min_bits= 25;
epsilon=10;
posmaxveclong=0;
maxposveclloc=0;
nombrepgrans=0;
controlgrans=0;
vectorlongitud=vector(100);
auxprimers=vector(100);
primers=vector(100);
s=1;
vectorlongitud[1]=500;
i=2;
for(k=1, 100,
if(vectorlongitud[k]25,longitud=vectorlongitud[k]-epsilon;while(longitudmin_bits,
vectorlongitud[i]=random(longitud-1)+1;
longitud=longitud-vectorlongitud[i];
i++);vectorlongitud[i]=longitud;i++);repetit=0;for(j=1,100,
if(auxprimers[j]==i,repetit=1)); if(repetit==0,
auxprimers[s]=i;s++))
for(k=1,100, if(vectorlongitud[k]!=0, posmaxveclong ++);
if(vectorlongitud[k]min_bits, nombrepgrans++));
for(k=1,100, if(auxprimers[k]!=0, maxposveclloc ++));
llocprimers=vector(maxposveclloc);
for(k=1,maxposveclloc,
llocprimers[k]=auxprimers[maxposveclloc+1-k]);
maxl=posmaxveclong;
control=f;
posaux, if(vectorlongitud[q]min_bits,
controlgrans++));var=nombrepgrans-controlgrans+1;
v[r]=primers[var];controlgrans=0);posaux--);for(j=2^6,
2^14,if(f==control, v[L]=nextprime(j); j=v[L]; p=2; for(k=1, L,
p=p*v[k]); p++; if(isprime(p)==1,i=0;while(i<15,
g=random(p-3)+2;aux=Mod(g,p)^((p-1)/2);
if(aux==Mod(-1,p),t=1;while(aux!=Mod(1,p),aux=Mod(g,p)^((p-1)/v[t]);
t++; if(t==L+1&&aux!= Mod(1,p),repetit=0;for(z=1, f,
if(p==primers[z],
repetit=1));if(repetit==0,primers[f]=p;f++);break));if(t==L+1,break));
i++))))));

If somebody see some mistake, please tell me.

Thanks.

Ra.

_________________________________________________________________
```
Dale rienda suelta a tu tiempo libre. Encuentra mil ideas para exprimir tu ocio con MSN Entretenimiento. http://entretenimiento.msn.es/
```
```