# Programmierung des AKS - Primzahltests



## andreas2505 (3. Jan 2010)

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 (3. Jan 2010)

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 (3. Jan 2010)

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.


----------

