Riesenzahl gleich Primzahl?
Marc Waesche
Ich bin leider kein Mathematiker, daher kommt Euch diese Frage vielleicht
merkwürdig vor.
Also, ich möchte wissen, ob es ein Verfahren gibt, auch bei einer extrem
großen Zahl (z.B. mit 300 Dezimalstellen) SCHNELL herauszufinden, ob diese
eine Primzahl ist.
Klar, man kann das mit Computerpower hochrechnen, aber das verstehe ich dann
nicht mehr unter "schnell". ;-)
Meine Frage ist also, ob man diese Mega-Zahl vielleicht in Blöcke zerlegen
und prüfen kann bzw. es irgendwelche Tricks über die Quersumme(n) gibt.
Viele Grüße,
Marc
Edgar Fuß
Lange Antwort: Das ist ein äußerst komplexes Gebiet, die verwendeten
Methoden sind alles andere als trivial; in der Tat sind sie größtenteils
so kompliziert, daß ich, der ich Mathematiker, aber kein Zahlentheoretiker
bin, nicht verstehe. Insbesondere gibt es probabilistische Methoden, die
Dir nur mit einer gewissen, durch langes Rechnen steigerbaren,
Wahrscheinlichkeit sagen, daß eine Zahl eine Primzahl ist. Man stellt
dabei an die Primzahl eine Frage, die noch von einem (zufällig wählbaren)
Parameter abhängig ist; ist die Zahl prim, kommt als Antwort ,,weiß
nicht`` heraus; ist sie zusammengesetzt, kommt ,,weiß nicht`` oder ,,ist
nicht prim`` heraus.
Hans-Peter Diettrich
MW>Ich bin leider kein Mathematiker
Ich auch nicht, und so nebenher beschäftige ich mich gerade auch mit
Primzahlen, speziell für die Verschlüsselung. Deshalb habe ich für Dein
Problem auch keine Lösung. Vermutlich gibt es auch keine, denn alle mir
bekannten Tests schließen nur bestimmte Faktoren (2, 3, 11...) aus. Die
übrigen Teiler müssen weiterhin per Division bzw. Modulo-Rechnung
ausgeschlossen werden, insgesamt ergibt sich keine Änderung der Ordung des
Problems. IMO, aber ich bin ja auch kein Mathemiker.
Dafür habe ich ein Problem mit der Ordnung. Wenn man die Stellenzahl einer
Zahl um 2 erhöht wird, dann erhöht sich die Zahl ihrer möglichen Teiler um
den Faktor 10 (Die Wurzel hat 1 Stelle mehr). Welche Ordnung hat nun das
Problem, eine Zahl auf Primzahl zu überprüfen? Exponentiell?
Irgendwie habe ich auch noch den Verdacht, daß die größten /bekannten/
Primzahlen alle von der Form (2^n - 1) sind? Liegt das vielleicht am
Verfahren, nach dem die Jagd auf die größte Primzahl abläuft?
Wenn nun jemand besonders clever sein will, und eine besonders große
Primzahl dieser Form für seinen Schlüssel verwendet, dann sollte der
Schlüssel (p*q) doch leicht zu knacken sein, weil sich die Ordnung des
Problems drastisch reduziert?
Gibt es noch mehr "einfache" Formen für Primzahlen, außer (2^n - 1)?
Hans-Peter
Uwe Ziemke
MW>> Ich bin leider kein Mathematiker
Heißt es nicht: Einmal Mathematiker immer Mathematiker ;-)
Na gut: sagen wir mal ich war nicht ganz unfähig. ;-)
HPD> Ich auch nicht, und so nebenher beschäftige ich mich gerade auch
HPD> mit Primzahlen, speziell für die Verschlüsselung. Deshalb habe
HPD> ich für Dein Problem auch keine Lösung. Vermutlich gibt es auch
HPD> keine, denn alle mir bekannten Tests schließen nur bestimmte
HPD> Faktoren (2, 3, 11...) aus. Die übrigen Teiler müssen weiterhin
HPD> per Division bzw. Modulo-Rechnung ausgeschlossen werden,
HPD> insgesamt ergibt sich keine Änderung der Ordung des Problems.
HPD> IMO, aber ich bin ja auch kein Mathemiker.
Die Ordnung dürfte sich nicht ändern. Ist ja gerade der "Trick" gegen
die Entschlüsselung ohne den Schlüssel.
HPD> Dafür habe ich ein Problem mit der Ordnung. Wenn man die
HPD> Stellenzahl einer Zahl um 2 erhöht wird, dann erhöht sich die
HPD> Zahl ihrer möglichen Teiler um den Faktor 10 (Die Wurzel hat 1
HPD> Stelle mehr). Welche Ordnung hat nun das Problem, eine Zahl auf
HPD> Primzahl zu überprüfen? Exponentiell?
Leider/glücklicherweise ja. Jenachdem ob man ent- oder verschlüsseln
will.
HPD> Irgendwie habe ich auch noch den Verdacht, daß die größten
HPD> /bekannten/ Primzahlen alle von der Form (2^n - 1) sind? Liegt
HPD> das vielleicht am Verfahren, nach dem die Jagd auf die größte
HPD> Primzahl abläuft?
Ja. IMHO liefert der kleine Fermatsche Satz (s.u.) für Zahlen der
Form 2^n-1 eine genau dann wenn Beziehung. Der Beweis war "relativ"
einfach.
HPD> Wenn nun jemand besonders clever sein will, und eine besonders
HPD> große Primzahl dieser Form für seinen Schlüssel verwendet, dann
HPD> sollte der Schlüssel (p*q) doch leicht zu knacken sein, weil
HPD> sich die Ordnung des Problems drastisch reduziert?
das Problems drastisch reduziert? JA
die Ordnung des Problems drastisch reduziert? Hmm, wirklich auch die
Ordnung?
HPD> Gibt es noch mehr "einfache" Formen für Primzahlen, außer (2^n-1?
Wenn Du mit "einfache" Formen meinst, daß es einen schnellen Test
gibt, dann leider nein. Daher liegt Dein Verdacht sehr nahe.
Der sogenannte kleine Fermatsche Satz liefert einen "relativ"
einfachen Primzahltest.
SATZ Wenn n eine Primzahl ist und a eine natürliche Zahl, a < n gilt,
dann ist a^n = a mod n.
Dabei bedeutet a = b mod n, daß a und b bei Division durch n mit Rest
den gleichen Rest haben (a kongruent b modulo n)
Wenn eine Zahl n keine Primzahl ist,
dann werden die meisten Zahlen a < n die obige Relation nicht
erfüllen. Man kann also eine Zahl a < n wählen und den Rest von a^n
bei Division durch n betrachten. Wenn das Ergebnis nicht gleich a
ist, dann ist n sicher keine Primzahl. Wenn das Ergebnis aber gleich
a ist, dann könnte n eine Primzahl sein.
Mehrmaliges Testen mit verschidenen Zahlen a steigert die
Wahrscheinlichkeit, daß n ein Primzahl ist.
Dieser Test ist als Fermat-Test bekannt.
a^n mod n zu berechnen erscheint zwar sehr speicherplatzintensiv zu
sein, aber es gibt einen kleinen Trick:
Man nehme die Binärdarstellung von n z.B. für n=43 =b101011
1 0 1 0 1 1
a^43 = a^(32*1) * a^(16*0) * a^(8*1) * a^(4*0) * a^(2*1) * a^(1*1)
- =1 - - =1 -
a^43 mod 43 =
((a^32 mod n) * (a^8 mod 43) * (a^2 mod 43) * (a mod 43)) mod 43
Dies wird nun wie folgt berechnet:
a mod 43 =: a1
a^2 mod 43 = (a1*a1) mod 43 =: a2 | (a1*a2) mod 43 =: a3
a^4 mod 43 = (a2*a2) mod 43 =: a4
a^8 mod 43 = (a4*a4) mod 43 =: a8 | (a3*a8) mod 43 =: a11
a^16 mod 43 = (a8*a8) mod 43 =: a16
a^32 mod 43 = (a16*a16) mod 43 =: a32 | (a11*a32) mod 43 =: a43
Dann ist a43 = a^43 mod 43
Fehlt nur noch der Test ob a43=a ist. :-)
statt a43 zu berechnen, berechnet man a42 und testet auf 1 ;-)
Es gibt einige wenige Zahlen n, die den Fermat-Test überlisten, die
sogenannten Carmichael-Zahlen.
Sie sind keine Primzahlen,
obwohl für sie a^n = a mod n für alle a < n gilt.
Die kleinsten Carmichael-Zahlen sind 561, 1105, 1729, 2465, 2821 und
6601.
Moin moin
Uwe
Moin moin
Uwe
Edgar Fuß
Zahlen a, daß a und a^p sich nur um ein Vielfaches von p unterscheiden. In
der Tat kann man beweisen, daß die Wahrscheinlichkeit, daß das bei
zusammengesetztem p für ein zufälliges a gilt, kleiner 1/2 ist (wenn ich
mich richtig erinnere). Also nimmt man zufällige a und probiert die
Beziehung durch. Wenn es für n Werte von a stimmt, dann ist p bis auf eine
Fehlerwahrscheinlichkeit von 2^-n prim; wenn es für einen Wert von a nicht
stimmt, kann p nicht prim sein, aber das liefert keinen Faktor.
RSA beruht ja gerade darauf, daß man relativ leicht zwei große Primzahlen
(oder Zahlen, die sehr wahrscheinlich prim sind) finden kann, das Produkt
aber sehr schwer zu faktorisieren ist.
Genauso, wie die Primzahltestmethoden wesentlich raffinierter sind, als
explizit das Nichtvorhandensein eines Teilers nachzuweisen, sind die
Faktorisierungsalgorithmen wesentlich raffinierter, als potentielle
Faktoren auszuprobieren.
Hans-Peter Diettrich
EF>Genauso, wie die Primzahltestmethoden wesentlich raffinierter sind, als
EF>explizit das Nichtvorhandensein eines Teilers nachzuweisen, sind die
EF>Faktorisierungsalgorithmen wesentlich raffinierter, als potentielle
EF>Faktoren auszuprobieren.
IMO funktionieren die ganzen "raffinierten" Tests nur in bestimmten Fällen?
Für eine definitive Feststellung, ob eine Zahl eine Primzahl ist, müssen
dann zumindest die von den vorhergehenden Tests nicht abgedeckten Fälle
weiterhin geprüft werden. Die Ordnung des Problems bleibt daher IMO
unverändert, und es ist ziemlich unwesentlich ob und wieviele der möglichen
Teiler durch vorgeschaltete Tests ausgeschlossen werden konnten.
Bei der Faktorisierung ergibt sich bei Zahlen mit mehr als 2 Teilern nur
ein kleiner Vorteil, indem die Faktorisierung nur für die verbleibende Zahl
(nach Division durch alle gefundenen Teiler) durchgeführt werden muß. Dabei
reduziert sich nicht die Ordnung des Problems, sondern nur deren Wert
(und damit die restliche Laufzeit...).
In der Praxis ist eine Reduzierung der Laufzeit von 10^x Jahren auf
10^(x-n) Jahre ziemlich belanglos, solange n<x bleibt ;-)
Hans-Peter
Uwe Ziemke
UZ>> das Problems drastisch reduziert? JA
UZ>> die Ordnung des Problems drastisch reduziert? Hmm, wirklich auch
UZ>> die Ordnung?
HPD> Ja, vor allem die Ordnung! Statt alle Zahlen von 2 bis sqrt(p)
HPD> zu prüfen, ob sie Teiler von p sind, müssen nur noch die Zahlen
HPD> 2^k - 1 untersucht werden, für k=2 bis ld(p). Verdoppelt man p,
HPD> erhöht sich k nur um 1.
Ägypten? Rembrandt???
Wenn p die Form 2^n-1 hat liefert der genannte Test ob p eine
Primzahl ist oder nicht. Falls nicht, mußt Du trotzdem die Zahlen 2
bis sqrt(p) (bzw. zumindest die Primzahlen bis dorthin ;-)) auf
Teilerschaft testen. Es sei denn Du brauchst die Teiler nicht. Für
die Entschlüsselung von RSA brauchst Du sie.
Wenn p nicht die Form 2^n-1 hat, dann kenne ich keinen Test der etwas
wesentlich vereinfacht. Es sei denn Du weißt, daß die Teiler die Form
2^m-1 haben.
HPD>> Gibt es noch mehr "einfache" Formen für Primzahlen, außer
HPD>> (2^n-1?
UZ>> Wenn Du mit "einfache" Formen meinst, daß es einen schnellen
UZ>> Test gibt, dann leider nein. Daher liegt Dein Verdacht sehr
UZ>> nahe.
HPD> Das ist ja schon mal sehr schön. Mit dem kleinen Fermatschen
HPD> Satz muß ich mich erst noch mal beschäftigen, vielen Dank für
HPD> die vielen nützlichen Hinweise. Er sieht jedoch nicht sehr
HPD> erfolgversprechend aus, wenn es um die Reduzierung der Ordnung
HPD> des Problems geht. Das war ja eigentlich auch nicht anders zu
HPD> erwarten, aber vielleicht fällt mir ja doch noch was ein. Da RSA
HPD> von Mathematikern erfunden bzw. zumindest abgesegnet wurde, dann
HPD> kann höchstens einem mathematischen Dilettanten (so wie mir)
HPD> eine Überlistung gelingen ;-)
Viel Spaß. Wenn Dir das gelingt, verkauf es möglichst teuer.
Moin moin
Uwe
Edgar Fuß
Ein Beispiel für einen (ziemlich primitiven) probalistischen Test habe ich
Dir ja gegeben.
>Die Ordnung des Problems bleibt daher IMO unverändert
Deine persönliche Meinung über die Komplexität ist ziemlich irrelevant. Es
wird Dir nichts anderes übrigbleiben, als zu glauben, daß es wesentlich
bessere Methoden als das Durchprobieren potentieller Teiler gibt. Oder Du
absolvierst zumindest ein Mathe-Grundstudium, um zumindest die alten
Algorithmen von Lenstra aus den späten 80ern verstehen zu können (da hab'
ich mal ein Seminar drüber besucht); wenn Du dann noch zwei oder vier
Semester Zahlentheorie dranhängst, kannst Du vielleicht auch verstehen,
wie das Zahlkörpersieb funktioniert, mit dem die Leute hier am Institut
letztens einen neuen Faktorisierungsrekord aufgestellt haben (wie gesagt:
da ich zwar Algebraiker, aber Guppen- und nicht Zahlentheoretiker bin,
verstehe ich diese Methoden nicht, was mich aber nicht davon abhält, an
ihre Existenz zu glauben).
Doch noch ein Beispiel für einen ganz primitiven Algorithmus, der große
Teiler einer Zahl sucht (und als Idee Ausgangspunkt für wirklich
verwendete, sehr viel geschicktere Verfahren sein soll):
Wenn sich die Zahl n, von der Du einen Faktor suchst, als Differenz zweier
Quadrate schreiben läßt, dann bist Du fertig, weil aus n=x^2-y^2 folgt,
daß x+y und x-y Teiler von n sind. Sei also m die größte (ganze) Zahl, so
daß m^2<n ist. Dann probiere kleine i durch und teste, ob n-(m-i)^2 ein
Quadrat ist.
Hermann Kremer
>
>... um zumindest die alten Algorithmen von Lenstra aus den späten 80ern
> verstehen zu können
http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html
http://www.ericweisstein.com/encyclopedias/books/PrimeNumbers.html
Gruß Hermann
--
Hans-Peter Diettrich
UZ>Wenn p die Form 2^n-1 hat liefert der genannte Test ob p eine
UZ>Primzahl ist oder nicht. Falls nicht, mußt Du trotzdem die Zahlen 2
UZ>bis sqrt(p) (bzw. zumindest die Primzahlen bis dorthin ;-))...testen.
Ich habe mich bei diesem Ansatz absichtlich auf Faktoren der Form 2^n-1
beschränkt, um den zu testenden Bereich auf n Zahlen zu schrumpfen. Dann
kann man sogar überflüssige Tests akzeptieren, falls ein Faktor 2^n-1
garkeine Primzahl ist. Das geht dann immer noch schneller als erst den
vermuteten Faktor erst auf Primzahl zu testen, und dann nochmal auf Faktor
der gegebenen Zahl.
Wenn die Zahl keinen Faktor der Form 2^n-1 enthält, liefert der
eingeschränkte Test natürlich kein brauchbares Ergebnis. Das habe ich bei
meinem Ansatz billigend in Kauf genommen.
Mein Ansatz war ähnlich wie beim Lotto: man kann zwar durch ein
Tipp-System
nicht die Wahrscheinlichkeit eines Gewinns erhöhen, aber durchaus die Höhe
des Gewinns und damit die Effizienz des Systems beeinflussen. Z.B. indem
man die von der Bild-Zeitung vorhergesagten Lottozahlen nicht verwendet.
UZ>Viel Spaß. Wenn Dir das gelingt, verkauf es möglichst teuer.
Genau das ist einer der Anreize, sich mit so einem Problem überhaupt zu
beschäftigen ;-)
An der ganzen Wissenschaft stört mich immer die Kluft zwischen Theorie und
Praxis. Natürlich ist Grundlagenforschung wichtig, ohne die geht es
einfach
nicht weiter. Daneben gibt es aber Leute, welche die Entdeckungen gerne
anwenden würden, und die werden dann oft mit unsinnigen Argumenten
abgespeist, wie "beschäftige Dich erst mal mit der Theorie / den
Grundlagen". Für die Anwendung muß man doch nicht wissen oder gar
begreifen, /wie/ ein Beweis zustande gekommen ist, wichtig ist nur, /daß/
es einen Beweis für irgendeine Aussage oder ein Verfahren gibt.
Solange kein Beweis existiert, daß sich große Zahlen nicht mit
vertretbarem
Aufwand faktorisieren lassen, darf sich auch ein Laie an das Problem
heranwagen. Er könnte ja zufällig ein brauchbares Verfahren finden, das
den
vernagelten Fachidioten in ihrem Elfenbeinturm <g> nie eingefallen wäre.
Für den Beweis der Korrektheit des Verfahrens sind dann wieder die
Experten
zuständig. In der Praxis reicht es dagegen aus zu wissen, daß (noch) kein
Gegenbeispiel gefunden wurde, in dem das Verfahren nachweislich versagt.
Gruppen wie diese sehe ich als so eine Brücke zwischen Theorie und Praxis,
nicht nur als Plattform für die Diskussion zwischen Experten oder
mit solchen, die es erst werden wollen.
Hans-Peter
Hans-Peter Diettrich
EF>Deine persönliche Meinung über die Komplexität ist ziemlich
EF>irrelevant.
Sehr schön, wie Du Deine fachliche Kompetenz gleich zu Anfang unter Beweis
stellst ;-)
EF> Es wird Dir nichts anderes übrigbleiben, als zu glauben,
EF>daß es wesentlich bessere Methoden als das Durchprobieren potentieller
EF>Teiler gibt.
Dir glauben? Das glaubst Du doch selbst nicht! ;-)
Aus der Sicht eines Informatikers tendiert der Informationsgehalt Deiner
Aussagen stark gegen Null.
EF> Oder Du absolvierst zumindest ein Mathe-Grundstudium
Im nächsten Leben vielleicht, in diesem sicher nicht mehr. Was die
Dozenten
vor 30 Jahren nicht geschafft haben, das schaffen sie heute erst recht
nicht mehr. Nachdem ein Bekannter mühsam und ziemlich vergeblich versucht
hat mir beizubringen, was es mit der Ordnung eines Algorithmus auf sich
hat, ist mir die Bedeutung bei der Faktorisierung ziemlich schnell klar
geworden. Ich brauche halt immer praktische Beispiele, um mir abstrakte
Sachverhalte tatsächlich merken zu können. Alles andere plätschert einfach
so an mir vorbei.
Hans-Peter
Hermann Kremer
>Hi Edgar,
[ ... ]
>EF> Oder Du absolvierst zumindest ein Mathe-Grundstudium
>Im nächsten Leben vielleicht, in diesem sicher nicht mehr. Was die
>Dozenten
>vor 30 Jahren nicht geschafft haben, das schaffen sie heute erst recht
>nicht mehr.
Dann röste hier nicht rum und lies Dir lieber erst mal
http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html
http://www.crypto-world.com/FactorWorld.html
http://www.loria.fr/~zimmerma/records/factor.html
http://www.loria.fr/~zimmerma/records/ecmnet.html
http://www.mupad.de/CAIN/APPL/FACTOR/
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/factors.html
http://www.cerias.purdue.edu/homes/ssw/cun/index.html
http://www-staff.maths.uts.edu.au/~rons/fact/fact.htm
http://research.microsoft.com/~pleyland/
http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/index.htm
und --> dort angegebene Links
http://primes.utm.edu/glossary/search.php --> Search Keyword: factorisation
http://www.alpertron.com.ar/ECM.HTM
http://mathworld.wolfram.com/PrimalityTest.html
http://mathworld.wolfram.com/news/2002-08-07_primetest/
durch ... und falls Dir das noch nicht reicht, in
http://directory.google.com/Top/Science/Math/Number_Theory/Factoring/?tc=1
sind noch mehr Links ...
>Nachdem ein Bekannter mühsam und ziemlich vergeblich versucht
>hat mir beizubringen, was es mit der Ordnung eines Algorithmus auf sich
>hat, ist mir die Bedeutung bei der Faktorisierung ziemlich schnell klar
>geworden.
Das möchte ich aber doch sehr bezweifeln ...
> Ich brauche halt immer praktische Beispiele, um mir abstrakte
>Sachverhalte tatsächlich merken zu können. Alles andere plätschert einfach
>so an mir vorbei.
siehe oben ...
Mfg
Hermann
--
>
>Hans-Peter
Edgar Fuß
elliptischen Kurven auf eine Art erklärt, die man ohne Grundstudium
verstehen kann?
Edgar Fuß
>vernagelten Fachidioten in ihrem Elfenbeinturm <g> nie eingefallen wäre.
Es ändert aber nichts an der Tatsache, daß Primzahltest und Faktorisierung
zwei unterschiedliche Probleme sind. Das wird einfach dadurch gezeigt, daß
es Verfahren gibt, die das eine, aber nicht das andere leisten.
Edgar Fuß
>Aussagen stark gegen Null.
soll. Nebenbei finde ich es leider erschreckend, daß ein Informatiker
nicht in der Lage ist, nachzuvollziehen, daß Faktorisierung und
Primalitätstest verschiedene Probleme sind, selbst, wenn man ihm einen
Algorithmus vorsetzt, der offenbar das eine, nicht aber das andere
leistet. Oder, daß er nicht einsieht, daß man beweisen kann, daß eine Zahl
zusammengesetzt ist, ohne einen Teiler zu finden, oder, daß man Teiler
finden kann, ohne explizit Teilbarkeit zu testen.
Also nochmal: Für alle Primzahlen p und alle natürlichen Zahlen a gilt,
daß a^p-a durch p teilbar ist (der Beweis hierzu dürfte sich bei Bedarf
selbst einem Informatiker in einer halben Stunde erklären lassen). Wenn Du
also ein a findest, so daß a^n-a nicht durch n teilbar ist, dann ist damit
bewiesen, daß n nicht prim ist. Einen Teiler liefert das natürlich nicht.
Algorithmisch wird man übrigens so vorgehen, daß man a^(n-1) ausrechnet,
indem man anhand der Binärdarstellung von n-1 sukzessive schiebt und mit a
multpliziert und dabei in jedem Schritt modulo n reduziert; am Ende muß
dann Eins herauskommen.
>Sehr schön, wie Du Deine fachliche Kompetenz gleich zu Anfang
>unter Beweis stellst ;-)
Ich habe im Gegenteil mehrfach betont, daß ich mich auf diesem Gebiet nur
ganz rudimentär auskenne. In der Tat bin ich letztens, um Dir ein Beispiel
für ein Faktorisierungsverfahren, das nicht einfach Teiler durchprobiert,
extra in's Institut gefahren, um jemanden zu fragen, der sich besser damit
auskennt (der Faktorisierungsexperte, der mir erschöpfend über den Stand
der Forschung Auskunft hätte geben können, war leider gerade nicht da).
Hans-Peter Diettrich
EF>also ein a findest, so daß a^n-a nicht durch n teilbar ist, dann ist
EF>damit bewiesen, daß n nicht prim ist. Einen Teiler liefert das
EF>natürlich nicht.
Gut, ich akzeptiere reumütig, daß hier kein Teiler herauskommt. Wenngleich
ich einem cleveren Mathematiker zutrauen würde, irgendwann doch noch
herauszufinden, wie man aus a und n einen Teiler berechnen kann ;-)
Was die Brauchbarkeit dieses Algorithmus in der Praxis angeht, da hege ich
allerdings noch gewisse Zweifel. Wieviele a muß man denn durchprobieren,
um
feststellen zu können, daß n keine Primzahl ist? Geht das wirklich
schneller (mit niedrigerer Ordnung) als stupides Dividieren durch alle in
Frage kommenden Teiler von n? Mir fällt jedenfalls keine obere Schranke
für
a ein, nicht mal ein Verfahren zur Aufzählung...
Hans-Peter
Hans-Peter Diettrich
HK>Dann röste hier nicht rum und lies Dir lieber erst mal
Danke für die vielen Links, aber bringen die wirklich was, bezüglich der
Ordnung der Algorithmen?
>hat, ist mir die Bedeutung bei der Faktorisierung ziemlich schnell klar
>geworden.
HK>Das möchte ich aber doch sehr bezweifeln ...
Ich bezweifle meinerseits, daß viele Mathematiker das wirklich begriffen
haben, zumindest diejenigen die kein Problem mit der Ordnung eines
Algorithmus sehen. Zum Öffnen einer Dose reicht es in der Praxis nun mal
nicht, wenn man ausgeht von "angenommen die Dose sei offen", und aufhört
mit "das Problem ist lösbar" ;-)
Hans-Peter
Edgar Fuß
wenig aus, um zu wissen, ob es vernünftige deterministische Algorithmen
gibt. Aber es ging ja nur ums Prinzip.
Praktisch ist es übrigens egal, daß der Algorithmus probabilistisch ist.
Wenn Du die Irrtumswahrscheinlichkeit auf 2^-100 oder sowas
heruntergehandelt hast, dann ist es viel wahrscheinlicher, daß sich der
Computer beim deterministischen Algorithmus verrechnet hat oder sich zwei
Meter über Dir spontan ein Walfisch materialisiert.
Hermann Kremer
>Hi Hermann,
>
>HK>Dann röste hier nicht rum und lies Dir lieber erst mal
Hi,
>Danke für die vielen Links, aber bringen die wirklich was, bezüglich der
>Ordnung der Algorithmen?
Ja, dort wird u.a. die Komplexität der Algorithmen betrachtet.
>>hat, ist mir die Bedeutung bei der Faktorisierung ziemlich schnell klar
>>geworden.
>
>HK>Das möchte ich aber doch sehr bezweifeln ...
>
>Ich bezweifle meinerseits, daß viele Mathematiker das wirklich begriffen
>haben, zumindest diejenigen die kein Problem mit der Ordnung eines
>Algorithmus sehen.
Diejenigen Mathematiker, die über Algorithmentheorie und
Berechenbarkeitstheorie arbeiten, haben es wirklich begriffen ...
und für diese Mathematiker sind 10-stellige Zahlen total uninteressant,
spannend wird es bei Zahlen mit >= 100 Stellen ...
> Zum Öffnen einer Dose reicht es in der Praxis nun mal
>nicht, wenn man ausgeht von "angenommen die Dose sei offen", und aufhört
>mit "das Problem ist lösbar" ;-)
Yep, den Witz kenne ich auch ;-))
Gruß
Hermann
--
>
>Hans-Peter
Hermann Kremer
> Hi Hermann,
>
> Danke f? die vielen Links, aber bringen die wirklich was, bez?lich der
> Ordnung der Algorithmen?
Hatte ich vergessen: Wenn Du mal mit einem einigermaßen schnellen
Algorithmus zur Faktorisierung spielen willst, dann schau Dir mal
das ECM-Applet (Elliptic Curve Method) von Dario Alpern in Buenos
Aires auf http://www.alpertron.com.ar/ENGLISH.HTM an; den Java-
Quellcode kannst Du Dir auch herunterladen. Dieses Applet
faktorisiert bis zu 1000-stellige Zahlen ...
Gruß
Hermann
--
Hans-Peter Diettrich
EF>Praktisch ist es übrigens egal, daß der Algorithmus probabilistisch
EF>ist.
Dann kann ich genausogut eine Münze werfen.
EF>Wenn Du die Irrtumswahrscheinlichkeit auf 2^-100 oder sowas
EF>heruntergehandelt hast,
Und wann bitte wird diese Grenze erreicht, oder irgend eine andere?
Vermutlich nicht vor dem Ende des Universums :-(
Hans-Peter
Edgar Fuß
fällt.
>Und wann bitte wird diese Grenze erreicht [...]?
Nach hundert Tests mit zufälligen Zahlen a. Wenn Du Dir etwas Mühe bei der
Wahl der a gibst, viel früher.
Uwe Ziemke
HPD> Was die Brauchbarkeit dieses Algorithmus in der Praxis angeht,
HPD> da hege ich allerdings noch gewisse Zweifel. Wieviele a muß man
HPD> denn durchprobieren, um feststellen zu können, daß n keine
HPD> Primzahl ist? Geht das wirklich schneller (mit niedrigerer
HPD> Ordnung) als stupides Dividieren durch alle in Frage kommenden
HPD> Teiler von n? Mir fällt jedenfalls keine obere Schranke für a
HPD> ein, nicht mal ein Verfahren zur Aufzählung...
Eine obere Schranke ist zumindest n.
a^n - a teilbar durch n
genau dann wenn (a+n)^n - (a+n) teilbar durch n.
Beweis:
(a+n)^n - (a +n) teilbar durch n
<=>
(a+n)^n - a teilbar durch n
<=>
(a+n)^n - a teilbar durch n
<=>
n /n\
Sigm| |(a^i)(n^(n-i)) -a teilbar durch n
i=0\i/
<=>
n /n\
Sigm| |(a^i)(n^(n-i)) -a teilbar durch n
i=n\i/
<=>
/n\
| |(a^n)(n^0) -a teilbar durch n
\n/
<=>
a^n - a teilbar durch n
qed.
Moin moin
Uwe
Hans-Peter Diettrich
>Und wann bitte wird diese Grenze erreicht [...]?
EF>Nach hundert Tests mit zufälligen Zahlen a.
Dazu würde mich eine etwas exaktere Berechnung interessieren. Zumindest
solltest Du nachweisen, daß Deine Angabe unabhängig ist von der zu
testenden Zahl. Und selbst dann wäre der Test für kleine Zahlen (n<100)
verdammt schlecht, wenn er nach 100 Tests immer noch kein sicheres
Ergebnis
liefert ;-)
Hans-Peter
Hans-Peter Diettrich
EF>Nein. Du wirst keine Münze haben, die bei Primzahlen garantiert auf
EF>Kopf fällt.
Nicht garantiert, aber mit einer ähnlichen Wahrscheinlichkeit wie die
anderer Tests.
Bei einer Münze weiß ich zumindest, daß die durchschnittliche Fehlerrate
50% nicht übersteigt. Andere Test dürften da wesentlich schlechter
abschneiden, falls sich überhaupt eine Fehlerrate berechnen läßt.
Hans-Peter
Hans-Peter Diettrich
UZ>Eine obere Schranke ist zumindest n.
Damit hätte dieser Test die Ordnung O(n). Dann ist aber das Dividieren
durch alle möglichen Faktoren mit der Ordnung O(log(n)) schon um
Größenordnungen schneller!
Grüße aus dem sonnigen Flensburg :-)
Hans-Peter
P.S.: Heute hat uns das Sauwetter auch erwischt :-(
Hermann Kremer
>
>UZ>Eine obere Schranke ist zumindest n.
>
>Damit hätte dieser Test die Ordnung O(n). Dann ist aber das Dividieren
>durch alle möglichen Faktoren mit der Ordnung O(log(n)) schon um
>Größenordnungen schneller!
Hää? Gemäß Primzahlensatz
http://mathworld.wolfram.com/PrimeNumberTheorem.html
gibt es für hinreichend großes n etwa n/ln(n) Primzahlen p < n, und da man
nur p <= sqrt(n) prüfen muß, hat ein solcher Test eine Komplexität von
O(sqrt(n)/ln(n)) > O(ln(n)) ... zumindest bei interessanten Zahlen:
http://perso.wanadoo.fr/yves.gallot/primes/chrrcds.html
Gruß
Hermann
--
Edgar Fuß
zusammengesetztem n die Differenz a^n-a für ein zufällig gewähltes a durch
n teilbar ist, kleiner als 1/2 ist.
Im übrigen gehört es zum Wesen probabilistischer Test, daß sie nach jeder
endlichen Zahl von Schritten eine nichtverschwindende
Irrtumswahrscheinlichkeit haben. Für kleine Zahlen sieht man sowieso in
Tabellen nach.
Hans-Peter Diettrich
HK>gibt es für hinreichend großes n etwa n/ln(n) Primzahlen p < n,
HK>und da man nur p <= sqrt(n) prüfen muß, hat ein solcher Test eine
HK>Komplexität von O(sqrt(n)/ln(n)) > O(ln(n)) ... zumindest bei
HK>interessanten Zahlen:
Danke für die Korrektur von log(n) auf ln(n). Auch mit p <= sqrt(n) bin
ich
einverstanden, aber bei n/ln(n) habe ich zumindest einen praktischen
Einwand: wie soll die Aufzählung der Primzahlen erfolgen?
Da es keinen Algorithmus für diese Aufzählung gibt, zumindest keinen mit
einer brauchbaren Ordnung, käme nur eine Liste von Primzahlen in Frage.
Diese Liste muß aber auch erst erzeugt werden, womit sich die Katze in den
Schwanz beißt :-(
Gäbe es so einen Algorithmus, der sich noch dazu mit einem Startwert
versorgen läßt, dann wäre der Primzahl-Test ganz einfach: Man starte mit
n-1, lasse die nächste Primzahl ermitteln, und wenn diese gößer als n ist,
dann ist n keine Primzahl.
Hans-Peter
Hermann Kremer
>Hi Hermann,
Hi Hans-Peter,
>HK>gibt es für hinreichend großes n etwa n/ln(n) Primzahlen p < n,
>HK>und da man nur p <= sqrt(n) prüfen muß, hat ein solcher Test eine
>HK>Komplexität von O(sqrt(n)/ln(n)) > O(ln(n)) ... zumindest bei
>HK>interessanten Zahlen:
>
>Danke für die Korrektur von log(n) auf ln(n). Auch mit p <= sqrt(n) bin
>ich einverstanden, aber bei n/ln(n) habe ich zumindest einen praktischen
>Einwand: wie soll die Aufzählung der Primzahlen erfolgen?
... gar nicht ...
>Da es keinen Algorithmus für diese Aufzählung gibt, zumindest keinen mit
>einer brauchbaren Ordnung, käme nur eine Liste von Primzahlen in Frage.
>Diese Liste muß aber auch erst erzeugt werden, womit sich die Katze in den
>Schwanz beißt :-(
Nein, muß sie nicht ... die Primzahlabschätzung des Primzahlsatzes
pi(n) ~= n/ln(n) bzw.
pi(n) ~= li(n) [Integrallogarithmus]
kann man rein mathematisch beweisen, ohne die PZ zählen zu müssen. Der
Beweis ist aber ziemlich kompliziert und wurde 1896 unabhängig voneinander
von Charles de la Vallée Poussin und von Jaques Hadamard auf unterschiedliche
Art geführt. Mittlerweile gibt es noch einige andere Beweise (Skewes, Erdös).
http://mathworld.wolfram.com/PrimeNumberTheorem.html
http://mathworld.wolfram.com/PrimeCountingFunction.html
Das sind natürlich keine exakten Formeln, sondern asymptotische
Abschätzungen:
lim{n->oo} pi(n)/(n/ln(n)) = 1, lim{n->oo} pi(n)/li(n) = 1 .
Nochmals - ohne eine ganz gehörige Menge an Kenntnissen in der Zahlentheorie
kommst Du hier nicht weiter ...
Grüße
Hermann
--
Hans-Peter Diettrich
>Einwand: wie soll die Aufzählung der Primzahlen erfolgen?
HK>... gar nicht ...
Siehst Du denn wirklich nicht, was daraus folgt?
Wenn es bis n nur n/ln(n) Primzahlen gibt, dann ist das zwar eine
interessante Erkenntnis, die aber bei der Primzahl-Prüfung bzw.
Faktorisierung überhaupt nichts bringt. Solange diese Primzahlen nicht
aufzählbar sind, bleibt nach wie vor nichts anderes übrig, als /alle/
möglichen Teiler durchzuprobieren, und das sind sqrt(n), abzüglich ein
paar
einfach auszuschließender Teiler (Vielfache von 2...).
HK>Nochmals - ohne eine ganz gehörige Menge an Kenntnissen in der
HK>Zahlentheorie kommst Du hier nicht weiter ...
Die Theorie braucht man hier wirklich nicht, um die praktischen
Konsequenzen zu erkennen.
Hans-Peter
Hermann Kremer
>Hi Hermann,
Hallo,
>>Einwand: wie soll die Aufzählung der Primzahlen erfolgen?
>
>HK>... gar nicht ...
>
>Siehst Du denn wirklich nicht, was daraus folgt?
Doch ...
>Wenn es bis n nur n/ln(n) Primzahlen gibt, dann ist das zwar eine
>interessante Erkenntnis, die aber bei der Primzahl-Prüfung bzw.
>Faktorisierung überhaupt nichts bringt. Solange diese Primzahlen nicht
>aufzählbar sind, bleibt nach wie vor nichts anderes übrig, als /alle/
>möglichen Teiler durchzuprobieren, und das sind sqrt(n), abzüglich ein
>paar einfach auszuschließender Teiler (Vielfache von 2...).
... und daraus folgt, daß man die Primalität eben nicht mittels
Probedivisionen, sondern z.B. mittels des kleinen Fermat'schen
Satzes (für Teilbarkeit) oder des Proth'schen Satzes (für Primalität)
oder der Methode der Elliptischen Kurven (ECM) für beides prüft ...
und die sind alle deterministisch und im wesentlichen O(log(n)^O(log(n))) ...
>HK>Nochmals - ohne eine ganz gehörige Menge an Kenntnissen in der
>HK>Zahlentheorie kommst Du hier nicht weiter ...
>
>Die Theorie braucht man hier wirklich nicht, um die praktischen
>Konsequenzen zu erkennen.
Doch, die braucht man ...
Gruß
Hermann
--
>
>Hans-Peter
Hans-Peter Diettrich
HK>und die sind alle deterministisch und im wesentlichen
HK>O(log(n)^O(log(n))) ...
...liefern aber AFAIK alle nicht das gewünschte Ergebnis.
Der Unterschied zwischen notwendig und hinreichend sollte einem
Mathematiker doch bekannt sein? Wenn eine Zahl solch einen Test besteht,
dann ist lediglich eine notwendige Bedingung erfüllt, aber noch lange
keine
hinreichende.
Schau Dir mal das Java Applet an, wieviele verschieden Methoden da
durchprobiert werden, in der Hoffnung daß irgendeine davon zu einem
brauchbaren Ergebnis kommt, in einer Zeit die wir noch erleben werden.
Hans-Peter
Hermann Kremer
>Hi Hermann,
Hi
>HK>und die sind alle deterministisch und im wesentlichen
>HK>O(log(n)^O(log(n))) ...
>
>...liefern aber AFAIK alle nicht das gewünschte Ergebnis.
... doch ... ich hatte absichtlich d e t e r m i n i s t i s c h geschrieben ...
Probabilistische Tests sind sehr viel weniger rechenintensiv als
deterministische und reichen für Kryto-Anwendungen völlig aus.
>Der Unterschied zwischen notwendig und hinreichend sollte einem
>Mathematiker doch bekannt sein? Wenn eine Zahl solch einen Test besteht,
>dann ist lediglich eine notwendige Bedingung erfüllt, aber noch lange
>keine hinreichende.
Der Unterschied ist mir bekannt ...
Wenn eine Zahl p beim Fermat-Test "durchfällt", dann ist sie
notwendigerweise und hinreichenderweise zusammengesetzt.
Wenn eine Zahl p den Fermat-Test besteht, dann ist sie entweder
eine Primzahl oder eine (Carmichael-)Pseudoprimzahl.
Wenn eine Zahl p beim Proth-Test "durchfällt", dann ist sie
notwendigerweise und hinreichenderweise zusammengesetzt.
Wenn eine Zahl p den Proth-Test besteht, dann ist sie
notwendigerweise und hinreichenderweise eine Primzahl.
>Schau Dir mal das Java Applet an, wieviele verschieden Methoden da
>durchprobiert werden, in der Hoffnung daß irgendeine davon zu einem
>brauchbaren Ergebnis kommt, in einer Zeit die wir noch erleben werden.
Wenn Du das Applet von Dario Alpern meinst: Damit wird eine Zahl
f a k t o r i s i e r t (in ihre Primfaktoren zerlegt), und das ist was völlig
anderes als eine Prüfung auf Primalität.
Nochmals: man kann die Primalität einer Zahl prüfen, o h n e nach deren
Primfaktoren zu suchen, und wie ganz vor kurzem Agrawal, Kayal und
Saxena gezeigt haben, geht das d e t e r m i n i s t i s c h schlimmstenfalls
in O(log_2(n)^12) und, falls eine (noch unbewiesene) Vermutung richtig
ist, in O(log_2(n)^6), also jedenfalls in P-Komplexität.
Gruß
Hermann
--
>Hans-Peter
Hermann Kremer
[ ... ]
Und hier ist auch ein Link zu Agrawal-Kayal-Saxena (AKS) mit
Code-Schnipseln in verschiedenen Programmiersprachen:
http://fatphil.org/maths/AKS/
Gruß
Hermann
--
> Hans-Peter
Uwe Ziemke
Hallo Hans-Peter,
HPD> Gibt es noch mehr "einfache" Formen für Primzahlen, außer (2^n - 1)?
Obwohl ich nicht glaube, daß es Dir wirklich weiterhilft, ein Text
den ich mal gefunden habe:
o
___________\/_____
/\
o
Absender : Gunther Piez @ Fido 2:2455/305.2
Betreff : PRIMZAHLPOLYNOM
Datum : Do 15.08.96, 11:37 (erhalten: 20.08.96)
SS>>> Primzahlen sind nach derzeitigem Kenntnisstand der Mathematik nicht
SS>>> berechenbar.
GP>> es gibt sogar ein Polynom, das als ganzzahlige Lösungen _alle_ Primzahlen
GP>> und negative Zahlen hat.
SS> _SOFORT_ _POSTEN_! _VOLLSTÄNDIG_!
SS> Das will & muß ich sehen, erstens, bevor ich's glaube, und zweitens, damit
SS> ich's nachkontrollieren kann! ]:->=>
Da dies die zehnte Mail dieser Art ist, die mich erreicht, werde ich es
ausnahmsweise mal vollständig posten.
SS> (Vorher kann ich's _NICHT_ glauben - ein _Polynom_, das _alle_ Primzahlen
SS> liefern kann, müßte entweder alle gängigen Ansichten über den Haufen
SS> schmeißen und die Cryptographen zur Verzweiflung treiben, oder es müßte
SS> unendlich viele Koeffizienten haben - die sich aus den Primzahlen
SS> ergeben...)
Warum? Die Kryptographen hätten höchstens ein Problem, wenn das Polynom eine
Faktorisierung bei großen Primfaktoren erlauben würde.
Ich zitiere: 'Wenn S eine aufzaehlbare Menge ist, dann gibt es ein Polynom
P(k,x1,x2,...) mit ganzzahligen Koeffizenten, dass eine Zahl k genau dann
Element von S ist, wenn die diophantische Gleichung P=0 eine Loesung besitzt.
Die Menge der Primzahlen ist beispielweise eine aufzaehlbare Menge. [...]
Ungluecklicherweise impliziert das von Matijasevic erzielte Ergebnis [obiger
Satz] nur die Existenz eines solchen Primzahlerzeugenden Polynoms. [...] Und
so waren betraechtliche Anstrengungen erforderlich bevor es [...] gelang,
dieses Polynom zu finden. Es besitzt 26 Variablen und ist vom Grad 25:
(k+2){1-[wz+h+j-q]²
-[(gk+2g+k+1)(h+j)+h-z]²
-[2n+p+q+z-e]²
-[16(k+1)^3(k+2)(n+1)²+1-f²]²
-[e^3(e+2)(a+1)²+1-o²]²
-[(a²-1)y²+1-x²]²
-[16r²y^4(a²-1)+1-u²]²
-[((a-u²(u²-a))²-1)(n+4dy)²+1-(x+cu)²]²
-[n+l+v-y]²
-[(a²-1)l²+1-m²]²
-[ai+k+1-l-i]²
-[p+l(a-n-1)+b(2an+2a-n²-2n-2)-m]²
-[q+y(a-p-1)+s(2ap+2a-p²-2p-2)-x]²
-[z+pl(a-p)+t(2ap-p²-1)-pm]²}.
Bitte beachten Sie das scheinbare Paradoxon, dass die Formel in zwei sehr
ungleiche Faktoren zerfaellt. Dies erfuellt jedoch einen Zweck: Die Formel
erzeugt ausschliesslich positive Werte, wenn der Faktor k+2 eine Primzahl ist
und der zweite Faktor gleich 1 ist.', Davis, Robinson, Putnam, Matijasevic,
Jones, Sato, Wada und Wiens, 1977 aus 'Sternstunden der modernen Mathematik',
Keith Devlin, dtv wissenschaft.
Steht übrigens auch im Jahrbuch der Mathematik 1984.
Wirklich praktisch, daß das Alphabet 26 Buchstaben hat. Ich hoffe, alle
Klarheiten sind jetzt beseitigt. :-)
BTW, wenn du eine Lösung mit k>0 findest, _sofort posten_ :-)
o
___________\/_____
/\
o
Moin moin
Uwe
Edgar Fuß
Hans-Peter Diettrich
UZ>Obwohl ich nicht glaube, daß es Dir wirklich weiterhilft, ein Text
UZ>den ich mal gefunden habe:
Toll, was es so alles gibt :-)
In der Tat hilft mir das (momentan) nicht viel weiter, aber ich werde
diese
Formel gut aufbewahren, für lange trostlose Winternächte ;-)
Hans-Peter
Hans-Peter Diettrich
EF>Der Unterscheid zwischen probabilistisch und deterministisch sollte
EF>einem Informatiker doch bekannt sein?
Jein. Bei einem deterministischen Test erwarte ich eigentlich ein
eindeutiges Ergebnis, ohne unterschiedliche Interpretationen für bestanden
und nicht bestanden. Der Fermat-Test erfüllt diese Annahme jedenfalls
nicht. Den Proth-Test werde ich mir mal näher anschauen, doch nach dem
ersten Eindruck (Ansatz) ist der genauso probabilistisch wie der
Fermat-Test.
Hans-Peter
Hermann Kremer
>Hans-Peter Diettrich schrieb in Nachricht <200209052...@nf.maus.de>...
[ ... ]
Nochmals: man kann die Primalität einer Zahl prüfen, o h n e nach deren
Primfaktoren zu suchen, und wie ganz vor kurzem M. Agrawal, N. Kayal und
N. Saxena gezeigt haben, geht das d e t e r m i n i s t i s c h schlimmstenfalls
in O(log_2(n)^12) und, falls eine (noch unbewiesene) Vermutung über
Sophie-Germain'sche Primzahlen richtig ist, in O(log_2(n)^6), also jedenfalls
in P-Komplexität.
Hermann Kremer
>Hi Edgar,
>
>EF>Der Unterscheid zwischen probabilistisch und deterministisch sollte
>EF>einem Informatiker doch bekannt sein?
>
>Jein. Bei einem deterministischen Test erwarte ich eigentlich ein
>eindeutiges Ergebnis, ohne unterschiedliche Interpretationen für bestanden
>und nicht bestanden. Der Fermat-Test erfüllt diese Annahme jedenfalls
>nicht.
Stimmt wegen der Pseudo-Primzahlen, die er falsch-positiv als PZ meldet.
>Den Proth-Test werde ich mir mal näher anschauen, doch nach dem
>ersten Eindruck (Ansatz) ist der genauso probabilistisch wie der
>Fermat-Test.
Falsch - der ist deterministisch, deterministischer geht es nicht - er
ist allerdings nicht auf jede beliebige Zahl anwendbar ...
Falls Du noch weitere d e t e r m i n i s t i s c h e PZ-Tests möchtest, dann
suche mal nach Adleman-Pomerance-Rumeley (APR) oder
Cohen-A.K.Lenstra (CL); und eine Suche nach Lenstra-Lenstra-Lovász (LLL)
könnte vielleicht auch ganz nützlich sein.
Einen Link auf Agrawal-Kayal-Saxena (AKS) hatte ich ja schon gepostet.
Aber Achtung: APR, CL, LLL, AKS sind r e i n e M a t h e m a t i k ...
Gruß
Hermann
--
>
>Hans-Peter
Hermann Kremer
>Und hier ist auch ein Link zu Agrawal-Kayal-Saxena (AKS) mit
>Code-Schnipseln in verschiedenen Programmiersprachen:
>http://fatphil.org/maths/AKS/
und hier ist noch einer:
http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html
http://crypto.cs.mcgill.ca/%7Estiglic/PRIMES_P_FAQ.html
Gruß
Hermann
--
Edgar Fuß
Hans-Peter Diettrich
HK>Primfaktoren zu suchen, und wie ganz vor kurzem M. Agrawal, N. Kayal und
HK>N. Saxena gezeigt haben, geht das d e t e r m i n i s t i s c h
HK>schlimmstenfalls
HK>in O(log_2(n)^12)
Ja, das habe ich vor kurzem <g> selbst gelesen. Jetzt haben wir also
endlich eine zufriedenstellende Antwort auf die vor Wochen aufgeworfenen
Fragen.
Der Algorithmus ist eigentlich recht "primitiv", und kommt auch nicht ohne
Faktorisierung und lineare Suche nach Primzahlen (1 < r < 64ld(n)^2) aus.
Raffiniert ist lediglich der Beweis für die obere Schranke in den beiden
Schleifen.
Eines ist mir an der obigen Formel noch nicht ganz klar, und zwar das O,
das ja im Originaltext etwa als ~O dasteht, mit
~O(t(n)) = O(t(n)poly(log(t(n))))
definiert ist. Wofür steht das poly(...)? Für ein Polynom?
Hans-Peter
Hans-Peter Diettrich
Zum Proth-Test:
HK>Falsch - der ist deterministisch, deterministischer geht es nicht -
HK> er ist allerdings nicht auf jede beliebige Zahl anwendbar ...
Gut, das ist ein Spezialfall: bedingt deterministisch ;-)
HK>Aber Achtung: APR, CL, LLL, AKS sind r e i n e M a t h e m a t i k
HK>...
Das ist mir schon klar. Die Mathematik glaube ich einfach mal, die wird ja
lediglich zum Beweis der Richtigkeit der Algorithmen benötigt. Das
entspricht ziemlich genau den Wegwerf-Programmen in der Informatik, die man
nur einmal braucht, und dann nie wieder einsetzen muß ;-)
Schaut man sich aber die Algorithmen an, dann braucht man für deren
Verständnis keine besonderen mathematischen Kenntnisse. Die größte Hürde
stellen für mich die mathematischen Zeichen dar, und die eingestreuten
Faktoren. So kann ich z.B. nur vermuten, daß log^2n nicht für
Zweier-Logarithmus steht, sondern für log(n)^2...
Da ich mich gerade auch mit anderen Dokumentationen mit mathematischen
Notationen befasse:
Gibt es irgendeine handliche Beschreibung für die Symbole, die in
mathematischen und ähnlichen (logischen...) Formeln verwendet werden?
Dafür müßte es doch einen internationalen Standard geben?
Wo kann ich den bekommen?
Hans-Peter