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: Iterating f(X) = X^2 - X + 1
Replies: 7   Last Post: Jun 11, 2013 9:41 AM

 Messages: [ Previous | Next ]
 Phil Carmody Posts: 2,219 Registered: 12/7/04
Re: Iterating f(X) = X^2 - X + 1
Posted: Jun 11, 2013 8:46 AM

David Bernier <david250@videotron.ca> writes:
> f(X) := X^2 - X + 1, a polynomial in say Z[X] or Q[X].
>
> Let q:= f^11 (m) = f^11 (5379) .
>
> Then q with about 7600 digits, is
> a probable prime.
>
> PARI-gp did the strong Rabin-Miller probabilitic
> primatitility test for 560 random bases on 'q' .
>
> And 'q' passed. From recent memory, a "random" composite
> will pass this test for 560 bases about (or no more than)
> with probability 1/4^560, or about 10^(-336).

If you can pull any factors out of f^i(x) for i<11, then they
could help towards a Pocklington or related proof of primality.
It seems i=1..5 crack instantly, but alas they're insignificant.
You'd need to crack everything up to i=8, or i=9 on its own,
in order to achieve the magical 25% factorisation for a
Coppersmith-Howgrave-Graham to work. Otherwise, your
number is in range for a multi-processor ECPP attack,
(Marcel Martin's "Primo" is what I always used to use,
but I think its name has changed to Certifix or similar
recently.)

Phil
--
"In a world of magnets and miracles"
-- Insane Clown Posse, Miracles, 2009. Much derided.
"Magnets, how do they work"
-- Pink Floyd, High Hopes, 1994. Lauded as lyrical geniuses.

Date Subject Author
5/27/13 David Bernier
5/27/13 David Bernier
5/28/13 David Bernier
5/28/13 David Bernier
6/2/13 David Bernier
6/11/13 Phil Carmody
6/11/13 JT
6/11/13 Robin Chapman