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

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

On Tue, Jun 03, 2025 at 11:55:39AM -0400, Max Alekseyev wrote:
> Hello,
> 
> Suppose I have a large number m, a quadratic polynomial f(x) and linear
> polynomial g(x).
> Is there a fast way to find all primes p such that the remainder of
> division of (x^m - g(x)) by f(x) vanishes modulo p ?
> To give a specific example, let m = 10^10, f(x) = x^2 - 3*x - 3, and g(x) =
> x - 4.

For m=10^5, you can do this:

factor(content(Mod(x,x^2 - 3*x - 3)^m-(x - 4)))
%22 = Mat([2,2])

Cheers,
Bill