- #1
JaeSun
- 37
- 0
strong primality test ... ??
ok, bear with me ...
we learned weak primality tests (given n and base a,::: a^(n-1) mod n ::: if it does not equal 1, then its composite, if it equals 1, then MAYBE prime) ...
then we learned strong primes ... think of n-1 = m2^k when m is odd. test ::: a^m mod n and keep squaring until we get 1 (or past n-1). go back one step, and check if it was -1 (if so, probably prime, if not, then it is composite)
so my homework. I am kinda confused.
I was given this algorithm for the strong primality test
my question is, where does m and k come from??
i been looking at my notes over and over again ... i did read that m is odd, so I can just choose any random odd number ? but then k ? what number is that?
i am kinda lost ...
other notes that i have:
write n-1 = 2^k m
check 2^m, (2^n)^2, ... , (2^m)^(2^k)
if 2^m mod n = 1, n is like a prime. otherwise find first j so that:
(2^m)^(2^j) != 1 and
(2^m)^(2^j+1) = 1
then 2^(m2^j) is a root of x^2-1 =0
if 2^(m2^j) = -1, n is like a prime, if not, n is composite ...
can anyone help??
he went over this in like 1 day, way back in the beginning of the semester, and he just gave us this assignment ... would like any help in understanding this, so I could program this (the assignment is to program numbers that pass weak test, but fail strong test) ...
i don't know where m and k come from, which is what is keeping me from finishing the program ...
grrrrrr
ok, bear with me ...
we learned weak primality tests (given n and base a,::: a^(n-1) mod n ::: if it does not equal 1, then its composite, if it equals 1, then MAYBE prime) ...
then we learned strong primes ... think of n-1 = m2^k when m is odd. test ::: a^m mod n and keep squaring until we get 1 (or past n-1). go back one step, and check if it was -1 (if so, probably prime, if not, then it is composite)
so my homework. I am kinda confused.
I was given this algorithm for the strong primality test
Code:
n-1 = m2^k
A = a^m mod n
if( A=1 )
"maybe prime
else
while( A^2 mod n != 1 )
{
A = A^2 mod n
}
if( A = -1 )
"maybe prime"
else
"composite"my question is, where does m and k come from??
i been looking at my notes over and over again ... i did read that m is odd, so I can just choose any random odd number ? but then k ? what number is that?
i am kinda lost ...
other notes that i have:
write n-1 = 2^k m
check 2^m, (2^n)^2, ... , (2^m)^(2^k)
if 2^m mod n = 1, n is like a prime. otherwise find first j so that:
(2^m)^(2^j) != 1 and
(2^m)^(2^j+1) = 1
then 2^(m2^j) is a root of x^2-1 =0
if 2^(m2^j) = -1, n is like a prime, if not, n is composite ...
can anyone help??
he went over this in like 1 day, way back in the beginning of the semester, and he just gave us this assignment ... would like any help in understanding this, so I could program this (the assignment is to program numbers that pass weak test, but fail strong test) ...
i don't know where m and k come from, which is what is keeping me from finishing the program ...
grrrrrr