4. Kleiner fermatscher Satz Problem

Kleiner fermatscher Satz Problem

  • D

    Hallo,
    Ich weiß nicht ob ich einen Fehler gemacht habe oder nur auf dem Schlauch stehe, aber ich versuche gerade mit Hilfe des kleinen fermatscher Satzes Primzahlen zu überprüfen, aber irgendwie funktioniert mein code nicht:

    srand (time(NULL));
for(i=0;i<=20;i++){
    a=rand()%(prim-2)+1;
    if(pow(a,(prim-1)) == (1%prim)){
    printf("Ist eine Primzahl!\n");
    return 0;
  }
  }
  printf("Ist keine Primzahl!\n");
return 0;

    Ich bekomme jedes mal die Meldung: Ist eine Primzahl.
    Obwohl ich auch bekannte prüfen (z.B. 11, 13...43...).
    Kann mir jemand einen Tipp geben?
    Denn laut Wikipedia müsste eine Primzahl doch eine Primzahl sein, wenn:
    a^Primzahl-1 == 1 modulo Primzahl oder?

    MfG,
    Fer

    PS: Der gesamte Code lautet:

    #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int main(void){
  int prim, a, i;
  printf("Zahl die geprüft werden soll:\n");
  scanf("%i",&prim);
  if(prim == 2){
    printf("Ist eine Primzahl!\n");
    return 0;
  }
  if(prim%2 == 0){
    printf("Ist keine Primzahl (teilbar durch 2)!\n");
    return 0;
  }
  srand (time(NULL));
  for(i=0;i<=20;i++){
    a=rand()%(prim-2)+1;
    if(pow(a,(prim-1)) == (1%prim)){
    printf("Ist eine Primzahl!\n");
    return 0;
  }
  }
  printf("Ist keine Primzahl!\n");
return 0;
}
    0
  • I

    Deine Interpretation der Formel ist Quatsch, aber darauf hättest du auch selbst kommen können. Nehmen wir als Primzahl 13. Was ist 1 mod 13? Natürlich 1, dein 1%prim ist sinnlos, das gibt immer 1. Auf der anderen Seite, kann a^12 denn jemals eins werden, außer a ist zufällig 1?
    Des Rätsels Lösung: Das (mod p) in der Gleichung bezieht sich auf die gesamte Gleichung, also gilt a^(p-1) mod p = 1 mod p = 1. Test: 5^12 = 244140625 = 18780048*13 + 1, stimmt also.

    Der Fehler im Programm ist aber noch ein anderer. Du musst überprüfen, ob der Test für alle 20 zufälligen Basen gilt, damit die Zahl mit hoher Wahrscheinlichkeit eine Primzahl ist. Zur Zeit überprüfst du nur, ob es für eine gilt. Und bei hinreichend kleinen Zahlen bekommst du öfters zufällig als Basis auch mal 1, die die Bediengung natürlich immer erfüllt (und du somit auch gleich ausschließen kannst).

    Wenn du irgendwann mit größeren Zahlen rechnest, wird der jetzige Weg mit pow übrigens schnell zu Überläufen führen (passiert teilweise jetzt schon). Da du aber mod p rechnest, könntest du nach jeder Multiplikation in deiner eigenen pow_mod_p-Funktion jeweils mod p rechnen und somit Überläufe verhindern.

    0
  • D

    Oh jetzt wo du es sagst oO
    Hätte ich doch lieber das noch mal durch gerechnet...und gedacht....

    Also gehe ich denn recht in der Annahme das es so richtig ist:
    P ist eine prim Zahl wenn:
    (a^(P-1)) mod P = 0
    Richtig? Also wenn P und a teilerfremd sind oder?

    Also nach der Formel von Wikipedia z.b.:
    a=4 , P =3
    a(P-1)-1=4(3-1)-1=4^2-1=15
    und 15 mod 3 = 0 -> Also 15 ist durch teilbar und das stimmt also 3 ist eine Primzahl. Hab ich es jetzt richtig verstanden?

    Ich überlege morgen noch mal wegen des Überlaufs....
    MfG,
    Fer

    0
  • I

    Ja ist richtig, bis auf eine Sache: es gibt Basen, bei denen die Gleichung auch für Nicht-Primzahlen erfüllt ist (Beispiel: 2^340 mod 341 = 1, aber 341 ist keine Primzahl). Nur Primzahlen erfüllen die Gleichung für alle Basen. Deswegen testet man mehrere Basen durch und wenn es für alle stimmt, kann man mit hoher Wahrscheinlichkeit davon ausgehen, dass es eine Primzahl ist.

    0
  • D

    Ahh ok, Danke.

    Also mit dem Code klappt es jetzt bis 11 (alle Primzahlen werden inkl. 11 erkannt).

    srand (time(NULL));
  for(i=0;i<=10;i++){
    a=rand()%(prim-2)+1;
    if((unsigned long)pow(a,prim-1)%prim == 1){
       isprim++;
    }
  }
  if(isprim < 10){
    printf("Ist keine Primzahl!\n");
  }else{
    printf("ist eine Primzahl\n");
  }

    Danach klappt es nicht mehr (es kommt bei der "Prüfung" 1 oder 11 heraus...) Ich denke das liegt dann wohl an dem Überlauf...

    MfG,
    Fer

    PS: Insgesamt sieht es so aus:

    #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

int main(void){
  unsigned int a, i;
  unsigned long prim;
  unsigned int isprim = 0;

  printf("Zahl die geprüft werden soll:\n");
  scanf("%li",&prim);
  if(prim == 2){
    printf("Ist eine Primzahl!\n");
    return 0;
  }
  if(prim%2 == 0){
    printf("Ist keine Primzahl (teilbar durch 2)!\n");
    return 0;
  }
  srand (time(NULL));
  for(i=0;i<=10;i++){
    a=rand()%(prim-2)+1;
    if((unsigned long)pow(a,prim-1)%prim == 1){isprim++;}
  }
  if(isprim < 10){
    printf("Ist keine Primzahl!\n");
  }else{
    printf("ist eine Primzahl\n");
  }
return 0;
}
    0
Anmelden zum Antworten