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

[Max Alekseyev <maxale@gmail.com>]

Hi Bill,

First off, I should have said that I'd like to have O(poly(log(m))) not O(log(m)) algorithm, but even with my honest typo, I don't quite follow how your exercise implies the absence of the algorithm with O(log(m)) space.

From m = p-1 (mod p^2-1), it follows that p <= m+1 and so it fits the O(log(m)) space (if it was the size of p you referred to).

Anyway, I'd like to have the algorithm be bounded in both time and memory resources by a polynomial in log(m), not in m itself.

Regards,

Max

On Wed, Jun 4, 2025 at 2:20 PM Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

On Wed, Jun 04, 2025 at 12:30:46PM -0400, Max Alekseyev wrote:
> 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.

You will not find a computational algorithm with this complexity,
because the result you seek is not of size O(log(m)) in general.

Exercise: Let p a prime number such that kronecker(21,p)==-1.

Let m be an integer such that m = p-1 (mod p^2-1)

Show that p divides the content of
Mod(x,x^2 - 3*x - 3)^m-(x - 4)

Cheers,
Bill.