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

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 <
[email protected]> 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
>
>