20171014, 14:57  #12 
Feb 2017
Nowhere
3·5·233 Posts 
Suppose that we start with a single known expression for N as a sum of two squares,
N = A^2 + B^2 = (A + B*I)*(A  B*I), where A + B is odd, and gcd(A,B) = 1 . Suppose we find that p = a^2 + b^2 = (a + b*I)*(a  b*I) divides n. Since A  B*I and A + B*I are relatively prime, a + b*I will only divide one of them (in the ring of Gaussian integers Z[I] which enjoys unique factorization  and is even Euclidean!). Thus, we only obtain one expression for N/p as the sum of two squares, from the known expressions for N and p. The same holds for the quotients from dividing out any further prime factors. Of course, we could (assuming N is not p or a power of p) then obtain other expressions for N as a sum of two squares, but this does not help in further factoring the quotient after all known prime factors are divided out. Taking advantage of PariGP's builtin capabilities, we obtain (up to sign and order) the previouslystated a and b for the C1133 factor of F_{12}: ? gcd(1+2^2048*I,114689) %1 = 260 + 217*I ? gcd(1+2^2048*I,26017793) %2 = 4672 + 2047*I ? gcd(1+2^2048*I,63766529) %3 = 3248 + 7295*I ? gcd(1+2^2048*I,190274191361) %4 = 101500 + 424231*I ? gcd(1+2^2048*I,1256132134125569) %5 = 19707737 + 29457380*I ? gcd(1+2^2048*I,568630647535356955169033410940867804839360742060818433) %6 = 740185352931079335881406872 + 144070437084262635215071007*I ? z=(1+2^2048*I)/(%1*%2*%3*%4*%5*%6); ? print(real(z)) Code:
200632848085394229198405077309776409669556160755822894920478194045891524675173877582799789843512719390209285348887171584058267613825062519170949236869832740299611688879431491248560122275125138227835639875304442149679485916420376715785002453587853905329008047468218821526665318251417289791164787502264540469658007753188396466487968753988674615092615847790001421479841641921279595503860736218792224235350272376658369292603790019796500735806899786991660195728966759044116399240680328117271881207382080232786405040556863376322477213246700048245459183343930058344600346916 Code:
11512882899820054257144225772505994511430981968359355559240636997087397239461885404688940982112272498773691260355731224763278685518244745544198267923163368736091123701779226072209279679342867029500044275233215203437226071842172804234583591297137729569486761340213325710137879698831126615998659706343950808674850862574868322314902443424081205544133789500128645355501388833990928089030944977862262874243179626287736961093227838096073086612878632276868708056678373714902078426666851025890207418013027573248367464970951431311736356210867866665430397629513384884406535591 
20171016, 07:03  #13 
Romulan Interpreter
Jun 2011
Thailand
19×461 Posts 
I still remember some discussion here around where we could factor N if we could write it as a sum of two squares in two ways...

20180123, 11:21  #14 
Dec 2010
2×37 Posts 
The original information could be useful if Euler's factorization method was attempted.
If N = A^2 + B^2 = C^2 + D^2, then N can be factored. 
20181125, 10:24  #15 
Nov 2018
Russia
7 Posts 
For how long did it take to find A and B for c1133? And is A in this solution smallest possible?

20181126, 14:29  #16  
Feb 2017
Nowhere
3×5×233 Posts 
Not long. Not long at all.
Quote:


20181127, 11:04  #17 
Nov 2018
Russia
111_{2} Posts 
I really want.
