Kevin Acres on Sat, 26 Dec 2009 02:01:40 +0100


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

Re: Montgomery Square Root question


Hi Bill,

At 10:32 AM 26/12/2009, you wrote:
On Fri, Dec 25, 2009 at 10:03:08PM +1100, Kevin Acres wrote:
> One more question that I have is about Montgomery square roots.  Can
> anyone tell me if this is supported natively by Pari/GP.
>
> Basically I'm trying to port a Magma SNFS example to Pari/GP and this
> is about my last stumbling block.
>
> Currently the ported code works well for Gaussian integers, but I'm
> trying to get the general case working as well.

I am not sure what Montgomery square roots exactly are, but you can
compute square roots over any number fields by computing the roots of
x^2-a with nfroots().

Cheers,
Bill.

A case in point is that I need to find the square root modulo x^3 + 60*x + 64 of:

28146578841227871637467936328085117616334995672344313744414\
    83926978867652153721301870381570719744*x^2 -
409421329393317510182732406505919857074978625675148613247217512014934258219\
    10113619606396083372032*x-
4597574705568933751179654537544093443765025\
    8546148057739453165564673458691658141449930516266483712

I know that the answer is:

189133117686159822165485681043654738588680060928*x^2 +
    2055476375095129701009302875309311162506447683584*x +
    1945600371033366152866700970896778949964215615488

But I just don't know how to get there in Pari/GP. I've tried a couple of things with nfroots, but failed to get any success as yet.

Regards,

Kevin