mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2017-10-14, 14:57   #12
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3·5·233 Posts
Default

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
?
Dr Sardonicus is offline   Reply With Quote
Old 2017-10-16, 07:03   #13
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

19×461 Posts
Default

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...
LaurV is offline   Reply With Quote
Old 2018-01-23, 11:21   #14
siegert81
 
Dec 2010

2×37 Posts
Default

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.
siegert81 is offline   Reply With Quote
Old 2018-11-25, 10:24   #15
Chara34122
 
Nov 2018
Russia

7 Posts
Default

For how long did it take to find A and B for c1133? And is A in this solution smallest possible?
Chara34122 is offline   Reply With Quote
Old 2018-11-26, 14:29   #16
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×5×233 Posts
Default

Quote:
Originally Posted by Chara34122 View Post
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...
Dr Sardonicus is offline   Reply With Quote
Old 2018-11-27, 11:04   #17
Chara34122
 
Nov 2018
Russia

1112 Posts
Cool

I really want.
Chara34122 is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 02:26.

Thu Oct 1 02:26:32 UTC 2020 up 20 days, 23:37, 1 user, load averages: 1.77, 1.49, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.