Ordnung von 2 modulo p

15.02.2023, 20:42

Malcang

Ordnung von 2 modulo p

Hallo mal wieder smile

ich beschäftige mich gerade mit der Frage, die multiplikative Ordnung von $\begin{eqnarray*} 2 \end{eqnarray*}$ modulo ungerade Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ zu bestimmen.
Nach dem Satz von Euler-Fermat weiß ich, dass $\begin{eqnarray*} 2^{p-1}\equiv 1\pmod p \end{eqnarray*}$ und nach Satz von Lagrange, dass $\begin{eqnarray*} ord_p(2)|p-1 \end{eqnarray*}$ .
Nun bilde ich $\begin{eqnarray*} 2^{\frac{p-1}{2}}\pmod p \end{eqnarray*}$ und schaue, ob ich dort -1 erhalte. Dann weiß ich, die Ordnung ist $\begin{eqnarray*} p-1 \end{eqnarray*}$ . Andernfalls führe ich das so weiter.
Gibt es Anforderungen an $\begin{eqnarray*} p \end{eqnarray*}$ , die mir das erleichtern? Ich habe mit ienem Skript festgestellt, dass die Werte $\begin{eqnarray*} p-1 \end{eqnarray*}$ und $\begin{eqnarray*} \frac{p-1}{2} \end{eqnarray*}$ überwiegen, aber mehr habe ich nicht erkannt verwirrt

16.02.2023, 08:57

HAL 9000

Auf diesen Beitrag antworten »

Nun, genau damit beschäftigt sich ja der zweite Ergänzungssatz des Quadratischen Reziprozitätsgesetzes: $\begin{eqnarray*} \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} \end{eqnarray*}$ , also $\begin{eqnarray*} \left(\frac{2}{p}\right) = -1 \end{eqnarray*}$ für $\begin{eqnarray*} p\equiv \pm 3\bmod 8 \end{eqnarray*}$ .

Allerdings teile ich nicht deine Ansicht, dass in diesem Fall stets auch $\begin{eqnarray*} \operatorname{ord}_p(2)=p-1 \end{eqnarray*}$ gelten muss:

Beispiel $\begin{eqnarray*} p=43 \end{eqnarray*}$ : Hier ist $\begin{eqnarray*} 2^{21}\equiv -1\bmod 43 \end{eqnarray*}$ , aber $\begin{eqnarray*} \operatorname{ord}_{43}(2)=14 \end{eqnarray*}$ .

Was du aus $\begin{eqnarray*} \left(\frac{2}{p}\right) = -1 \end{eqnarray*}$ lediglich sicher folgern kannst ist, dass $\begin{eqnarray*} \operatorname{ord}_p(2) = \frac{p-1}{q} \end{eqnarray*}$ gilt, wobei $\begin{eqnarray*} q \end{eqnarray*}$ ein ungerader Teiler von $\begin{eqnarray*} p-1 \end{eqnarray*}$ ist.

16.02.2023, 11:26

Malcang

Auf diesen Beitrag antworten »

Hallo HAL, danke für deine Zeit!

Zuerstmal zu deiner Anmerkung:

Zitat:

Original von HAL 9000
Allerdings teile ich nicht deine Ansicht, dass in diesem Fall stets auch $\begin{eqnarray*} \operatorname{ord}_p(2)=p-1 \end{eqnarray*}$ gelten muss:

Beispiel $\begin{eqnarray*} p=43 \end{eqnarray*}$ : Hier ist $\begin{eqnarray*} 2^{21}\equiv -1\bmod 43 \end{eqnarray*}$ , aber $\begin{eqnarray*} \operatorname{ord}_{43}(2)=14 \end{eqnarray*}$ .

Ja, das ist ein gutes Gegenbeispiel. Vielen Dank dafür. Mein Gedankengang war, dass aus $\begin{eqnarray*} 2^{p-1}\equiv 1\pmod 1 p \end{eqnarray*}$ ja $\begin{eqnarray*} 2^{\frac{p-1}{2}}\equiv\pm 1\pmod p \end{eqnarray*}$ folgt. Aber wie dein Beispiel zeigt, lande ich eben nicht nur mit der "Quadratwurzel" bei $\begin{eqnarray*} \pm 1 \end{eqnarray*}$ . Danke.

Du schreibst weiter:

Zitat:

Original von HAL 9000
Nun, genau damit beschäftigt sich ja der zweite Ergänzungssatz des Quadratischen Reziprozitätsgesetzes: $\begin{eqnarray*} \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} \end{eqnarray*}$ , also $\begin{eqnarray*} \left(\frac{2}{p}\right) = -1 \end{eqnarray*}$ für $\begin{eqnarray*} p\equiv \pm 3\bmod 8 \end{eqnarray*}$ .

Kannst du mir da nochmal auf die Sprünge helfen?
Hm...Ich sehe leider nicht den Zusammenhang zwischen Ordnung und quadratischem (Nicht)rest. Deshalb kann ich auch gerade nicht ohne weiteres dieses nachvollziehen:

Zitat:

Original von HAL 9000
Was du aus $\begin{eqnarray*} \left(\frac{2}{p}\right) = -1 \end{eqnarray*}$ lediglich sicher folgern kannst ist, dass $\begin{eqnarray*} \operatorname{ord}_p(2) = \frac{p-1}{q} \end{eqnarray*}$ gilt, wobei $\begin{eqnarray*} q \end{eqnarray*}$ ein ungerader Teiler von $\begin{eqnarray*} p-1 \end{eqnarray*}$ ist.

Edit:
Ah, mein Ansatz wäre dieser:
Sei $\begin{eqnarray*} p\equiv\pm 3\pmod 8 \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} \left(\frac{2}{p}\right) = -1 \end{eqnarray*}$ , also $\begin{eqnarray*} \left(\frac{2}{p}\right) \equiv -1 \pmod p \end{eqnarray*}$ .
Hm, jetzt fehlt mir noch ein Schubs, denke ich.

16.02.2023, 11:32

HAL 9000

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \operatorname{ord}_p(2) \mid (p-1) \end{eqnarray*}$ hast du ja selbst schon festgestellt, damit existiert eine ganze Zahl $\begin{eqnarray*} q\geq 1 \end{eqnarray*}$ mit $\begin{eqnarray*} \operatorname{ord}_p(2) = \frac{p-1}{q} \end{eqnarray*}$ .

Ist $\begin{eqnarray*} q \end{eqnarray*}$ gerade, dann folgt daraus aber $\begin{eqnarray*} 1 \equiv \left( 2^{\frac{p-1}{q}}\right)^{\frac{q}{2}} \stackrel{!}{=} 2^{\frac{p-1}{2}}\bmod p \end{eqnarray*}$ im Widerspruch zu $\begin{eqnarray*} 2^{\frac{p-1}{2}}\equiv -1\bmod p \end{eqnarray*}$ .

16.02.2023, 11:51

Malcang

Auf diesen Beitrag antworten »

Ah ja, vielen Dank, dass sehe ich nun deutlicher. Ich beschäftige mich nun noch eine Weile damit, danke sehr!

Das führt mich aber schlussendlich zu der Frage, wie ich die Ordnung $\begin{eqnarray*} ord_2(p) \end{eqnarray*}$ effizient implentieren kann (in meinem Falle: python).
Die naive Idee, die Exponenten einfach hochzuzählen, ist zwar zielführend, aber sicher nicht die beste. Also dachte ich, ich könnte ja auch "runterzählen": Beginne bei $\begin{eqnarray*} p-1 \end{eqnarray*}$ , bilde $\begin{eqnarray*} 2^{\frac{p-1}{2}} \end{eqnarray*}$ . Wenn das 1 ergibt, habe ich ja zumindest schonmal eine viel niedrigere Obergrenze.
Nun stellt sich aber ja heraus, dass ich im Falle -1 dann eben noch auf andere Teiler zurückgreifen muss.
Auch wenn ich vorher prüfen könnte, ob ich es mit einem geraden oder ungeraden Teiler zu tun habe, so erscheint mir das insgesamt doch sehr aufwändig.

Gibt es eine bessere Möglichkeit?

16.02.2023, 12:26

HAL 9000

Auf diesen Beitrag antworten »

Naja, ein mögliches Vorgehen:

1) Start mit $\begin{eqnarray*} m=p-1 \end{eqnarray*}$ .

2) Untersuche für alle Primteiler $\begin{eqnarray*} q \end{eqnarray*}$ von $\begin{eqnarray*} m \end{eqnarray*}$ , ob $\begin{eqnarray*} 2^{\frac{m}{q}}\equiv 1\bmod p \end{eqnarray*}$ gilt.

3) Gibt es ein solches $\begin{eqnarray*} q \end{eqnarray*}$ , dann setze $\begin{eqnarray*} m:=\frac{m}{q} \end{eqnarray*}$ und fahre fort mit 2).

4) Andernfalls ist $\begin{eqnarray*} m \end{eqnarray*}$ die gesuchte Ordnung $\begin{eqnarray*} \operatorname{ord}_p(2) \end{eqnarray*}$ .

Ist bei großen $\begin{eqnarray*} p \end{eqnarray*}$ wohl effizienter als die naive Methode. Allerdings sollte es auch nicht so groß sein, dass die Primfaktorzerlegung von $\begin{eqnarray*} p-1 \end{eqnarray*}$ erhebliche Schwierigkeiten macht. Augenzwinkern

16.02.2023, 14:16

Malcang

Auf diesen Beitrag antworten »

Danke HAL.

Zitat:

Original von HAL 9000
Allerdings sollte es auch nicht so groß sein, dass die Primfaktorzerlegung von $\begin{eqnarray*} p-1 \end{eqnarray*}$ erhebliche Schwierigkeiten macht. Augenzwinkern

Das war genau meine Befürchtung Big Laugh

Ich hatte gehofft dass es Möglichkeiten gibt, in denen ich ohne die Primfaktorzerlegung auskomme. Also ein hinreichendes Kriterium dafür, wie die Ordnung $\begin{eqnarray*} ord_2(p) \end{eqnarray*}$ berechnet wird. Bisher weiß ich ja nur $\begin{eqnarray*} \log_2(p) \leq ord_2(p)\leq p-1 \end{eqnarray*}$ .

16.02.2023, 14:29

HAL 9000

Auf diesen Beitrag antworten »

In Größenordnungen, wo die Primfaktorzerlegung von $\begin{eqnarray*} p-1 \end{eqnarray*}$ Probleme macht, muss man aber nicht ernsthaft mehr über die naive Methode sprechen - schon viel eher nicht mehr.

16.02.2023, 15:03

Malcang

Auf diesen Beitrag antworten »

Das war meine Befürchtung.

Danke sehr! Freude

17.02.2023, 10:20

HAL 9000

Auf diesen Beitrag antworten »

Hab mal ein kleines Skript erstellt, was die obige Idee zur Ordnungsberechnung $\begin{eqnarray*} \operatorname{ord}_p(a) \end{eqnarray*}$ umsetzt:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

import gmpy2, primefac

def ordp(a, p):
    m = p-1
    r = 1
    for q in primefac.primefac(p-1):
        if (q != r):
            mt = m//q
            if (gmpy2.powmod(a, mt, p) == 1):
                m = mt
                r = 1
            else:
                r = q
    return m

In der Hoffnung, dass Generator "primefac" aus dem gleichnamigen Modul (musst du vermutlich nachinstallieren) einigermaßen brauchbar auch für sehr große Zahlen ist.

P.S.: Hab auch sympy.ntheory.factorint ausprobiert, aber das scheint signifikant langsamer zu sein.

Neue Frage »

Antworten »

Ordnung von 2 modulo p

Verwandte Themen