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

Hi Watson,
Thanks for the suggestion. Wouldn't computing the norm of x^m-g(x) be
tricky here, given the magnitude of m?
Regards,
Max


On Tue, Jun 3, 2025 at 6:52 PM Watson Ladd <[email protected]> wrote:

> On Tue, Jun 3, 2025 at 9:03 AM Max Alekseyev <[email protected]> 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.
>
> You are probably best off constructing Z[x]/f(x), going to the
> relevant number field (Q adjoin the discriminant) than explicitly
> considering the primes that divide the norm of x^m-g(x) as candidates.
> It takes a bit of theory to figure out exactly what the next step is,
> but shouldn't be that tricky.
>
> Sincerely,
> Watson
> >
> > Thanks,
> > Max
> >
> >
>
>
> --
> Astra mortemque praestare gradatim
>