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

Proth-like thinking

Expand Messages
  • leavemsg1
    Hello, Group. modifying the theorem... choose a odd n such that 2^k +1
    Message 1 of 4 , Sep 21 5:38 PM
    • 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
    • leavemsg1
      ... as ... 15) ! ... Oddly enough, 121 is a psuedoprime base 3 according to Sloane s list. ... when ... to ... classical p- ... 561 and ... theorem? ... be
      Message 2 of 4 , Sep 22 10:37 AM
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@...>
        wrote:
        >
        > Hello, Group.
        >
        > modifying Proth's Theorem...
        >
        > choose an 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 the 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 it not prime.

        Oddly enough, 121 is a psuedoprime base 3 according to Sloane's list.

        >
        > 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 test 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 any counter-example using this modification of Proth's
        theorem?
        >
        > 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
        >
        I would name this class of primes... "2nd kind Proth primes"
      • Paul Underwood
        ... Bill, is the 771st (?) Carmichael number a counterexample?: ? N=1657700353 1657700353 ? factor(N-1) [2 15] [3 2] [7 1] [11 1] [73 1] ? n=(N-1)/(2^15) 50589
        Message 3 of 4 , Sep 22 11:12 AM
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@...> wrote:
          >
          > --- In primenumbers@yahoogroups.com, "leavemsg1" <leavemsg1@>
          > wrote:
          > >
          > > Hello, Group.
          > >
          > > modifying Proth's Theorem...
          > >
          > > choose an 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 the 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 it not prime.
          >
          > Oddly enough, 121 is a psuedoprime base 3 according to Sloane's list.
          >
          > >
          > > 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 test 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 any counter-example using this modification of Proth's
          > theorem?
          > >
          > > 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
          > >
          > I would name this class of primes... "2nd kind Proth primes"
          >

          Bill,

          is the 771st (?) Carmichael number a counterexample?:

          ? N=1657700353
          1657700353
          ? factor(N-1)

          [2 15]

          [3 2]

          [7 1]

          [11 1]

          [73 1]

          ? n=(N-1)/(2^15)
          50589
          ? 2^15+1<n&&n<2*(2^15+1)
          1

          Paul
        • leavemsg1
          ... No. The idea for testing any Proth-like number would be to subtract 1 and divide out 2 until only other prime factors existed, and then to compute the
          Message 4 of 4 , Sep 24 2:13 PM
          • 0 Attachment
            --- In primenumbers@yahoogroups.com, "Paul Underwood"
            <paulunderwood@...> wrote:
            >
            >
            > Bill,
            >
            > is the 771st (?) Carmichael number a counterexample?:
            >
            > ? N=1657700353
            > 1657700353
            > ? factor(N-1)
            >
            > [2 15]
            >
            > [3 2]
            >
            > [7 1]
            >
            > [11 1]
            >
            > [73 1]

            No. The idea for testing any Proth-like number would be to subtract 1
            and divide out 2 until only other prime factors existed, and then to
            compute the classical 'p-1' test with 'any' of those numbers relative-
            ly prime to 50589. Hence, 2, 5, 13 up to 2^15 +1 would work but gcd
            (50589,3)!= 1 and 2 exposes that 1657700353 isn't prime.
            Bill
            The same is true for Proth primes except the test changes to a^((p-
            1)/2) == 1 mod p instead of the 'p-1'.

            >
            > ? n=(N-1)/(2^15)
            > 50589
            > ? 2^15+1<n&&n<2*(2^15+1)
            > 1
            >
            > Paul
            >
          Your message has been successfully submitted and would be delivered to recipients shortly.