Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: six strong pseudoprimes, one degree 4096 polynomial
Replies: 10   Last Post: Jun 21, 2013 12:46 PM

 Messages: [ Previous | Next ]
 David Bernier Posts: 3,892 Registered: 12/13/04
Re: six strong pseudoprimes, one degree 4096 polynomial
Posted: Jun 21, 2013 12:46 PM

On 06/20/2013 07:04 AM, David Bernier wrote:
> On 06/12/2013 12:19 AM, Graham Cooper wrote:
>> On Jun 1, 8:36 am, David Bernier <david...@videotron.ca> wrote:
>>> 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.
>

[...]

Update on testing up to 25000 exhaustively:
now, about 11 probable primes. It's still
running mind you.

The PARI/gp code:

?
count=0;for(W=2,25000,count=count+1;for(Z=6,6,par=Z;new=W;for(X=1,par,new=new^4-new^2+1);if(ispseudoprime(new),print(W,"
",round(log(new)/log(10))))))

Here's the output, meaning a value 'k' such that
g^6 (k) is a probable prime, followed by
the number of decimal digits in g^6 (k), within a margin
of error of +/- 1 digit.

g(X):= X^4 -X^2 + 1 , as always.

Extended table:

55 7128
1948 13474
3269 14395
3981 14746
6942 15735
7341 15834
10141 16409
14845 17087
15476 17161
20913 17696
23360 17893

dave
--
On Hypnos,
http://messagenetcommresearch.com/myths/bios/hypnos.html

Date Subject Author
5/31/13 David Bernier
6/3/13 David Bernier
6/11/13 Phil Carmody
6/11/13 David Bernier
6/12/13 Graham Cooper
6/12/13 Graham Cooper
6/12/13 David Bernier
6/12/13 Graham Cooper
6/12/13 David Bernier
6/20/13 David Bernier
6/21/13 David Bernier