Primzahlen schnell erkennen
Von: , Frage gestellt am Di, 12. Dez 2000
Hallo, wie kann ich bei einer grossen Zahl schnell erkennen, ob es sich um eine Primzahl handelt? (gib es da irgendwelche Regeln)
Gruss Mirco
8 Antworten zu dieser Frage
-
Antwort von nach 6 Minuten hilfreich
Re: Primzahlen schnell erkennen
Hallo, wie kann ich bei einer grossen Zahl schnell erkennen,
ob es sich um eine Primzahl handelt? (gib es da irgendwelche
Regeln)
leider nein. Es gibt keinen schnellen Algorithmus, der verr"at ob eine Zahl eine Primzahl ist.
Du musst also testen, ob sie durch eine Primzahl < Wurzel der grossen Zahl teilbar ist....
-
Antwort von nach einer Stunde hilfreich
Re^2: Primzahlen schnell erkennen
Es gibt keinen schnellen Algorithmus, der verr"at
ob eine Zahl eine Primzahl ist.
Du musst also testen, ob sie durch eine Primzahl < Wurzel
der grossen Zahl teilbar ist....
Soweit ich weiß gibt es eine Funktion, die 1 zurückgibt, wenn man eine Primzahl einsetzt und 0 wenn wie eingesetzte Zahl keine Primzahl ist. Wenn ich mich recht entsinne heißt das Ding Primzahlpolynom. Leider habe ich dazu nichts brauchbares im Netz gefunden.
-
Antwort von nach 4 Stunden 2 hilfreich
Re^2: Primzahlen schnell erkennen
leider nein. Es gibt keinen schnellen Algorithmus, der verr"at
ob eine Zahl eine Primzahl ist.
Hallo Michaela,
das stimmt nicht: Es gibt schnelle Algorithmen zum Primzahltesten.
Du weißt vielleicht, daß die heute üblichen Verschlüsselungssysteme (PGP etc.) auf Produkten aus zwei großen Primzahlen beruhen. Bei der Generierung eines solchen Schlüssels muß also von dem betreffenden Programm festgestellt werden, ob eine große (z. B. 64 oder 128 Bit lange) Zufallszahl prim ist oder nicht. Diese Algorithmen arbeiten nun aber nicht so, daß sie beginnend von 3 bis Wurzel(Zufallszahl) alle ungeraden Zahlen als eventuelle Teiler durchchecken – dabei würde man sich in der Tat schwarzrechnen –, sondern sie testen nur mit einer vergleichweisen geringen Menge an potentiellen Teilern, wobei dies aber besonders "ausgesuchte" Zahlen sind, in dem Sinne, daß sie bei einem Fehlschlag der Teilung (Rest > 0) ein starkes Indiz darauf liefern, daß die Zahl prim ist. Diese Algorithmen werden als "probabilistische Primzahltests" bezeichnet. Sie können in der Tat "nur" mit einer gewissen Wahrscheinlichkeit bestimmen, ob eine gegebene Zahl prim ist, aber diese Wahrscheinlichkeit kann beliebig groß ("1–10^–x") gemacht werden (es gibt Tests, bei denen die Wahrscheinlichkeit eines Irrtums kleiner ist als die eines Hardwarefehlers(!) während der Laufzeit). Was diese Algorithmen alle nicht liefern, ist die Primfaktorzerlegung einer nicht-primen Zahl; für diese Aufgabe gibt es tatsächlich keinen schnellen Algorithmus (gäbe es einen, wäre den Verschlüsselungssystemen ihre Grundlage entzogen).
Es ist also wichtig, zwischen der Frage "Ist die Zahl N prim?" und der Frage "Wie lautet die Faktorisierung der Zahl N?" zu unterscheiden. Die erste ist auch für große Zahlen schnell zu beantworten, die zweite nicht.
Mit freundlichem Gruß
Martin
-
Antwort von nach 3 Tagen hilfreich
Re^3: Primzahlen schnell erkennen
leider nein. Es gibt keinen schnellen Algorithmus, der verr"at
ob eine Zahl eine Primzahl ist.
Hallo Michaela,
das stimmt nicht: Es gibt schnelle Algorithmen zum
Primzahltesten.
und wie funktioniert der? wo kann man sowas nachlesen (ich würde gerne selber mal sowas programmieren)
Grüße
Moritz
-
-
-
Antwort von nach 2 Stunden hilfreich
Re: Primzahlen schnell erkennen
Hallo, wie kann ich bei einer grossen Zahl schnell erkennen,
ob es sich um eine Primzahl handelt? (gib es da irgendwelche
Regeln)
Gruss Mirco
Versuch den Primzahlchecker:
http://ema.bonn.de/primzahl.htm
Gruß
Rainer
-
Antwort von nach 3 Stunden 1 hilfreich
Re^2: Primzahlen schnell erkennen
Versuch den Primzahlchecker:
http://ema.bonn.de/primzahl.htm
Versuch ihn lieber nicht. Das Programm ist eine Frechheit. Anstatt zu sagen, ob die Zahl eine Primzahl ist, gibt sie nacheinander jede Primzahl aus, durch die sie teilbar ist und zwar jedesmal mit einem eigenen Dialog. Wenn Du eine hinreichend große Zahl eingibst, mußt Du klicken bis der Finger abstirbt oder den Browser mit Gewalt abschießen.
-
Antwort von nach 4 Stunden hilfreich
Re^3: Primzahlen schnell erkennen
Natürlich sagt es, ob die Zahl eine Primzahl ist, gib mal 7 rein.
Die Teilerei kommt nur bei Nicht-Primzahlen und ist so gewollt.
Ist allerdings bei großen Zahlen etwas lästig, stimmt ;-)
Gruß
Rainer [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
-
-
-
Antwort von nach einem Tag 3 hilfreich
Re: Primzahlen schnell erkennen
Hallo, wie kann ich bei einer grossen Zahl schnell erkennen,
ob es sich um eine Primzahl handelt? (gib es da irgendwelche
Regeln)
Es gibt den kleinen Fermatschen Satz:
Ist p prim und a natürliche Zahl mit 1<=a<p, so ist
ap-1 = 1 (mod p)
Das folgende Verfahren wird als Fermat-Test bezeichnet:
1. Wähle ein a <p
2. berechne ap-1 (mod p)
3. kommt nicht 1 raus, so ist p keine Primzahl. Fertig.
4. kommt 1 raus, so ist p vielleicht eine Primzahl. In diesem Fall kann man dasselbe ja noch mit anderen a's wiederholen, bis man entweder rausgekriegt hat, dass p nicht prim ist, oder bis einem die Wahrscheinlichkeit dafür, dass es eine Primzahl ist, hoch genug erscheint.
Das ist zwar nur ein probabilistischer Algorithmus, aber immerhin.