## 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. im 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 dont know where m and k come from, which is what is keeping me from finishing the program ...

grrrrrr
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
 bump ... anyone?
 ANYONE? bump one last time as its due tomorrow and im still stuck

 Similar discussions for: strong primality test ... ?? Thread Forum Replies Biology, Chemistry & Other Homework 10 Calculus & Beyond Homework 0 Linear & Abstract Algebra 11 Calculus & Beyond Homework 2 Linear & Abstract Algebra 2