Modulare Logarithmen < Mathematica < Mathe-Software < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:32 So 26.11.2006 | | Autor: | Kiki3000 |
| Aufgabe | Sei p prim und [mm] n=[\wurzel{p}]. [/mm] Dann gilt:
x [mm] \equiv log_a [/mm] b mod p [mm] \gdw a^r \equiv ba^{-qn} [/mm] mod p (1)
wobei x= qn + r mit 0 [mm] \le [/mm] q, r<n.
Aufgabe:
Die Äquivalenz (1) rechtfertigt die Vorgehensweise im folgenden Babystep-Giantstep-Verfahren zur Bestimmung von modularen Logarithmen.
i) Bilden Sie eine Menge M mit den Elementen [mm] a^r [/mm] mod p für r=0,...,n-1.
ii) Vergleichen Sie, ob [mm] ba^{-qn} [/mm] mod p in M enthalten ist (q=0,...,n-1). Gilt [mm] a^r \equiv ba^{-qn} [/mm] mod p für ein Paar (q,r), so geben Sie den (minimalsten) modularen Logarithmus x= qn +r aus.
Hinweis: [mm] ba^{-qn} \equiv b(a^{-n})^q [/mm] mod p lässt sich aus [mm] b(a^{-n})^{q-1} a^{-n} [/mm] mod p, also aus der vorherigen Iteration, bestimmen.
Implementieren Sie diesen Algorithmus. |
Hallo!
Also in Computeralgebra sollten wir die Programmieren, habe ich auch gemacht, aber es wird nichts ausgegeben. Also hier mein Programmcode:
Clear[BGV];
BGV[a_, b_, p_] := Module[{M, n},
n = [mm] Floor[\wurzel{n}];
[/mm]
M = Table[PowerMod[a, r, p], {r, 0, n - 1}];
For[q = 0 , q <= n - 1, q++,
For[r = 0, r <= n - 1, r++,
If[Mod[b*PowerMod[a, -q*n, p], p] == M[ [ r ] ], Return[q*n + r]]]]]
Dann sollten wir den Algorithmus ausprobieren für
[mm] log_2 [/mm] 5 mod 7, [mm] log_5 [/mm] 8 mod 13 und [mm] log_{16643} [/mm] 3376 mod 104729.
Aber bei keiner passiert was, also muss in meinem Algorithmus irgendwas falsch sein. Ich denke, dass alles eigentlich so weit richtig ist, nur dass eine Kleinigkeit falsch ist. Vielleicht kennt sich jemand mit aus und könnte mir helfen. Das wäre super!
Danke schonmal, Vlg Kiki
|
|
| |
|
Hallo,
ganz am Anfang musst du die Wurzel aus p ziehen, nicht aus n.
Außerdem fangen die Listen in Mathematica bei 1 an, so dass du in deiner If-Abfrage auf M r+1 zugreifen musst.
Allerdings funktioniert es für (2,5,7) immer noch nicht...
Gruß
Martin
|
|
|
|
