The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

David Bernier <> 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

"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.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.