Programmierung des AKS - Primzahltests

[andreas2505]

Hallo,

ich benötige Hilfe bei der Implementierung des AKS - Primzahltests.
Hier erstmal der allgemeine Algorithmus:

Eingabe: n ℕ, n ≥ 2
Ausgabe: „n ist zusammengesetzt“ oder „n ist prim“

1: if (n ist von der Form , b > 1) then
2: „n ist zusammengesetzt“
3: end if
4: r := 2
5: while (r < n) do
6: if (ggT(n,r) ≠ 1) then
7: „n ist zusammengesetzt“
8: end if
9: if (  > 22) then
10: break;
11: end if
12: r := r+1
13: end while
14: for (a := 1 to 2 ⌊ () ∙ 2 ⌋) do
15: if ((x+a)^n ≢ ( x^n+a ) (mod x^r -1, n)) then
16: „n ist zusammengesetzt“
17: end if
18: end for
19: „n ist prim“

Mein Problem dabei ist, die Zeile 15 zu programmieren.
Hier muss ich ja ein Polynom modulo eines anderen Polynoms nehmen.
Ich krieg das nicht hin.
Ich habe bereits eine C++ variante (http://pagesperso-orange.fr/yves.gallot/src/aks.html) gefunden, aber die kann ich auch igendwie nicht in java übersetzen.
Vielleicht kann mir wer helfen, dass zu programmieren.

 

[Marco13]

Inline-Assembler ... Och, mit der BCEL - ließe sich da bestimmt was machen

Aber im Ernst: Da wird doch nicht auf Polynomen gerechnet, oder? Geht es nicht um den WERT, den das Polynom dort hat? ???:L

 

[andreas2505]

ich denke schon.
Ich weiß es aber auch nicht genau, deswegen dachte ich ja dass mir wer helfen kann.
ich muss ja (x+a)^n modulo x^r -1 und modulo n rechnen und dann mit x^n + a modulo x^r -1 und modulo n vergleichen.
Wäre echt super wenn mir hier mal wer sagt, wie das geht.
Wie gesagt es geht dabei um das AKS-Kriterium vom AKS-Primzahltest.
Vielleicht versteht ihr den besser.