Re: Proving primality of an integer

From: Cristiano (cristiano.pi@nsquipo.it)
Date: 02/09/03 

From: "Cristiano" <cristiano.pi@nsquipo.it>
Date: Sun, 09 Feb 2003 11:24:39 GMT

Aldo wrote:
>
> The reader can download Ubasic interpreter from the Internet, or
> translate the program into C.

Very good! Your implementation is very fast.

Just a question: if your program say "N is prime", N is really prime
without any doubt?

This is my translation in c++ for miracl (N.get_bit() is not included in
the miracl library):

// -------------------------
// (S(x)*S(x)) % (x^r-1) % n
// -------------------------
void S_x_S(Big *S,Big *T,const int R,Big &N)
{
 for(int i=0;i<=R;i++) { S[i]=T[i]; T[i]=0; }

 for(int i=0;i<R;i++)
  for(int j=0;j<R;j++) {
   int k=(i+j)%R; T[k]=(T[k]+S[i]*S[j])%N;
  }
}

// -------------------------
// (S(x)*A(x)) % (x^r-1) % n
// -------------------------
void S_x_A(Big *S,Big *T,const int R,int *A,Big &N)
{
 for(int i=0;i<=R;i++) { S[i]=T[i]; T[i]=0; }

 for(int i=0;i<R;i++)
  for(int j=0;j<=1;j++) {
   int k=(i+j)%R; T[k]=(T[k]+S[i]*A[j])%N;
  }
}

int AKS(Big &N)
{
 int R=2,K=N%R;
 while(K*K%R==1) { R++; K=N%R; }

 if(K==0) return 0; // N is divisible by R

 Big *S=new Big[R+1],*T=new Big[R+1];
 int A[2]={-1,1}; // A = x-1

 T[0]=-1; T[1]=1;

 // Mod exp: (x-1)^n (mod x^r-1, n)
 // -------------------------------
 int I=bits(N)-2;
 while (I>=0) {
  S_x_S(S,T,R,N); // (S*S)%(x^r-1)%n
  if(N.get_bit(I)) S_x_A(S,T,R,A,N); // (S*A)@(x^r-1)@n
  I--;
 }

 // Normalization as in UBASIC
 for(int i=0;i<=R;i++) if(T[i]<0) T[i]+=N;

 // -----------
 // Test result
 // -----------

 for(int i=0;i<=R;i++) S[i]=0;
 S[K]=1; S[0]=N-1;

 I=0; while (I<R && S[I]==T[I]) I++;

 delete[] S; delete[] T;

 if(I==R) return 1; // N is prime
 return 0; // N is composite
}

Cristiano

Relevant Pages

  • Re: Proving primality of an integer
    ... >> The reader can download Ubasic interpreter from the Internet, ... >> translate the program into C. ...
    (sci.crypt)
  • Re: Array of indices
    ... > thing is to translate it to C... ... But it is nowhere close to be translateable into a programming language. ... After that whole thing finished all array elements ... int FindLargest(float A, int NrElements) ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Reading C code in matlab... mex file?
    ... translate" The following from c: ... 'int nKernels' */ ... FLOAT32 Offset, dTheta_i, dTheta_j; ...
    (comp.soft-sys.matlab)
  • Re: help understanding assignment with post increment operator
    ... > until after the assignment has taken place, but to my mind the line ... Hi Rob, ... int x = 0; ... it would translate to something like this: ...
    (comp.lang.java.help)
  • Re: SML please for translation
    ... you translate me this program: ... type var = string; ... N of int ...
    (comp.lang.ml)