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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Jun 04, 2025 at 03:44:11PM -0400, Max Alekseyev wrote:
> 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.

If you only need m = 10^k then it might possible to prove the content
is always 4 for k>=2.

Cheers,
Bill.