Re: Montgomery Square Root question

[ewan.Delanoy@math.unicaen.fr]

Here's how I would do it in GP, by an algebraic method  :

  Let a be a root of p1(x)=x^3+60*x+4, and let
p2(x)=2814657884122787163746793632808511761633499567234431374441483926978867652153721301870381570719744*x^2-40942132939331751018273240650591985707497862567514861324721751201493425821910113619606396083372032*x-45975747055689337511796545375440934437650258546148057739453165564673458691658141449930516266483712.
The problem then bogs down to computing the gcd
of p1(x) and p3(x)=x^2-p2(a) in the number field Q[a]. Note that the gcd
function yields an unexpected result in GP, which makes me think the
numerical values you posted were wrong.

                                                                                  Ewan

PARI/GP is free software, covered by the GNU General Public License, and
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 4000000, primelimit = 500000
? p1(x)=x^3+60*x+64
? a=Mod(variable_for_a,p1(variable_for_a))
%1 = Mod(variable_for_a, variable_for_a^3 + 60*variable_for_a + 64)
?
p2(x)=2814657884122787163746793632808511761633499567234431374441483926978867652153721301870381570719744*x^2-40942132939331751018273240650591985707497862567514861324721751201493425821910113619606396083372032*x-45975747055689337511796545375440934437650258546148057739453165564673458691658141449930516266483712
? gcd(p1(x),x^2-p2(a))
%2 = 1




> 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.
>>
>
> 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
>
>