Re: Montgomery Square Root question

[Kevin Acres <research@research-systems.com>]

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