Re: finding primes modulo which x^m mod f(x) has a prescribed result

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Jun 04, 2025 at 12:30:46PM -0400, Max Alekseyev wrote:
> Hi Bill,
> 
> This would be my approach for small m, but it's impractical for m about
> 10^10. Another approach is to try testing small primes, that is, for a
> candidate p to compute the power x^m in GF(p)[x]/<f(x)>. It'll be fast for
> any chosen p, but it's impossible to guess/find a large prime solution p
> when one exists.
> 
> All in all, I'm hoping for an algorithm that works in O(log(m)) time and
> space.
> I do not expect many primes to be produced this way, but my goal is to
> systematically search for non-trivial cases when such primes do exist and
> may be large.

You will not find a computational algorithm with this complexity,
because the result you seek is not of size O(log(m)) in general.

Exercise: Let p a prime number such that kronecker(21,p)==-1.

Let m be an integer such that m = p-1 (mod p^2-1)

Show that p divides the content of
Mod(x,x^2 - 3*x - 3)^m-(x - 4)

Cheers,
Bill.