David Bernier <email@example.com> 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.