Re: computing all square root modulo a composite

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Bill Allombert [2024-10-12 17:51]:
> On Sat, Oct 12, 2024 at 05:41:06PM +0200, Karim Belabas wrote:
> > * Max Alekseyev [2024-10-12 16:50]:
> > > On Tue, Oct 1, 2024 at 4:56 AM Bill Allombert <
> > > Bill.Allombert@math.u-bordeaux.fr> wrote:
> > > 
> > > >
> > > > Internally, we have a function Zn_quad_roots that compute all the solution
> > > > of x^2+b*x+c mod N
> > > > for composite N.
> > > > Maybe we could add it to GP if we find a GP interface to it.
> > > >
> > > >
> > > Bill, I'd truly appreciate having such a function.
> > 
> > You have it already:
> > 
> >   install(Zn_quad_roots, GGG)
> >   Zn_quad_roots([N, factor(N)], 0, -B)
> > 
> > should output all square roots of B mod N. (Didn't test :-)
> > Of course, [N, factor(N)] should be precomputed.
> 
> Indeed, but my question was:
> Could you suggest a GP interface for it ?

No time for this today, already spent too much time with email. 

The "natural" interface is going to be painful / awkward (take a
general quadratic polynomial as input); I don't think I want to do
this ... Be my guest. :-)

The easiest solution (and most sensible IMHO) would be to simply
provide a Zn_quad_roots0 libpari wrapper that one could safely install,
returning 0 or [] (or any sentinel value) instead of NULL.

Then people could install and play with it in GP.

> (even the C interface is strange, N should be last).

Agreed.

Cheers,

    K.B.
-- 
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/