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

[Watson Ladd <watsonbladd@gmail.com>]

On Tue, Jun 3, 2025 at 4:47 PM Max Alekseyev <maxale@gmail.com> wrote:
>
> Hi Watson,
> Thanks for the suggestion. Wouldn't computing the norm of x^m-g(x) be tricky here, given the magnitude of m?

Yes, this is a constraint. You may be able to get around this by
considering the Chinese remainder theorem but if the remainder
polynomial has very large coefficients there is not much of a way
around that I can think of.

> 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



-- 
Astra mortemque praestare gradatim