Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] it works!

Expand Messages
  • Peter Kosinar
    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
    • 0 Attachment
      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.