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

Fermat Variation

Expand Messages
  • William F Sindelar
    Hi Everybody: Fermat says that if A is a PRIME integer, then 2^A divided by A will leave a remainder of 2. It occurred to me that perhaps we might not have to
    Message 1 of 4 , May 5, 2001
    • 0 Attachment
      Hi Everybody:
      Fermat says that if A is a PRIME integer, then 2^A divided by A will
      leave a remainder of 2.
      It occurred to me that perhaps we might not have to raise 2 all the way
      to exponent A, but only to some fractional part of A and still have just
      as good a probable prime test as Fermat while significantly reducing
      computation.
      I came up with 2 statements listed below. They seem to be true but I
      can't prove them. I chased Little Fermat all over the web looking for
      something like this but with no luck. I'm starting to suspect that maybe
      I'm all wet, that I've run into something that works only for small
      numbers. Can anyone help?
      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).
      I would appreciate any comments. My thanks and regards to all.
      Bill Sindelar
    • Jack Brennen
      ... You are absolutely correct about this, although you must add the condition that A be an ODD integer. This is the initial step toward coming up with the
      Message 2 of 4 , May 5, 2001
      • 0 Attachment
        Bill Sindelar wrote:

        > 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).

        You are absolutely correct about this, although you must add the
        condition that A be an ODD integer.

        This is the initial step toward coming up with the concept used for
        defining "strong probable primes" -- there is plenty written about
        this and easily accessible with a web search, but you didn't know
        what to look for (strong probable prime).

        Start with:

        http://www.utm.edu/research/primes/prove/prove2_3.html
      • Phil Carmody
        ... Bill, You might want to look into (modular) exponentiation algorithms, as the calculations x^n (mod p) x^((n-1)/2) (mod p) take almost the same
        Message 3 of 4 , May 5, 2001
        • 0 Attachment
          On Sat, 05 May 2001, William F Sindelar wrote:
          > Hi Everybody:
          > Fermat says that if A is a PRIME integer, then 2^A divided by A will
          > leave a remainder of 2.
          > It occurred to me that perhaps we might not have to raise 2 all the way
          > to exponent A, but only to some fractional part of A and still have just
          > as good a probable prime test as Fermat while significantly reducing
          > computation.
          > I came up with 2 statements listed below. They seem to be true but I
          > can't prove them. I chased Little Fermat all over the web looking for
          > something like this but with no luck. I'm starting to suspect that maybe
          > I'm all wet, that I've run into something that works only for small
          > numbers. Can anyone help?
          > 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).
          > I would appreciate any comments. My thanks and regards to all.
          > Bill Sindelar

          Bill,
          You might want to look into (modular) exponentiation algorithms, as the calculations
          x^n (mod p)
          x^((n-1)/2) (mod p)
          take almost the same number of steps, in fact only one square and one multiply are required to get from the latter to the former.

          A rule of thumb is that an m-bit exponent, n, takes roughly
          m squares and m/2 multiplies on average. Here m =~ lg(n) the binary logarithm (round it up).

          Phil

          Mathematics should not have to involve martyrdom;
          Support Eric Weisstein, see http://mathworld.wolfram.com
          Find the best deals on the web at AltaVista Shopping!
          http://www.shopping.altavista.com
        • 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 4 of 4 , May 5, 2001
          • 0 Attachment
            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.