Proth-like thinking

Expand Messages
• 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
• ... 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
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
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
• ... 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
<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.