Re: Montgomery Square Root question

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Sat, Dec 26, 2009 at 11:54:58AM +1100, Kevin Acres wrote:
> Hi 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.

Let P=a^3+60*a+64 and z your number expressed in term of a, not x:
P=a^3+60*a+64
z=2814657884122787163746793632808511761633499567234431374441483926978867652153721301870381570719744*a^2-40942132939331751018273240650591985707497862567514861324721751201493425821910113619606396083372032*a-45975747055689337511796545375440934437650258546148057739453165564673458691658141449930516266483712

then do
nfroots(P,x^2-z)
%3 = [Mod(-189133117686159822165485681043654738588680060928*a^2 - 2055476375095129701009302875309311162506447683584*a - 1945600371033366152866700970896778949964215615488, a^3 + 60*a + 64), Mod(189133117686159822165485681043654738588680060928*a^2 + 2055476375095129701009302875309311162506447683584*a + 1945600371033366152866700970896778949964215615488, a^3 + 60*a + 64)]

Cheers,
Bill.