Re: [PrimeNumbers] it works!
- Hello Bill,
> the following program tries to determine the primality of a number bySlightly less programatic description of the test: If both
> combining two tests into one, avoiding the usual pseudo-prime situ-
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
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.
[Name] Peter Kosinar [Quote] 2B | ~2B = exp(i*PI) [ICQ] 134813278