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

Re: [PrimeNumbers] Another form of probabilistic test for primeness

Expand Messages
  • Peter Kosinar
    ... Four shalt be the number thou shalt count, and the number of the counting shalt be four. For any odd prime x, we have 2^(4x+1) = 2^(5 + 4(x-1)), so
    Message 1 of 3 , Jun 23, 2012
    • 0 Attachment
      > It will be a matter of empirical research to determine lower bounds
      > on composite y such that
      >
      > 2^(3y+1) = 2^(y+3) mod (3y)
      > 2^(5y+1) = 2^(y+5) mod (5y)
      > 2^(7y+1) = 2^(y+7) mod (7y)

      Four shalt be the number thou shalt count, and the number of the counting
      shalt be four.

      For any odd prime x, we have 2^(4x+1) = 2^(5 + 4(x-1)), so
      2^(4x+1) = 0 (mod 4) and 2^(4x+1) = 2^5 (mod x), thus by Chinese Remainder
      Theorem, we get 2^(4x+1) = 2^5 (mod 4x)

      We also have 2^(x+4) = 2^(5 + (x-1)), which gets us
      2^(x+4) = 0 (mod 4) and 2^(x+4) = 2^5 (mod x). Combining them by CNT
      gives 2^(x+4) = 2^5 (mod 4x)

      Ergo, 2^(4x+1) = 2^(4+x) mod (4x), and 4 is the smallest counterexample
      for any odd prime x.

      Peter
    • Kermit Rose
      ... counting shalt be four. ... 0 (mod 4) and 2^(4x+1) = 2^5 (mod x), thus by Chinese Remainder Theorem, we get 2^(4x+1) = 2^5 (mod 4x) ... counterexample for
      Message 2 of 3 , Jun 24, 2012
      • 0 Attachment
        On 6/23/2012 5:44 PM, Peter Kosinar wrote:
        >> It will be a matter of empirical research to determine lower bounds
        >> on composite y such that
        >>
        >> 2^(3y+1) = 2^(y+3) mod (3y)
        >> 2^(5y+1) = 2^(y+5) mod (5y)
        >> 2^(7y+1) = 2^(y+7) mod (7y)
        >
        > Four shalt be the number thou shalt count, and the number of the
        counting shalt be four.
        >
        > For any odd prime x, we have 2^(4x+1) = 2^(5 + 4(x-1)), so 2^(4x+1) =
        0 (mod 4) and 2^(4x+1) = 2^5 (mod x), thus by Chinese Remainder Theorem,
        we get 2^(4x+1) = 2^5 (mod 4x)
        >
        > We also have 2^(x+4) = 2^(5 + (x-1)), which gets us
        > 2^(x+4) = 0 (mod 4) and 2^(x+4) = 2^5 (mod x). Combining them by CNT
        > gives 2^(x+4) = 2^5 (mod 4x)
        >
        > Ergo, 2^(4x+1) = 2^(4+x) mod (4x), and 4 is the smallest
        counterexample for any odd prime x.
        >
        > Peter

        Hello Peter.

        Thanks.

        My test is even worse than you have discovered.

        For any composite y such that 2^y = 2 mod y, (Original Fermat test
        which fails too many times)
        and for any odd prime x,

        Calculate 2^(xy-x-y+1) mod x and 2^(xy-x-y+1) mod y

        2^(xy-x-y+1) = (2^x)^y * 2^(-x-y+1) = 2^y * 2^(-x-y+1) = 2^(y-x-y+1) =
        2^(-x+1) = 2^(1-1) mod x


        2^(xy-x-y+1) = (2^x)^y * 2^(-x-y+1) = 2^x * 2^(-x-y+1) = 2^(x-x-y+1) =
        2^(-y+1) = 2^(1-1) mod y


        Thus by chinese remainder theorem, 2(xy-x-y+1) = 1 mod (xy).

        This proves that my proposed "new" test is only a disguised Fermat test.

        Kermit Rose
      Your message has been successfully submitted and would be delivered to recipients shortly.