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

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