Kryptologie(Primzahltest)

[elielham]

Hallo,

es geht um ein einen kombinierten Testmit Miller Rabin..was ich aber nicht verstehe ist was (a/p) = 1 bedeutet.und zwar in folgendes:

Any prime p ≡ 1 mod 6 passes MR3 for any input a with (a/p) = 1.

Proof. Recall the notation of the MR3 algorithm and write p in place of n. We have

a^(p−1)/2 = a^(3s t) ≡ 1 mod p and s > 1. Note that (−3/p) = 1, so that there exists r3

with r3^ 2 ≡ −3 mod p. Therefore, ξ3 = (−1 + r3)/2 ∈ Zp and, in Zp, x^3 = 1 has the

three roots 1, ξ3, and ξ3 ^−1

und MR ist Miller Rabin test ,der in unseren Alg so aussieht:

The MR3 Test to Base a

Input: n ≡ 1 mod 6, a ∈ Zn with (a/n) = 1, r3 such that r3^2 ≡ −3 mod n.

Output: “composite†or “probable primeâ€.

Write (n − 1)/2 = 3^(s) t, such that t mod 3 != 0.

1. Let ξ3 = (−1+r3)/2 mod n. If 1 < gcd(ξ3, n) < n, return “compositeâ€.

2. If a^t = 1 mod n, or a^(3i t) = ξ3 or ξ3^−1 mod n for some 0 ≤ i < s,

then return “probable primeâ€, else return “compositeâ€.

Ich würde mich echt freuen, wenn jemand mir helfen könnte..

l

[Steffo]

Hallo elielham,

Ich fand das ganz interessant was du da geschrieben hast und hab mich eben mal mit beschäftigt. So ganz bin ich in den par Minuten nicht durchgestiegen, aber das Prinzip ist doch, dass du rausfinden willst, ob das was du reinsteckst, also eine beliebige Zahl a, eine Primzahl ist. Eine Primzahl ist ja nur durch sich selbst, oder durch 1 restlos teilbar. Deshalb verwendet man auch diese ganzen Modulo Operatoren ...

Dieser MR Test ist mir nicht bekannt, hab den eben mal in Wikipedia überflogen. Allerdings solltest du die Theorie die dahinter steckt mal genauer anschauen, das ist nämlich nicht ganz so trivial. Aus dem Algorithmus unten wird man nämlich erstmal nicht so schlau ...

So wie ich das verstehe ist das eine Aufgabenstellung wo oben steht, Beweisen sie das gilt, und unten halt angegeben ist wies funktioniert. Wobei der erste Hinweis ja gegeben ist, dass die Primzahl p unten als n dargestellt wird. Ich weiß allerdings gerade nicht was das zeta da sein soll und muss jetzt auch weg *g* Aber eventuell würde es helfen, die Definitionen von oben mal unten einzusetzen ?! Ist halt eher mathematisch die Aufgabe als Informationstechnisch ^^

Da das Thema schon weiter ind er Vergangenheit liegt hast du mittlerweile bestimmt mehr dazu in Erfahrung bringen können und ich würde mich freuen, wenn du hier mal antwortest und mich/uns auf den neuesten Stand bringst.

Gruß, Stefan

[elielham]

Hallo Stefan,

ich hab rausgefunden,was das bedeutet.(a/p)=1 ist das Jacobi Symbol und das heisst, dass a^(p-1/2) = 1 ist .in diesem Fall ist a quadratischer Rest mod p.

Aber danke trotzdem

Gruß,

Elham