Max Alekseyev on Sat, 12 Oct 2024 17:55:51 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: computing all square root modulo a composite

As for the name, maybe sqrtall() ?

Regards,
Max


On Sat, Oct 12, 2024 at 11:50 AM Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:
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 ?

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

Cheers,
Bill.