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

Re: [PrimeNumbers] Fermat Variation

Expand Messages
  • Chris Nash
    Hi there Bill ... the ... What you ve discovered is the basis for two slight improvements on Fermat probable primality. Euler s test does precisely as you
    Message 1 of 4 , May 5, 2001
      Hi there Bill

      >Here are the 2 statements, either of which (if true) could be used as
      the
      >basis of a probable prime test:
      >If A is a PRIME integer, then 2^((A+1)/2) divided by A will leave a
      >remainder of 2 OR a remainder of (A-2).
      >If A is a PRIME integer, then 2^((A-1)/2) divided by A will leave a
      >remainder of 1 OR a remainder of (A-1).

      What you've discovered is the basis for two slight improvements on
      Fermat probable primality. Euler's test does precisely as you describe,
      and looks at b^((A-1)/2). As you've discovered, it's either +1 or -1
      mod A, if A is prime, since it must be a square root of +1. (In fact,
      you can determine which result should occur before embarking on the
      calculation, and this is sufficient to prove Proth primes, given the
      right choice of b).

      This is a little less naive than Fermat PRP, and help catch a few
      'obvious' pseudoprimes. A little more work will give the Miller-Rabin
      test - see http://www.utm.edu/research/primes/prove/prove2_3.html. It's
      also the beginnings of the N-1 primality testing methods, where you
      consider factors of N-1 other than 2. http://www.utm.edu/research/
      primes/prove/prove3_1.html is a gentle introduction to this - notice
      the proofs all revolve around "the order of a, modulo p" - the smallest
      integer e>0 such that a^e=1 mod p.

      As far as execution times of these tests go, the calculation of a^b mod
      c can be done in time that scales with the number of bits in b - so
      saving one bit in b does not save much. On the other hand, the amount
      of extra calculation involved in the theorems on Chris C's page is not
      great, so this line of thought can see very strong probable primality
      results with not too much effort - and ultimately, deterministic proofs
      for those forms where we can factor N-1.

      Chris N.
    Your message has been successfully submitted and would be delivered to recipients shortly.