c modular exponentiation right to left

[johninio]

Καλημερα εχω ενα προγραμμα στην c να φτιαξω αλλα αντιμετωπιζω διαφορα προβληματα.Το προβλημα ειναι το εξης.Εχω ενα διαστημα MINNUM=1990000001 MAXNUM=20000000 παιρνω ενα π απο αυτο διαστημα και θελω να δω αν ειναι πρωτος . Ο fermat λεει οτι αν a^(p-1)modp =1 τοτε πιθανως ειναι πρωτος αριθμος οπου α ενας τυχαιος αριθμος απο 1 μεχρι π-1. Οσο πιο πολλα α γενναω τοσο η πιθανοτητα τεινει αυξανεται.Οποτε πρεπει να βρω ποσα πρωτοι υπαρχουν σε αυτο διαστημα γεννωντας ενα α μετα 2 μετα 3 μεχρι 10. Το προγραμμα μου ειναι το εξης

 

/*File:fermat.c*/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
# define MINNUM 1990000001
# define MAXNUM 2000000000
# define MAXTRIES 10
main()
{ int i,j,flag,sum,c,sum1,s4;
  unsigned int p,a,s,k,s2,s3,s1,n;  
  long curtime;
  double sttime,endtime;
  printf("Checking range [%d,%d]\n",MINNUM,MAXNUM);

curtime = time(NULL);
      srand((unsigned int) curtime);
      printf("Trying Fermat test with seed %ld\n",curtime);   
  for(i=1; i<=MAXTRIES; i++){
    sum=0;    
    sttime= ((double) clock ()) /CLOCKS_PER_SEC;   
    for (p=MINNUM; p<=MAXNUM; p=p+2){
        sum1=0;
        for(j=1; j<=i; j++){
        a = rand() % (p-1) + 1 ;
        unsigned long long s1=a*a;
         s2=(s1%p);
        n=(p-1)/2;        
         k=s2;        
        while(n!=1){
        unsigned long long s=(k*k)%p;
        n=n/2;
        unsigned long long k=s;       }        
        s4=k%p;    
                
            if(s4==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);}
 
 
}

 

Θελω να μου πειτε αν ειμαι στο σωστο δρομο και γενικα αν γινεται overflow ετσι οπως το εχω κανει διοτι σπαω το κεφαλι μου και τιποτα.Ευχαριστω εκ των προτερων

[albNik]

H powmod (a^b mod m) υλοποιείται αναδρομικά

long PowerMod(long a, long b, long m)
{
 if(b == 0)
  return 1;
 else if(b == 1)
  return a % m;
 else
 {
  long temp = PowerMod(a, b / 2, m);
  if(b % 2 == 0)
   return (temp * temp) % m;
  else
   return ((temp * temp) % m) * a % m;
 }
}

Γενικα πρεπει το (mod m)² να χωράει σε long, οποτε επειδή η αριθμοί σου ειναι της ταξης του 2 δις μπορει να εχεις overflow (4*10¹⁸)

Πάντως αν για καποιον εχεις overflow σίγουρα δεν ειναι prime. 

 

Edit 

Το MAX_LONG (64-bit) ειναι μεγαλύτερο απο 4*10^18 , αρα δεν εχεις πρόβλημα

[johninio]

Το πρόβλημα πρέπει να λυθεί χωρίς pow

[albNik]

Προσαρμοσε τον κωδικα της PowerMod που σου δινει το modular exponentiation στο for loop

*Που ειδες την pow?

 

Στον κωδικα που εχεις εσυ για να βρες π.χ.  2^1990000000 mod 1990000001 θα κανεις 1990000000 πολλαπλασιασμους και αλλα τοσα mods

[johninio]

Το προγραμμα μου το εγραψα ετσι αλλα και παλι δεν μου βγαζει αποτελεσματα σωστα

 

/*File:fermat.c*/

#include <stdio.h>

#include <time.h>

#include <stdlib.h>

# define MINNUM 1990000001

# define MAXNUM 2000000000

# define MAXTRIES 10

main()

{ int i,j,flag,sum,c,sum1,s4;

  int p,a,s,k,s2,s3,s1,n; 

  long curtime;

  double sttime,endtime;

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

curtime = time(NULL);

  srand((unsigned int) curtime);

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

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

sum=0;

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

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

sum1=0;

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

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

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

s=a;

n=(p-1)/2;

while(n!=0){

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

long long s=s1;

n=n/2;}}

else

{ 

n=(p-1)/2;

s=a;

while(n!=0){

long long s1=((s*s)%p)*a;

long long s=s1;

n=n/2;}}

s2=s%p;

if(s2==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);}

 

 

}

 

 

[albNik]

Για δες αυτο

Για καθε p τσεκαρει i^(p-1) mod p για καθε 1<i<10

Αν για καποιο i δεν ειναι 1 τότε δεν ειναι πρωτος

 

Τον υπολογισμό το κανει όπως στο λινκ

http://stackoverflow.com/a/8496248/1750895

for(int p = MINNUM; p <= MAXNUM; p = p + 2)
{
 int isPrime = 1;
 for(int i = 2; i < 10; i++) //check i^(p-1) mod p
 {
  long long a = i;
  long long b = p - 1;
  long long n = p;
  int modPow = 1;   //modPow=i^(p-1) mod p
  while(
  {
   if(b % 2) { modPow = (modPow * a) % n; }

   a = (a * a) % n;
   b /= 2;
  }

  if(modPow != 1)
  {
   isPrime = 0;
   break;
  }
 }
 if(isPrime)
  sum++;
}
printf("%d", sum);

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

[johninio]

εγω δεν μπορω να κατλαβω στο δικο μου προβλημα που ειναι το λαθος στα sum; γινεται overflow;

α εκανα και μια αλλαγη εβαλα οπου s2 =s και οχι mod p διοτι το υπολογιζω στο loop αλλα και παλι τιποτα

[albNik]

Εκανα εδιτ στο παραπάνω και βγαινει οκ.

Το sum δεν γινεται overflow ειναι περιπου 400.000 -500000

[johninio]

φιλε μου σε ευχαριστω πολυ απλως τωρα καθομαι και βλεπω τον δικο μου κωδικα να δω που υπαρχει λαθος . Διοτι θελω να δουλεψει ο δικος μου κωδικασ

[albNik]

φιλε μου σε ευχαριστω πολυ απλως τωρα καθομαι και βλεπω τον δικο μου κωδικα να δω που υπαρχει λαθος . Διοτι θελω να δουλεψει ο δικος μου κωδικασ

Καταρχας μηδενιζεις το sum σε καθε retry ...

[johninio]

δεν πρεπει να το μηδενιζω ;;

[albNik]

δεν πρεπει να το μηδενιζω ;;

Δλδ αν ολοι ειναι πρωτοι και ο τελευταίος συνθετος το sum στο τελος θα γινει 0

[johninio]

μπορεις να κανεις edit τον κωδικα μου ;

[albNik]

Ναι

Ctrl-A, Delete,  Ctrl-A τον δικο μου, Ctrl-C, Ctrl-V στον δικο σου

[defacer]

φιλε μου σε ευχαριστω πολυ απλως τωρα καθομαι και βλεπω τον δικο μου κωδικα να δω που υπαρχει λαθος . Διοτι θελω να δουλεψει ο δικος μου κωδικασ

 

Σωστό σε βρίσκω αλλά αν θες να βρεις που υπάρχει λάθος, και ειδικά αν θες να σε βοηθήσει άλλος να το βρεις, θα πρέπει να ξεκινήσεις κάνοντας τον κώδικα κατανοητό στον για να μπορεί κανείς να τον επεξεργαστεί νοητικά.

 

int i,j,flag,sum,c,sum1,s4;
int p,a,s,k,s2,s3,s1,n; 

Σοβαρά τώρα αυτό π.χ. μοιάζει περισσότερο με λίστα από android smartphones παρά από ακέραιες μεταβλητές.