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