Warum schlägt der AKS-Test hier fehl?

07.07.2021, 20:48

ichbinneu

Warum schlägt der AKS-Test hier fehl?

Hallo ihr Lieben,

ich beschäftige mich gerade mit dem AKS-Test, aber er spuckt mir immer wieder 97 als zusammengesetzt aus.

Ich wähle $\begin{eqnarray*} a=1, n = 97, r = 59 \end{eqnarray*}$ . Das r ist korrekt gewählt, denn $\begin{eqnarray*} ord_{59}(97) > ld(97)^2 \end{eqnarray*}$ , alle kleineren Werte von r erfüllen das nicht.
Nun ist aber
$\begin{eqnarray*} (X + 1)^{97} \not\equiv X^{97} + 1 \pmod{97, X^{59} - 1} \end{eqnarray*}$ .

Aber das sollte doch bei einer Primzahl erfüllt sein? verwirrt

Wo ist mein Fehler?

08.07.2021, 13:21

Huggy

Auf diesen Beitrag antworten »

RE: Warum schlägt der AKS-Test hier fehl?
Wozu braucht man den AKS-Test? Wenn ich wissen will, ob $\begin{eqnarray*} n \end{eqnarray*}$ eine Primzahl ist, gebe ich einfach

code:
1:	PrimeQ[n]

in Mathematica ein. Big Laugh

Aber Spaß beiseite:

Zitat:

Original von ichbinneu
Nun ist aber
$\begin{eqnarray*} (X + 1)^{97} \not\equiv X^{97} + 1 \pmod{97, X^{59} - 1} \end{eqnarray*}$ .

Wie kommst du darauf? Mathematica ist da anderer Meinung.

code:
1: 2: 3: 4:	PolynomialMod[PolynomialRemainder[(X + 1)^97, X^59 - 1, X], 97] 1 + X^38 PolynomialRemainder[X^97 + 1, X^59 - 1, X] 1 + X^38

15.07.2021, 21:56

Malcang

Auf diesen Beitrag antworten »

Hallo Huggy,

bitte entschuldige die viel zu späte Antwort.
Ich danke dir vielmals für deinen Einwand, also den mit dem AKS-Test Big Laugh

Ich habe das ganze in Python implementiert und siehe da, die Binomialkoeffizienten waren selbst nach Reduktion noch falsch. Allerdings nur um die Differenz 4 verwirrt

Interessant zu wissen, aber ich habe es nun nochmal anders implementiert und es funktioniert.

Ich danke die vielmals smile