kleiner Fermats Satz, große

[Andavos]

Hallo,
also ich versuche gerade den kleinen Fermat Satz zur Überprüfung von Primzahlen zu Programmieren in C.

http://de.wikipedia.org/wiki/Primzahl

Es gilt:
 "a^(p-1) ist kongruent zu 1 in Bezug auf mod p" (hoffe habs so richtig geschrieben)

http://de.wikipedia.org/wiki/Mod_(Mathematik)

Also ihr müsst beachten das dort _kein_ Gleichheitszeichen steht.

Weiter steht bei Wikipedia geschrieben, dass dies für jede ungerade Primzahl p und jede natürliche Zahl a mit 2 <= a < p gilt.

Ich hab es versucht mal in C zu programmieren:

unsigned long x;
long p;

x = pow(2,p-1);
x = x%p;

if(x == 1)
{
//Primzahl
}
else
{
//Keine Primzahl
}

Dabei ist mein a
= 2.

Naja jetzt stoße ich sehr schnell auf ein Problem, denn long kann ja nur Zahlen bis 4 294 967 296 speichern, allerdings ergibt 2^37 = 137 438 953 472 (bräuchte 2^37 Bit speicherplatz).

Dann speichert er also in die Variable x einfach eine 0, und somit sind die weiteren Rechnungen falsch => Falsche Ausgabe. Das ist natürlich nicht so schön, denn die Primzahlen bis 32 (max. größter Wert) kann man ja auswendig ;)

Meine Lösungen dazu wären:
x = pow(2,p-1) % p; //Zeile 39

So könnten ja am Beispiel (p=37) max. einen Wert von bis 36 bekommen.

Das Problem, beim Compiler (Dev-C++ 5.x) erscheint folgende Fehlermeldung:
39 c:\primzahlen.cpp invalid operands of types double' and long int' to binary `operator%'

Da müsste ich dem Computer irgendwie "verklickern", dass pow(...) _kein_ double sondern ein (long) int ausgibt.

Ich habe mir mal eine hoch funktion geschrieben:
long hoch(long x,long y)
{
  long erg,i,x_anf;
  x_anf = x;
  i = 1;

while(i < y)
    {
    x = x*x_anf;
    i++;
    }

return(x);
}

Aber da kann ich ja auch nur Zahlen bis max. 2^32 (sofern ich es noch auf unsigned setze) potenzieren.
Aber:
x = hoch(2,p-1) % p; //Zeile 39

funktioniert dann.

Naja dann 2. Idee wäre:
Wie könnte man größere Zahlen als 2^32 speichern, und mit denen dennoch einen Modulo-Division (%) durchführen kann?

MFG
Andavos

[Hans]

Guten Abend,

tut mir leid Dich enttäuschen zu müssen, aber hier in diesem
Forum findest du auf solch eine Frage meißt keine wirklichen
(qualitativen) Antworten. Die Poster hier 'programmieren'
alle HTML und PHP und so einen WebKram. Also nichts wirklich
Richtiges. Was man dann u.a. eben bei solchen Fragen feststellt.
Aber wer weiß, vielleicht hast du
ja dennoch Glück ;-)

Friede, Freude, Eierkuchen
Euer Hans

[Mike©]

Moin Hans,

tut mir leid Dich enttäuschen zu müssen, aber hier in diesem
Forum findest du auf solch eine Frage meißt keine wirklichen
(qualitativen) Antworten. Die Poster hier 'programmieren'
alle HTML und PHP und so einen WebKram. Also nichts wirklich
Richtiges. Was man dann u.a. eben bei solchen Fragen feststellt.

was soll den dieser Kommentar?

Ich zügle mich, da Du mich erbost findest.

Nur weil hier das "Thema" WEB ist, heist das noch lange nicht, das die Leutr hier nicht programmieren können! Bzw. auch über den Tellerrand hinaus schauen können.

Ich sags mal so: Ich weiß wer Fermats war, und ich kenne seinen Satz.
Du auch?

regds
Mike©

[ottogal]

Moin,

Ich sags mal so: Ich weiß wer Fermats war ...

... und auch, dass er Fermat hieß?

;)
ottogal

[Mike©]

Moin ottogal,

... und auch, dass er Fermat hieß?

möge mir im Eifer des Gefechts verziehen sein :-(

regds
Mike©

[Thomas Meinike]

Hallo,

Wie könnte man größere Zahlen als 2^32 speichern, und mit denen dennoch einen Modulo-Division (%) durchführen kann?

BCD-Arithmetik (Binary Coded Decimals) bietet sich an. PHP kennt dazu bereits fertige Funktionen. Ansonsten suche mal nach entsprechenden Routinen fuer C. Sogar fuer BASIC-Dialekte gibt es solche Routinen, z. B. im ProMath-Paket.

MfG, Thomas

[ziegenmelker]

Hallo,

Naja dann 2. Idee wäre:
Wie könnte man größere Zahlen als 2^32 speichern, und mit denen dennoch einen Modulo-Division (%) durchführen kann?

ich würde dies alles in Assembler programmieren, mir meine eigenen Datentypen definieren und die nötike Arithmetik eben auch. Praktisch ist mein letztes Assemblerprogramm aber schon viel zu lange her, um das mal eben so zu machen, obwohl, da ist sofort wieder dieses Kribbeln *g*

Andererseits müsste es auch möglich sein sowas in C zu programmieren, indem du z.B. 2 long int Variablen zu einem neuen Datentyp (nennen wir ihn array oder Vektor) machst und die nötige Arithmetik selbst programmierst. Das Problem hierbei sind die Überträge vom 'low' zum 'high' Byte und umgekehrt. Du müsstest also die Größe der jeweils darstellbaren Zahl begrenzen und alles was größer ist, als Übertrag betrachten und diesen gesondert behandeln.

Ich habe sowas früher mal in Simula programmiert, ebenfalls um so etwa die doppelte Rechengenauigkeit zu erreichen. Wenn du noch Tips brauchst, dann frag' ruhig noch mal nach.

cu,
ziegenmelker

[Christian Kruse]

你好 ziegenmelker,

Andererseits müsste es auch möglich sein sowas in C zu programmieren,
indem du z.B. 2 long int Variablen zu einem neuen Datentyp (nennen wir
ihn array oder Vektor) machst und die nötige Arithmetik selbst
programmierst.

Unnoetig... die meisten Compiler koennen mit “unsigned long long” umgehen,
was auf gaengigen 32-Bit-Maschinen eben 64 Bit sind. Und die reichen nun
wirklich aus, auch ohne Optimierungen...

再见,
 CK

[Andavos]

Hallo

Unnoetig... die meisten Compiler koennen mit  unsigned long long

Gut das funktioniert auch, allerdings ist es dann nur möglich bis max. 65 (x^(65-1)) zu testen, danach reicht der Speicher wieder nicht aus.

Also müsste man einen Speichertyp finden der z.B. bis 2^4 000 000 testen kann, in PHP ist es ja ohne Probleme möglich mit 600stellige Zahlen zu rechnen, da die Typenzuweisung automatisch übernommen wird.

Oder durch Zerlegung, daran werde ich mich jetzt machen.

P.S. Das soll nicht Kryptologisch sicher sein, aber unser Lehrer meinte es gäbe keine Formel um Primzahlen zu testen, nur das Sieb verfahren.
Naja da wollte ich ein Programm schreiben das Primzahlen bis ~100 000 testen kann, _ohne_ das Sieb des Eratosthenes zu benutzen.
Denn ab 20 stelligen Zahlen dauert das ja zu lange.

MFG
Andavos

[Daniel Thoma]

Hallo Andavos,

Oder durch Zerlegung, daran werde ich mich jetzt machen.

Was willst Du denn wie zerlegen?

P.S. Das soll nicht Kryptologisch sicher sein, aber unser Lehrer meinte es gäbe keine Formel um Primzahlen zu testen, nur das Sieb verfahren.
Naja da wollte ich ein Programm schreiben das Primzahlen bis ~100 000 testen kann, _ohne_ das Sieb des Eratosthenes zu benutzen.

Naja, damit hast Du die Aussage Deines Lehrers nicht wiederlegt. Da dieser Test eben auch nicht-Primzahlen erkennt.
Tatsächlich kann man Primzahlen aber viel schneller als mit dem Sieb erkennen.
Es geht sogar in Polynomialzeit: < http://de.wikipedia.org/wiki/AKS-Methode>

Grüße

Daniel

[Andavos]

Hallo,
bei Zahlen ab 20 stellen ist die Siebmethode nicht schnell genug, da muss man dann auf solche "Formelen" zurückgreifen.

Gut dass diese auch Pseudoprimzahlen erkennen ist mir bekannt, dennoch wollte er mir nicht glauben, dass man Primzahlen mit einer Genauigkeit von ~99.999% [1] nur durch dem kleinen Fermat Satz bestimmen kann.

Möglich ist sogar eine Genauigkeit von 1 zu 2^-80

Mit zerlegen bezog ich mich auf folgenedn Post:
link:http://forum.de.selfhtml.org/?t=101529&m=623449]

P.S. Mein Code sieht so aus und ich hab ihn bis Primzahlen von 1 Mio getestet und es funktioniert :)

===========Anfang=========

long long modpow(long long b, long long e, long long m)
  {
  if(e == 1)
    {
    return b % m;
    }
  else
    {
    unsigned long long r = modpow(b, e / 2, m);
    r = (r * r) % m;
    if(e % 2 == 0)
      {
      return r;
      }
    else
      {
      return (r * b) % m;
      }
    }
  }

long fermat(long p)
{
long x2;
x2 = modpow(2,p-1,p);

return x2;
}

=============ENDE==========

[1] Bei a=2 gibt es bei Zahlen zwischen 10 und 100.010 genau 78 Pseudoprimzahlen.

MFG
Andavos

[Henryk Plötz]

Moin,

also ich versuche gerade den kleinen Fermat Satz zur Überprüfung von Primzahlen zu Programmieren in C.

http://de.wikipedia.org/wiki/Primzahl

Unabhängig von deinem Problem weiter unten solltest du aber noch beachten dass es auch eine Reihe Zahlen gibt die zwar keine Primzahlen sind, aber dennoch nicht durch diesen Test fallen. D.h. eigentlich willst du nicht nur den kleinen Fermat machen sondern einen Rabin-Miller-Test. Ich kann da grade meine Mitschrift zum Thema anbieten: http://www.informatik.hu-berlin.de/~ploetz/openssl/ (Abschnitt 4.3, bzw. Seite 22). (Ich hoffe nur da ist alles richtig, das ist alles work in progress.)

Ich hab es versucht mal in C zu programmieren:

Hmm, dann würde ich dich am besten mal an den Sourcecode von OpenSSL verweisen, da die sowas ja auch machen müssen. Ich glaube der entsprechende Code liegt in crypto/bn/bn_prime.c, das sah jedenfalls beim Überfliegen vielversprechend aus.

[Daniel Thoma]

Hallo Andavos,

Mit longs kannst Du sehr viel größere Primzahlen so testen. Du musst nur ein Bisschen geschickter vorgehen.

Statt erst zu Potenzieren, und dann Modulo zu rechnen, kannst Du nach jeder Multiplikation modulo rechnen.
Es gilt: a^n % m = f(a, n, m) wobei:
f(a, 1, m) := a % m;
f(a, n, m) := (f(a, n - 1, m) * a) % m;

Beweis durch Induktion:
Für 1: a % m = f(a, 1, m) = a % m --> OK
Für n + 1; a^(n + 1) % m = (a^n * a) % m = ((a^n div m) * m * a + (a^n % m) * a) % m = ((a^n % m) * a) % m = (f(a, n, m) * a) % m

Damit hat man nun eine Möglichkeit die Zahlen < p^2 zu halten.

Die Potenzen kann man noch mit folgendem Trick schneller ausrechnen (Beispiel):

2 * 2 * 2 * 2 * 2 * 2 * 2 = (2 * 2 * 2) * ((2 * 2 * 2) * 2) = 8 * 8 * 2 = 128

Man verwendet Teilergebnisse also mehrmals.
Daraus kann man nun einen Algorithmus bauen (hier in Java):

public class Prim {

public static void main(String[] argv) {
                long p = Long.parseLong(argv[0]);
                long x = modpow(2, p - 1, p);
                if(x == 1) {
                        System.out.println(p + " ist eine Primzahl.");
                }
                else {
                        System.out.println(p + " ist keine Primzahl.");
                }
        }

public static long modpow(long b, long e, long m) {
                if(e == 1) {
                        return b % m;
                }
                else {
                        long r = modpow(b, e / 2, m);
                        r = (r * r) % m;
                        if(e % 2 == 0) {
                                return r;
                        }
                        else {
                                return (r * b) % m;
                        }
                }
        }
}

Grüße

Daniel

[Henryk Plötz]

Moin,

Die Potenzen kann man noch mit folgendem Trick schneller ausrechnen (Beispiel):

2 * 2 * 2 * 2 * 2 * 2 * 2 = (2 * 2 * 2) * ((2 * 2 * 2) * 2) = 8 * 8 * 2 = 128

Wobei man Potenzen von 2 natürlich nicht über die Multiplikation sondern über Bitoperationen ausrechnet: pow(2,x) == 1 << x

Man verwendet Teilergebnisse also mehrmals.
Daraus kann man nun einen Algorithmus bauen (hier in Java):

public class Prim {

public static void main(String[] argv) {
                long p = Long.parseLong(argv[0]);
                long x = modpow(2, p - 1, p);
                if(x == 1) {
                        System.out.println(p + " ist eine Primzahl.");
                }
                else {
                        System.out.println(p + " ist keine Primzahl.");
                }
        }

Vorsicht! So kann man nicht auf Primzahlen testen. Das Programm würde behaupten dass 561 (die erste Carmichael-Zahl) eine Primzahl ist, obwohl 561 = 3·11·17.

[Daniel Thoma]

Hallo Henryk,

Wobei man Potenzen von 2 natürlich nicht über die Multiplikation sondern über Bitoperationen ausrechnet: pow(2,x) == 1 << x

Da man aber die Modulooperation immer noch dazwischen schieben muss, hilft einem das nicht viel. In dem Algorithmus gibt es ja nur eine Multiplikation mit 2.
Man könnte natürlich einfach n mal mit 2 Multiplizieren, aber da hat man dann n Modulos und Shifts, wärend man so nur lg(n) hat.
So lang man mit longs rechnet, ist das in etwa gleich schnell. Wenn man mit größeren Zahlen rechnen will, wirkt sich das aber auch, da die Rechenoperationen dann natürlich auch deutlich langsamer sind.

Vorsicht! So kann man nicht auf Primzahlen testen. Das Programm würde behaupten dass 561 (die erste Carmichael-Zahl) eine Primzahl ist, obwohl 561 = 3·11·17.

Vermutlich handelt es sich eh nur um eine Spielerei, dass das für Verschlüsselung nicht taugt, steht ja auch in dem angegebenen Wikipediaartikel.
Ich wollte nur demonstrieren, dass man solche Probleme nicht durch mehr Rechenpower oder Assemblertrickserreien löst.

Grüße

Daniel