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

18374Proth-like thinking

Expand Messages
  • leavemsg1
    Sep 21, 2006
    • 0 Attachment
      Hello, Group.

      modifying the theorem...

      choose a odd 'n' such that 2^k +1 < n < 2*(2^k +1) for some k --
      notice that this is different from Proth's notion that 'n' must be <
      2^k +1.

      if Z = n*(2^k) +1, then any number relatively prime to, less than,
      and up to the lower limit for 'n' would rather quickly expose 'Z' as
      composite using q^(Z-1) != 1 (mod Z) test.

      choose n = 15, k = 3 and 9 < 15 < 18 and q = 7 since gcd(3 or 5, 15) !
      = 1; Z = 121. compute 7^120 == 109^24 == 45^6 == 23 (mod 121). I
      could have also chosen q = 2, 4, or 8 to prove not prime.

      Conversely, however, a single test might also confirm primality when
      the value for 'q' is chosen relatively prime to, less than, and up to
      the lower limit for 'n' as opposed to performing several classical 'p-
      1' tests.

      The two notable counter examples for Z < 1000 (that are shown prime
      via 2^(p-1) == 1 mod p but are actually composite) are 341 & 561 and
      both of them can't be produced using the above criteria since 341 =
      2^2 * 85 +1 (85 is much larger than n < 2*(2^2 +1)) and 561 = 2^4 *
      35 +1 (35 is just larger than n < 2*(2^4 +1) = 34.

      Can someone find a counter-example of Z > 1000 using the construct?

      i.e. After 'Z' is produced and 'q' is so carefully chosen... Can Z be
      composite and still return a value of '1' from a classical 'p-1' test?

      I can't show it... or prove it, but it would seem so... I think the
      classical counter-examples would not fall into this class of primes.

      Bill
    • Show all 4 messages in this topic