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

[Max Alekseyev <maxale@gmail.com>]

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.

Regards,

Max

On Wed, Jun 4, 2025 at 6:00 AM Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

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