hermann on Wed, 28 Feb 2024 21:22:43 +0100


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

Re: foursquares.gp 

On 2024-02-28 16:39, Bill Allombert wrote:
Another way to state it is to say that one knows one square root of -1 modulo the composite (the square root is 2^2^11) so we need another one to factor N. 

N =
(2^2^12+1)/114689/26017793/63766529/190274191361/1256132134125569/568630647535356955169033410940867804839360742060818433;
A = gcd(2^2^11 + I,N);
? norm(A)==N
%16 = 1
? real(A)
%17 =
200632848085394229198405077309776409669556160755822894920478194045891524675173877582799789843512719390209285348887171584058267613825062519170949236869832740299611688879431491248560122275125138227835639875304442149679485916420376715785002453587853905329008047468218821526665318251417289791164787502264540469658007753188396466487968753988674615092615847790001421479841641921279595503860736218792224235350272376658369292603790019796500735806899786991660195728966759044116399240680328117271881207382080232786405040556863376322477213246700048245459183343930058344600346916
? imag(A)
%18 =
11512882899820054257144225772505994511430981968359355559240636997087397239461885404688940982112272498773691260355731224763278685518244745544198267923163368736091123701779226072209279679342867029500044275233215203437226071842172804234583591297137729569486761340213325710137879698831126615998659706343950808674850862574868322314902443424081205544133789500128645355501388833990928089030944977862262874243179626287736961093227838096073086612878632276868708056678373714902078426666851025890207418013027573248367464970951431311736356210867866665430397629513384884406535591

Cheers,
Bill.


Thanks — or with halfgcd():

hermann@7950x:~$ gp -q
? N = (2^2^12+1)/114689/26017793/63766529/190274191361/1256132134125569/568630647535356955169033410940867804839360742060818433; 
? [M,V]=halfgcd(2^2^11,N);[M[2,1],V[2]]
[11512882899820054257144225772505994511430981968359355559240636997087397239461885404688940982112272498773691260355731224763278685518244745544198267923163368736091123701779226072209279679342867029500044275233215203437226071842172804234583591297137729569486761340213325710137879698831126615998659706343950808674850862574868322314902443424081205544133789500128645355501388833990928089030944977862262874243179626287736961093227838096073086612878632276868708056678373714902078426666851025890207418013027573248367464970951431311736356210867866665430397629513384884406535591, 200632848085394229198405077309776409669556160755822894920478194045891524675173877582799789843512719390209285348887171584058267613825062519170949236869832740299611688879431491248560122275125138227835639875304442149679485916420376715785002453587853905329008047468218821526665318251417289791164787502264540469658007753188396466487968753988674615092615847790001421479841641921279595503860736218792224235350272376658369292603790019796500735806899786991660195728966759044116399240680328117271881207382080232786405040556863376322477213246700048245459183343930058344600346916] 
?


Regards,

Hermann.