- #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

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