Faster Primality Test - Applied Cryptography

[juicyclaws]

maybe explain what t and s are? You are really moving too fast for anyone to understand.

You get the value for t and s by continually dividing n-1 by two, t times.

for example if we have n = 17, n-1 = 16 (an even number)

s = 16/2 = 8 t = 1
s = 8/2 = 4 t = 2
s = 4/2 = 2 t = 3
s = 2/2 = 1 t = 4

now we can write 17 as 2^4 * 1 + 1


Also you forgot to mention that if a^s = n-1 mod p, it is also a potential prime.
And if a^((2^j) * s) = 1 mod p, it is not a prime

[LokeshSharmaa]

Exactly what I was looking for; precise and to the point.

[tengb]

fermat is pronounced "ferr-MAH"