Re: Montgomery Square Root question

[ewan.Delanoy@math.unicaen.fr]

   Apologies, the computations were made too quickly in my last post.
Below is a correction
(which shows that the values provided by Kevin were correct contrary to
what I thought)

                                                                                                                             Ewan


p1(x)=x^3+60*x+64
p2(x)=2814657884122787163746793632808511761633499567234431374441483926978867652153721301870381570719744*x^2-40942132939331751018273240650591985707497862567514861324721751201493425821910113619606396083372032*x-45975747055689337511796545375440934437650258546148057739453165564673458691658141449930516266483712
a=Mod(variable_for_a,p1(variable_for_a))
charpoly_for_b=polresultant(x^2-p2(variable_for_a),p1(variable_for_a),variable_for_a)
minpoly_for_b=factor(charpoly_for_b)[2,1]
u1=gcd(minpoly_for_b,x^2-p2(a))
u2=lift(u1)
formula_for_b=-subst(polcoeff(u2,0,x)/polcoeff(u2,1,x),variable_for_a,a)


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
?
p2(x)=2814657884122787163746793632808511761633499567234431374441483926978867652153721301870381570719744*x^2-40942132939331751018273240650591985707497862567514861324721751201493425821910113619606396083372032*x-45975747055689337511796545375440934437650258546148057739453165564673458691658141449930516266483712
? a=Mod(variable_for_a,p1(variable_for_a))
%1 = Mod(variable_for_a, variable_for_a^3 + 60*variable_for_a + 64)
?
charpoly_for_b=polresultant(x^2-p2(variable_for_a),p1(variable_for_a),variable_for_a)
%2 = x^6 +
475686187261802472185004872063344214708970723706575938151337567931484494333420980574237337285820416*x^4
+
144368804413018167939534590528428127097821218296427714041676769056670073530438292012969438295344075208508643521324460910077100894548722673546351583034736629808656847211501062491260969803478997139456*x^2
-
1232420717995426094961644589736104747645291356808112113882818041389512085244477663321817280884540842729479166548949486715251568653108358450677052967418655981948635207206606240317474825091191517544064416528268036110182976166957778173505140443323832876445978748518400000000000000
? minpoly_for_b=factor(charpoly_for_b)[2,1]
%3 = x^3 + 16859173009239080201258178812548231780748960464896*x^2 +
379958950908628987609069191779997752746095542653831161168225863215611652279362522770987284867055616*x
-
1110144458165434474895282512977345731888592578382628923344204116618433859722097011307309452250738834068301511695250321862791822049280000000
? u1=gcd(minpoly_for_b,x^2-p2(a))
%4 =
Mod(6568850470220229030621930170095627975462304965163155178168901727*variable_for_a^2
-
95550777494994518292482841466784170681152951023595449926275546956*variable_for_a
+ 779450226633417287470782202373991921824147913735444118318808288132,
variable_for_a^3 + 60*variable_for_a + 64)*x +
Mod(110745386549264325651314614492274469033150197099136335379622487358903388829145248271197688245169854407463657275392*variable_for_a^2
-
1610907088955420514513462240651416628480366900375602138151707818549350794589565409150647575392375084253962437656576*variable_for_a
-
1808959417621275933191329511303162003732057819674696749919726261644076808422537327403479555371305779116999564066816,
variable_for_a^3 + 60*variable_for_a + 64)
? u2=lift(u1)
%5 =
(6568850470220229030621930170095627975462304965163155178168901727*variable_for_a^2
-
95550777494994518292482841466784170681152951023595449926275546956*variable_for_a
+ 779450226633417287470782202373991921824147913735444118318808288132)*x +
(110745386549264325651314614492274469033150197099136335379622487358903388829145248271197688245169854407463657275392*variable_for_a^2
-
1610907088955420514513462240651416628480366900375602138151707818549350794589565409150647575392375084253962437656576*variable_for_a
-
1808959417621275933191329511303162003732057819674696749919726261644076808422537327403479555371305779116999564066816)
? formula_for_b=-subst(polcoeff(u2,0,x)/polcoeff(u2,1,x),variable_for_a,a)
%6 = Mod(189133117686159822165485681043654738588680060928*variable_for_a^2
+ 2055476375095129701009302875309311162506447683584*variable_for_a +
1945600371033366152866700970896778949964215615488, variable_for_a^3 +
60*variable_for_a + 64)



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