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

[Max Alekseyev <maxale@gmail.com>]

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 <watsonbladd@gmail.com> wrote:

On Tue, Jun 3, 2025 at 9:03 AM Max Alekseyev <maxale@gmail.com> 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