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

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