c modular exponentiation right to left

[johninio]

Όντως εχεις δικιο σε αυτο.Αυριο που θα ασχοληθω θα τον καθαρογραψω και θα τον postαρω .Ελπιζω να με βοηθησετε να βρω τα λαθη μου.

main()

{

int i,j,sum,a,p,n,k,sum1,s;

long curtime;

    double sttime,endtime;

    printf("Checking range [%d,%d]\n",MINNUM,MAXNUM);

    curtime = time(NULL);

srand(1414258936);

  printf("Trying Fermat test with seed %ld\n",curtime); 

  for(i=1; i<=MAXTRIES; i++){

  sttime= ((double) clock ()) /CLOCKS_PER_SEC; 

  sum=0;

 for (p=MINNUM; p<=MAXNUM; p=p+1){

  sum1=0;

 for(j=1; j<=i; j++){

  if((p-1)%2==0){

   n=(p-1)/2;

   a = rand() % (p-1) + 1 ;

   s=a;

 while(n!=0){

  long long k=(s*s)%p;

  long long s=k;

  n=n/2;}

    k=k%p;

  

  }

  else{

  n=(p-2)/2;

  a = rand() % (p-1) + 1 ;

  s=a;

  while(n!=0){

  long long k=(s*s)%p;

  long long s=k;

  n=n/2;}

  k=((k%p)%p)*a;

  

  

  }

  

if(k==1){

  sum1=sum1+1;

  }

 

 

 

 }

  if(sum1==i){

  sum=sum+1;

  }

  }

 

 endtime= ((double) clock()/CLOCKS_PER_SEC);

printf("Probabilistic algorithm: Found %d primes in %.2f secs (tries = %d)\n",sum,endtime-sttime,i);

 

 }

 

 

  }

 

 

 

 

 

 

 

 

 

 

 

1)Χρησιμοποιω αυτο το φιτρο διοτι μου το δινει η ασκηση

2)Πρεπει να χρησιμοποιησω αυτες τις σχεσεις 

 

x^(2n+1)=(x*(x^2n mod m) )mod m

x^2n= (x^2 mod m)^n mod m

 

 

 

 

 

Επεξ/σία 15 Νοεμβρίου 2014 από johninio