18375Re: Proth-like thinking
- Sep 22, 2006--- In email@example.com, "leavemsg1" <leavemsg1@...>
> 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'
> composite using the q^(Z-1) != 1 (mod Z) test.15) !
> choose n = 15, k = 3 and 9 < 15 < 18 and q = 7 since gcd(3 or 5,
> = 1; Z = 121. compute 7^120 == 109^24 == 45^6 == 23 (mod 121). IOddly enough, 121 is a psuedoprime base 3 according to Sloane's list.
> could have also chosen q = 2, 4, or 8 to prove it not prime.
> Conversely, however, a single test might also confirm primality
> the value for 'q' is chosen relatively prime to, less than, and upto
> the lower limit for 'n' as opposed to performing severalclassical 'p-
> 1' tests.561 and
> 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 &
> both of them can't be produced using the above criteria since 341 =theorem?
> 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
> i.e. After 'Z' is produced and 'q' is so carefully chosen... Can Z
> composite and still return a value of '1' from a classical 'p-1'test?
>I would name this class of primes... "2nd kind Proth primes"
> 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.
- << Previous post in topic Next post in topic >>