Diskrete algebraische Methoden

i

i

“main”—2013/4/10—15:19—page124—#136

i

i

i

i

i

i

124 Primzahlerkennung in Polynomialzeit

Damit gilt 2

n

< kgV(n) für alle n ≥ 9. Es bleiben noch die Fälle n = 7 und n = 8

zu untersuchen. Dies weisen wir mit den folgenden Rechnungen direkt nach: 2

7

=

128 < 420 = kgV(7)

, 2

8

= 256 < 840 = kgV(8).

4.3 Von kleinen Zahlen und großen Ordnungen

Für ggT(n, r ) = 1 definieren wir ord

r

(n) als die Ordnung von n in der multiplikati-

ven Gruppe

(Z/rZ)

∗

,also

ord

r

(n) = min{i |i ≥ 1,n

i

≡ 1modr }

Bevor wir das eigentliche Verfahren vorstellen, beweisen wir ein technisches Lemma.

Dieses besagt, dass unter gewissen Vora ussetzungen stets eine kleine Zahl

r existiert,

so dass

ord

r

(n)