Diskussion:AKS-Primzahltest

Es gibt dazu einen Artikel in Telepolis: [1] -- Dishayloo [ +] 10:20, 8. Aug 2005 (CEST)

Frage zur Schreibweise bei der Laufzeit

Was bedeutet die Schreibweise $\log ^{12+\epsilon }n$? Das gleiche wie $(\log n)^{12+\epsilon }$, oder steckt da was anderes dahinter? -- srb ^♋ 22:10, 12. Aug 2005 (CEST)

Genau das. Da steckt nicht mehr dahinter. Außer vielleicht, daß $\log n$ die Anzahl der Stellen von n ist. -- MlaWU 23:11, 12. Aug 2005 (CEST)

log n ist schon klar, mich hat nur die Schreibweise mit dem Exponenten vor dem Argument gewundert - ist zwar kürzer und vielleicht sogar übersichtlicher als mit Klammer und Exponent drum rum, aber ich wüßte nicht, dass ich das schon mal gesehen habe (zumindest nicht bewußt). Ist das eine übliche Schreibweise, die vielleicht sogar irgendwo erklärt ist? Wenn nicht, dann sollte das irgendwo rein - vielleicht in Logarithmus - oder gibt es einen speziellen Sammelartikel für Kurzschreibweisen? -- srb ^♋ 00:01, 13. Aug 2005 (CEST)

Für Logrithmen sieht man das tatsächlich nur eher selten. Für Winkelfunktionen ist es aber auf jeden Fall üblich. Zumindest das Schema sollte also allgemein bekannt sein. -- MlaWU 00:16, 13. Aug 2005 (CEST)

Hmm, bei Winkelfunktionen ist es wirklich häufiger, da wäre es mir wohl gleich klar gewesen. Aber da ich ins Straucheln gekommen bin, und tatsächlich erst etwas überlegen mußte bis ich auf die "Lösung" gekommen bin, sollte man es im Artikel vielleicht doch mit Klammer schreiben. Immerhin richtet sich so ein Artikel ja nicht ans "Fachpublikum", sondern auch und vor allem an den Durchschnittsleser - und da sollte man m.E. im Zweifelsfall etwas konservativer schreiben. -- srb ^♋ 00:45, 13. Aug 2005 (CEST)

Ich habe es jetzt einfach mal geändert. -- MlaWU 13:07, 13. Aug 2005 (CEST)

Interessant wäre in diesem Zusammenhang natürlich die aktuellste Verbesserung der originalen Laufzeitschranke $O(l^{12+\varepsilon })$. Kennt die jemand?--JFKCom 22:04, 13. Aug 2005 (CEST)

Hab grade bei Mathworld deswegen reingeschaut, da ist von einer Reduzierung $O(ln^{6+\varepsilon }n)$ die Rede, wenn man gewisse Unsicherheiten für ein falsches Ergebnis akzeptiert sogar $O(ln^{4+\varepsilon }n)$ - Stand 2003. -- srb ^♋ 00:52, 14. Aug 2005 (CEST)

Nichts für ungut. Aber es sollte wohl epsilon darin erklärt werden. Wofür steht es? Wunderknabe 00:15, 26. Aug 2006 (CEST)

Frage zum Lemma

Ich vermute in $(x+a)^{n}\equiv x^{n}+a\mod N$ muss n durch N ersetzt werden. Über das n ist nichts gesagt wir könnten es gleich 0 oder 1 wählen und hätten wir Nullaussagen. Ach ich ersetzte das mal.--ThiloHarich 12:33, 17. Jan. 2007 (CET)

mod (x^r-1,N)

Die mod Geschichte ist etwas komisch. Im zitierten Artikel http://www-m3.ma.tum.de/m3old/ftp/Bornemann/pdf/aks.pdf wird mod (x^r-1,N) geschrieben hier lautet die Notation: $(x+a)^{N}\ ({\text{mod }}x^{r}-1,N)$ und das ohne Erklärung. Ich vermute mal s = t mod (x^r-1,N) <-> (s mod x^r-1) mod N = (t mod x^r-1) mod N?--ThiloHarich 12:47, 17. Jan. 2007 (CET)

Die ungewohnte Schreibweise $\equiv ({\text{mod }}x^{r}-1,N)$ ist leider erforderlich, weil $\mathbb {Z} [x]$ kein Hauptidealring ist. Somit bedeutet

$\not \equiv ({\text{mod }}x^{r}-1,N)$,

dass aus der Kongruenz

$\equiv ({\text{mod }}x^{r}-1)$

die Inkongruenz

$\not \equiv ({\text{mod }}N)$

folgen muss. Oder umgekehrt

$\equiv ({\text{mod }}x^{r}-1,N)\quad \Longleftrightarrow \quad \equiv ({\text{mod }}x^{r}-1)\;\land \;\equiv ({\text{mod }}N).$

–Nomen4Omen (Diskussion) 18:00, 4. Okt. 2020 (CEST)

Schlusssätze

Die letzten beiden Sätze des Artikels sind nicht gut verständlich: Welche Vermutung? Der letzte Satz braucht eine Erläuterung; "Ein Algorithmus mit geringerer Laufzeit könnte gefunden werden, wenn ..." Jonasclemens 00:01, 13. Feb. 2007 (CET)

n und/oder N ??

Die Verwendung von n und N führt zu Missverständnissen. Am Anfang sollte zumindest klar werden, was n bzw. N bedeutet, sonst könnte jemand auf die Idee kommen, N ist die Zahl die untersucht wird und n ist die Anzahl der Stellen der Zahl o.ä.

n=N, wenn keine weiteren Einsprüche kommen. --Zaph 23:46, 26. Sep. 2008 (CEST)

Macht keinen großen Unterschied, da die Anzahl der Stellen von der Größenordnung der Zahl ist, aber in der Regel ist n die Zahl der Stellen. Am Besten nimmt man aber p für die Zahl. --P. Birken 15:54, 27. Sep. 2008 (CEST)

p ist irgendwie auch nix, hab das alte wiederhergestellt. --P. Birken 16:18, 27. Sep. 2008 (CEST)

Im Abschnitt AKS-Primzahltest#Nach Agrawal, Kayal und Saxena kommt N 3mal vor und ist nicht erklärt, n kommt aber auch vor! Ein brauchbarer Beleg zu „Algorithmus von Lenstra und Pomerance“ fehlt, so dass man schwertut, die Bedeutung von N zu ergänzen. –Nomen4Omen (Diskussion) 19:36, 23. Sep. 2020 (CEST)

Epsilon

Wie groß ist denn jeweils das Epsilon? Kann das (wie üblich) beliebig klein gewählt werden? Wäre nett, wenn das jemand aufklären könnte. --Zaph 23:46, 26. Sep. 2008 (CEST)

Das würde ich auch gerne wissen. Im Originalpaper ist es nicht zu finden und unter Landau-Notation steht auch nichts. Oder ist es eine mathematische Formalität und ε verschwindet asymptotisch? — Toshiki^Disku 11:51, 28. Jul. 2014 (CEST)

Version des Algorithmus

Im Artikel wird die Version des Algorithmus aus [2] verwendet. In [3] ist eine verbesserte Version zu finden. Gibt es Gründe gegen den Ersatz durch die verbesserten Variante? -- Hanauska 09:40, 10. Jun. 2009 (CEST)

10 oder 12?

Laut diesem Artikel hatte das Original O(l^(10+epsilon)), laut Co-NP war es jedoch O(l^(12+epsilon)). Wie war es denn jetzt im Original? --Chricho 14:07, 29. Mai 2010 (CEST)

12 ist richtig (siehe [4], u.a. Seite 2). Ich korrigiere das mal. --Hanauska 17:41, 30. Mai 2010 (CEST)

In der Introduction des Papers steht $O^{\sim }(\log ^{15/2}n)$. Steht die Tilde für das Epsilon? Dann wäre es ja $O(\log ^{7.5+\varepsilon }n)$. --Jobu0101 (Diskussion) 10:41, 20. Apr. 2015 (CEST)

Tilde für das Epsilon: ^~O oder O^~

Im Orginal steht: „We use the symbol $O^{\sim }(t(n))$ for $O(t(n)\cdot {\text{poly}}(\log t(n)){\color {Red})}$, where $t(n)$ is any function of $n$.“ In primality_original steht: „We will use the symbol ${\tilde {O}}(t(n))$ for $O(t(n)\cdot {\text{poly}}(\log t(n)))$, where $t(n)$ is some function of $n$.“

Wenn $t(n)=\log ^{15/2}n$, kommt tatsächlich sowas Ähnliches wie $O(t(n)^{1+\varepsilon })$ heraus, nämlich $O(\log ^{15/2}n\cdot {\text{poly}}(\log \log ^{15/2}n))$. –Nomen4Omen (Diskussion) 19:31, 23. Sep. 2020 (CEST)

Bedeutung des X auch im Abschnitt 2 "Der Algorithmus" erklären

Die Bedeutung des x als Basis des Restklassenringes Z/nZ, wird nur klar, wenn auch der Abschnitt zur Entstehungsgeschichte gelesen wird. Ich denke es sollte jedoch auch möglich sein, den "endgültigen" Algorithmus zu verstehen, wenn nur der Abschnitt 2 ("Der Algorithmus") gelesen wird.

Siehe auch http://www.java-forum.org/mathematik/82523-bestimmung-x-n-x-n-mod-r.html

--Jev12 (Diskussion) 17:57, 28. Aug. 2012 (CEST)

Habe jetzt eine entsprechende Zeile in den Erläuterungen zum Algorithmus ergänzt.

--Jev12 (Diskussion) 17:00, 17. Nov. 2012 (CET)

Reine Potenz

Was ist eine "reine Potenz" (kommt ganz am Anfang des Algorithmus vor)? der Begriff ist in Wikipedia nicht erläutert. Falls damit gemeint ist Potenz einer ganzen Zahl mit ganzzahligen Exponent > 1 (1 wäre ja banal), schließt sich die Frage an, wie testet man das?--HeRoMa (Diskussion) 18:34, 2. Mär. 2015 (CET)

log

Zmindest im Algoritmus sollte die Basis des Logarithmus explizit oder implizit angegeben werden, ich vermute, es ist 2 und nicht 10 gemeint, also lb (binarius) statt log.--HeRoMa (Diskussion) 19:24, 2. Mär. 2015 (CET)

Im Wikipedia-Artikel https://de.wikipedia.org/wiki/Logarithmus heißt es, "In theoretischen Abhandlungen, insbesondere zu zahlentheoretischen Themen, steht log oft für den natürlichen Logarithmus." So wohl auch hier.--2003:6:331D:7B44:F98A:E52A:B1B8:B482 13:24, 26. Mai 2020 (CEST)

Laut Originalarbeit M. Agrawal, N. Kayal, N. Saxena: PRIMES is in P. ist es ld (dualis=binarius): „We use log for base 2 logarithm, and ln for natural logarithm.“ –Nomen4Omen (Diskussion) 12:19, 23. Sep. 2020 (CEST)

Laufzeitverhalten

Die Autoren schreiben:
Die Feststellung von

$(X+a)^{n}\equiv X^{n}+a\quad ({\text{mod }}(X^{r}\!-\!1),n)$

kostet $O(r^{2}\log ^{3}n)$. Dabei wird die linke Seite $(X+a)^{n}$ durch wiederholtes Quadrieren berechnet. Bei Schneller Fourier Multiplikation ist der Aufwand sogar nur $O(r\log ^{2}n)$.
Dabei werden die Multiplikationen durch die Kongruenz

$\equiv ({\text{mod }}(X^{r}\!-\!1))$

so stark vereinfacht, dass maximal $r$ Monome $X^{0},\ldots ,X^{r-1}$ zu bilden sind. Und $r$ verhält sich polynomial zu $n$. –Nomen4Omen (Diskussion) 18:07, 4. Okt. 2020 (CEST)

kleines Beispiel / Gegenbeispiel für Hilfssatz

In dem auf Freshman's Dream und dem Kleinen Fermatschen Satz basierenden Hilfssatz wird laut Lemma 2.1 im originalen Beweis schlicht jeder Koeffizient der Differenz (X+a)^n-(X^n+a) auf 0 modulo n getestet. Wäre es bitte möglich, dies in einem kleinen Beispiel (n=3) / Gegenbeispiel (n=4) zu illustrieren. Danke --2.247.251.203 10:05, 6. Mär. 2021 (CET)

Insbesondere scheint: "n ist genau dann keine Primzahl, wenn deren kleinster Teiler k die Ungleichung 1 < k < n erfüllt" nicht zu stimmen (weder für kgT noch für ggT). --2.247.251.203 11:35, 6. Mär. 2021 (CET)