Math Forum Discussions

David Bernier

Posts: 3,892
Registered: 12/13/04

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

Plain Text

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 pseudo-prime,
>> passing the Rabin-Miller 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 psudo-prime and
>> x <= 14845.
>>
>> P(14845) has about 17000 digits, and
>> 17000-digit 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^4-X^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 Rabin-Miller
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