Expand Messages
• Hello Bill, ... Slightly less programatic description of the test: If both 1) N must not be divisible by 5, and 2) 2^N - 3^((N-1)/2) = 1 or 3 (mod N), then N
Message 1 of 5 , Feb 7, 2008
Hello Bill,

> the following program tries to determine the primality of a number by
> combining two tests into one, avoiding the usual pseudo-prime situ-
> ation:

Slightly less programatic description of the test: If both
1) N must not be divisible by 5, and
2) 2^N - 3^((N-1)/2) = 1 or 3 (mod N),
then N is declared prime.

Clearly, this test is surely not stronger (although it is likely strictly
weaker) than a combination of
1) Divisibility by 5 test,
2) Base 2 Fermat test and
3) Base 3 Euler test
while having about the same time-complexity as these three together (in
fact, performing the step 3 only if step 2 succeeds can improve the
actual speed).

Combining the tests the way you did is usually not a good idea, as you're
losing some potentially useful information. In particular, instead of
checking 2^N = 2 (mod N) and 3^((N-1)/2) = +/-1 mod N, you're just
checking if their difference is equal to something -- which can, unless
proven otherwise, happen a lot more often.

Peter

--
[Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI) [ICQ] 134813278
Your message has been successfully submitted and would be delivered to recipients shortly.