strong primality test ... ??

JaeSun

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

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

JaeSun

bump ...

anyone?

JaeSun

ANYONE? bump one last time as its due tomorrow and im still stuck