mersenneforum.org F12
 Register FAQ Search Today's Posts Mark Forums Read

 2017-10-14, 14:57 #12 Dr Sardonicus     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 Pari-GP's built-in capabilities, we obtain (up to sign and order) the previously-stated a and b for the C1133 factor of F12: ? 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 ? print(imag(z)) Code: 11512882899820054257144225772505994511430981968359355559240636997087397239461885404688940982112272498773691260355731224763278685518244745544198267923163368736091123701779226072209279679342867029500044275233215203437226071842172804234583591297137729569486761340213325710137879698831126615998659706343950808674850862574868322314902443424081205544133789500128645355501388833990928089030944977862262874243179626287736961093227838096073086612878632276868708056678373714902078426666851025890207418013027573248367464970951431311736356210867866665430397629513384884406535591 ?
 2017-10-16, 07:03 #13 LaurV 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...
 2018-01-23, 11:21 #14 siegert81   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.
 2018-11-25, 10:24 #15 Chara34122   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?
2018-11-26, 14:29   #16
Dr Sardonicus

Feb 2017
Nowhere

3×5×233 Posts

Quote:
 Originally Posted by Chara34122 For how long did it take to find A and B for c1133?
Not long. Not long at all.
Quote:
 And is A in this solution smallest possible?
AFAIK, the only way of making this determination is to factor C1133 completely, from this factorization determine all expressions as the sum of two squares, and then see what the smallest square summand of any of them turns out to be. So if you really want to know that answer, I'd say you've got your work cut out for you...

 2018-11-27, 11:04 #17 Chara34122   Nov 2018 Russia 1112 Posts I really want.