(adsbygoogle = window.adsbygoogle || []).push({}); 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

my question is, where does m and k come from??Code (Text):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"

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Strong primality test ?

**Physics Forums | Science Articles, Homework Help, Discussion**