
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. > > PARIgp did the strong RabinMiller 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 CoppersmithHowgraveGraham to work. Otherwise, your number is in range for a multiprocessor 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.

