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

trying to expose pseudo's

Expand Messages
  • Bill Bouris
    I m posing the question: Does this criteria always expose 2-pseudoprimes ??? (sorry if I m not using the maths totally correctly) let 2^(Q-1) mod Q == 1 where
    Message 1 of 2 , Apr 30, 2009
    • 0 Attachment
      I'm posing the question:
      Does this criteria always expose 2-pseudoprimes ???
      (sorry if I'm not using the maths totally correctly)

      let 2^(Q-1) mod Q == 1 where Q = 4m +1 (possibly pseudo)
      now, 'Q' is prime iff the above criteria and...
      2^(Q-1)-2 mod 'q' == -1, 0
      where 'q' is 'Q' w/all 2's factored out.

      it approves primes...
      eg. Q= 641 = 4*160 +1 and 2^640 mod 641 == 1
      q= 5 or 640 w/all the 2's factored out
      then, 2^640-2 mod 5 == -1, so 641 truly is prime.

      and dis-allows pseudos...
      eg. Q= 341 = 4*85 +1 and 2^340 mod 341 == 1
      q= 85 or 340 w/all 2's factored out
      then, 2^340-2 mod 85 == 14, so 341 is pseudo.

      eg. Q= 101 = 4*25 +1 and 2^100 mod 101 == 1
      q= 25 or 100 w/all the 2's factored out
      then, 2^100-2 mod 25 == -1, so 101 truly is prime.

      I think that it's always 'true', but can't prove it!

      from a cursory glance, it looks O.K.?
      it takes a pseudo to know a pseudo...

      Bill Bouris
    • David Broadhurst
      ... 2^52 - 2 = 1 mod 13
      Message 2 of 2 , May 3, 2009
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        Bill Bouris <leavemsg1@...> wrote:

        > sorry if I'm not using the maths totally correctly
        > 2^(Q-1)-2 mod 'q' == -1, 0

        2^52 - 2 = 1 mod 13
      Your message has been successfully submitted and would be delivered to recipients shortly.