Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: six strong pseudoprimes, one degree 4096 polynomial
Posted:
Jun 20, 2013 7:04 AM


On 06/12/2013 12:19 AM, Graham Cooper wrote: > On Jun 1, 8:36 am, David Bernier <david...@videotron.ca> wrote: >> If I start with the polynomial function: >> g(x) = x^4  x^2 +1 then >> >> P(x) := g(g(g(g(g(g(x)))))) is also a polynomial function of x. >> >> The degree of P in x is: 4*4*4*4*4*4 = 4^6 = 2^12 = 4096. >> >> Letting 'x' go from 2 to 14,845 >> 6 values of 'x' give that P(x) is a strong pseudoprime, >> passing the RabinMiller test with 60 random bases in each >> case. >> >> x= 55, 1948, 3269, 3981, 7341, 14845 >> are those 6 values. >> >> Beyond ~= 3269, I was only testing x with exactly >> two prime factors, so there could possibly be >> more x with P(x) a strong psudoprime and >> x <= 14845. >> >> P(14845) has about 17000 digits, and >> 17000digit numbers are prime once in >> 2.5 *17000 or one time in 42500. >> >> With x in {55, 1948, 3269, 3981, 7341, 14845} >> each yielding a probable prime for P(x), the >> (with "high probability"), the primality >> statistics for the P(x), heuristics, seem to >> be out of whack. > > > How many were you expecting?
I redid the tests. Now I find 8 probable primes up to k= 14900. I was expecting 0.43 using 1/log(x) heuristics as the likelihood a somesuch integer x > 1.
Here's a small table:
[===========================] [ 1 55 7128 ] [ 2 1948 13474 ] [ 3 3269 14395 ] [ 4 3981 14746 ] [ 5 6942 15735 ] [ 6 7341 15834 ] [ 7 10141 16409 ] [ 8 14845 17087 ] [===========================]
8 probable primes up to 'arg' as in g^6(arg) > a large number that I test for probable primeness.
Reminder that g(X):= X^4X^2+1.
Naive expectation for how many primes for this range of arguments to g^6 is then 0.4312 but we may have 8, which is 18.55 times the naive expectation.
I may retest then with a RabinMiller test to 100 bases or so. Then the probability of a composite passing is 1/4^100, or less ... But doing primality proofs on numbers with 7000 to 17000 digits is not my objective. In any case, compared to the likelihood of a statistical fluke which is not representative of "typical behaviour" for prime values of g^6(n), the chances of a composite passing itself as an impostor "prime" turn pale by comparison ...
> 17,000 DIGITS 1 in 42500 (5 digits) > > and you only got 6!
So ... ?
dave  On Hypnos, http://messagenetcommresearch.com/myths/bios/hypnos.html



