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

[Max Alekseyev <maxale@gmail.com>]

Hi Bill,

Unfortunately, not. Number m = 10^10 was just randomly picked as an example to show its magnitude.

Regards,

Max

On Fri, Jun 6, 2025 at 3:32 PM Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:

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.