Can the sum of two squares be used to factor large numbers?
$begingroup$
The method described below is different from Euler sum of two squares factorization method. The method below does not require 2 sum of two squares representations to factor a number.
This post was inspired by the post on using the sum of two squares to determine if a number is square free (see Can the sum of two squares be used to determine if a number is square free?"). We will show below that the sum of two squares can definitely be used to factor integers. However, at this point in time, it is not known if this method is fast enough to factor large numbers (hundred digits).
We start with a simple example of $N=a^2+b^2=3*5=15$. We know that this number cannot be decomposed into a sum of two squares (2sq rep). So we square $N$ to get $N^2=M=3^2*5^2=225$. We calculate the two squares representation (2sq rep) of $M$ and find $M=9^2 + 12^2$. At this point we take the GCD of $GCD(9^2,12^2)=9$. So $9$ is a common factor and this means that $M$ can be rewritten as $M=3^2*3^2 + 3^2*4^2= 3^2*(3^2+ 4^2)=3^2*5^2$. The last step is not needed. Once a common factor is found, we know that it is a factor of M and its square root is a factor of N.
To show that the method works for an arbitrary numbers we will provide few more examples. However at this point we only consider numbers of the form $N=pq$ or numbers of the form $N=pq^2$.
Example #1. $N=7*37=259$, $N^2=259^2=67081=84^2 + 245^2$. We calculate $GCD(84^2,245^2)=7^2$. So we find that $7^2$ is a factor of $N^2$ and that $7$ is a factor of $N$.
Example #2. $N=13*17=221$, $N^2=221^2=48841=21^2 + 220^2=85^2 + 204^2= 104^2 + 195^2=140^2 + 171^2$. We calculate the GCD for each 2sq rep.
$$
begin{split}
gcd(21^2,220^2)&=1\
gcd(85^2,204^2)&=289=17^2\
gcd(104^2,195^2)&=169=13^2\
gcd(140^2,171^2)&=1
end{split}
$$
We that the first and last 2sq rep give no information on the factors of $N^2$ but the 2nd and 3rd 2sq rep provide the squares of the factors of N.
This example shows that the sum of two squares can factor an integer provided we consider all 2sq representations of $N^2$ since we don't know which one is going to provide us with the information on the factors.
We now provide an example where the sum of two squares does not work.
Example #3. $N=19*31=589$. This number does not have a sum of two squares. We square it to get $N^2=589^2=0^2 + 589^2$. This 2sq rep provides no information on the original factors of N.
The question is this: can the sum of two squares get the factors of $N^2$ in a reasonable amount of time?
number-theory elementary-number-theory prime-numbers factoring sums-of-squares
asked Jan 8 at 18:15
user25406user25406
3891413
$endgroup$
|
show 19 more comments
$begingroup$
The method described below is different from Euler sum of two squares factorization method. The method below does not require 2 sum of two squares representations to factor a number.
This post was inspired by the post on using the sum of two squares to determine if a number is square free (see Can the sum of two squares be used to determine if a number is square free?"). We will show below that the sum of two squares can definitely be used to factor integers. However, at this point in time, it is not known if this method is fast enough to factor large numbers (hundred digits).
We start with a simple example of $N=a^2+b^2=3*5=15$. We know that this number cannot be decomposed into a sum of two squares (2sq rep). So we square $N$ to get $N^2=M=3^2*5^2=225$. We calculate the two squares representation (2sq rep) of $M$ and find $M=9^2 + 12^2$. At this point we take the GCD of $GCD(9^2,12^2)=9$. So $9$ is a common factor and this means that $M$ can be rewritten as $M=3^2*3^2 + 3^2*4^2= 3^2*(3^2+ 4^2)=3^2*5^2$. The last step is not needed. Once a common factor is found, we know that it is a factor of M and its square root is a factor of N.
To show that the method works for an arbitrary numbers we will provide few more examples. However at this point we only consider numbers of the form $N=pq$ or numbers of the form $N=pq^2$.
Example #1. $N=7*37=259$, $N^2=259^2=67081=84^2 + 245^2$. We calculate $GCD(84^2,245^2)=7^2$. So we find that $7^2$ is a factor of $N^2$ and that $7$ is a factor of $N$.
Example #2. $N=13*17=221$, $N^2=221^2=48841=21^2 + 220^2=85^2 + 204^2= 104^2 + 195^2=140^2 + 171^2$. We calculate the GCD for each 2sq rep.
$$
begin{split}
gcd(21^2,220^2)&=1\
gcd(85^2,204^2)&=289=17^2\
gcd(104^2,195^2)&=169=13^2\
gcd(140^2,171^2)&=1
end{split}
$$
We that the first and last 2sq rep give no information on the factors of $N^2$ but the 2nd and 3rd 2sq rep provide the squares of the factors of N.
This example shows that the sum of two squares can factor an integer provided we consider all 2sq representations of $N^2$ since we don't know which one is going to provide us with the information on the factors.
We now provide an example where the sum of two squares does not work.
Example #3. $N=19*31=589$. This number does not have a sum of two squares. We square it to get $N^2=589^2=0^2 + 589^2$. This 2sq rep provides no information on the original factors of N.
The question is this: can the sum of two squares get the factors of $N^2$ in a reasonable amount of time?
number-theory elementary-number-theory prime-numbers factoring sums-of-squares
asked Jan 8 at 18:15
user25406user25406
3891413
$endgroup$
$begingroup$
thanks for the edit.
$endgroup$
– user25406
Jan 8 at 18:28
$begingroup$
See Euler's factorization method
$endgroup$
– Robert Israel
Jan 8 at 18:49
$begingroup$
Yes, I am aware of Euler method but the above method is different. It does not need 2 "sum of 2 squares representation". The first example of $N^2=7^2*37^2= 84^2 + 245^2$ has only one 2sq representation yet we were able to factor the number. Euler's method would not have been able to factor this one.
$endgroup$
– user25406
Jan 8 at 18:58
1
$begingroup$
@user25406, I downloaded the PARI/GP source code for the tool you mentioned. When I ran it, I was able to compute the representation of 100 digit numbers as sums of squares. The only other step is to compute the gcd of each of the representations, which can be done fairly quickly (polynomial time).
$endgroup$
– coDE_RP
Jan 8 at 20:01
2
$begingroup$
A representation $N=x^2+y^2$ is called primitive if $gcd(x,y)=1$. It is well known that $N$ has no primitive representations if it is divisible by primes $pequiv 3 pmod 4$. What this means is if there are primes $pequiv 3 pmod 4$ that divides $N$ and you can find a sum of squares representation, $d =gcd(x,y)neq 1$ and $d$ always gives you a product of $p^2$. So yes you can factor certain integers efficiently this way. However for products of $pequiv 1 pmod 4$ I believe it is always possible to form primitive representations, so that $gcd(x,y)=1$.
$endgroup$
– Yong Hao Ng
Jan 9 at 9:49
|
show 19 more comments
$begingroup$
The method described below is different from Euler sum of two squares factorization method. The method below does not require 2 sum of two squares representations to factor a number.
This post was inspired by the post on using the sum of two squares to determine if a number is square free (see Can the sum of two squares be used to determine if a number is square free?"). We will show below that the sum of two squares can definitely be used to factor integers. However, at this point in time, it is not known if this method is fast enough to factor large numbers (hundred digits).
We start with a simple example of $N=a^2+b^2=3*5=15$. We know that this number cannot be decomposed into a sum of two squares (2sq rep). So we square $N$ to get $N^2=M=3^2*5^2=225$. We calculate the two squares representation (2sq rep) of $M$ and find $M=9^2 + 12^2$. At this point we take the GCD of $GCD(9^2,12^2)=9$. So $9$ is a common factor and this means that $M$ can be rewritten as $M=3^2*3^2 + 3^2*4^2= 3^2*(3^2+ 4^2)=3^2*5^2$. The last step is not needed. Once a common factor is found, we know that it is a factor of M and its square root is a factor of N.
To show that the method works for an arbitrary numbers we will provide few more examples. However at this point we only consider numbers of the form $N=pq$ or numbers of the form $N=pq^2$.
Example #1. $N=7*37=259$, $N^2=259^2=67081=84^2 + 245^2$. We calculate $GCD(84^2,245^2)=7^2$. So we find that $7^2$ is a factor of $N^2$ and that $7$ is a factor of $N$.
Example #2. $N=13*17=221$, $N^2=221^2=48841=21^2 + 220^2=85^2 + 204^2= 104^2 + 195^2=140^2 + 171^2$. We calculate the GCD for each 2sq rep.
$$
begin{split}
gcd(21^2,220^2)&=1\
gcd(85^2,204^2)&=289=17^2\
gcd(104^2,195^2)&=169=13^2\
gcd(140^2,171^2)&=1
end{split}
$$
We that the first and last 2sq rep give no information on the factors of $N^2$ but the 2nd and 3rd 2sq rep provide the squares of the factors of N.
This example shows that the sum of two squares can factor an integer provided we consider all 2sq representations of $N^2$ since we don't know which one is going to provide us with the information on the factors.
We now provide an example where the sum of two squares does not work.
Example #3. $N=19*31=589$. This number does not have a sum of two squares. We square it to get $N^2=589^2=0^2 + 589^2$. This 2sq rep provides no information on the original factors of N.
The question is this: can the sum of two squares get the factors of $N^2$ in a reasonable amount of time?
number-theory elementary-number-theory prime-numbers factoring sums-of-squares
asked Jan 8 at 18:15
user25406user25406
3891413
$endgroup$
The method described below is different from Euler sum of two squares factorization method. The method below does not require 2 sum of two squares representations to factor a number.
This post was inspired by the post on using the sum of two squares to determine if a number is square free (see Can the sum of two squares be used to determine if a number is square free?"). We will show below that the sum of two squares can definitely be used to factor integers. However, at this point in time, it is not known if this method is fast enough to factor large numbers (hundred digits).
We start with a simple example of $N=a^2+b^2=3*5=15$. We know that this number cannot be decomposed into a sum of two squares (2sq rep). So we square $N$ to get $N^2=M=3^2*5^2=225$. We calculate the two squares representation (2sq rep) of $M$ and find $M=9^2 + 12^2$. At this point we take the GCD of $GCD(9^2,12^2)=9$. So $9$ is a common factor and this means that $M$ can be rewritten as $M=3^2*3^2 + 3^2*4^2= 3^2*(3^2+ 4^2)=3^2*5^2$. The last step is not needed. Once a common factor is found, we know that it is a factor of M and its square root is a factor of N.
To show that the method works for an arbitrary numbers we will provide few more examples. However at this point we only consider numbers of the form $N=pq$ or numbers of the form $N=pq^2$.
Example #1. $N=7*37=259$, $N^2=259^2=67081=84^2 + 245^2$. We calculate $GCD(84^2,245^2)=7^2$. So we find that $7^2$ is a factor of $N^2$ and that $7$ is a factor of $N$.
Example #2. $N=13*17=221$, $N^2=221^2=48841=21^2 + 220^2=85^2 + 204^2= 104^2 + 195^2=140^2 + 171^2$. We calculate the GCD for each 2sq rep.
$$
begin{split}
gcd(21^2,220^2)&=1\
gcd(85^2,204^2)&=289=17^2\
gcd(104^2,195^2)&=169=13^2\
gcd(140^2,171^2)&=1
end{split}
$$
We that the first and last 2sq rep give no information on the factors of $N^2$ but the 2nd and 3rd 2sq rep provide the squares of the factors of N.
This example shows that the sum of two squares can factor an integer provided we consider all 2sq representations of $N^2$ since we don't know which one is going to provide us with the information on the factors.
We now provide an example where the sum of two squares does not work.
Example #3. $N=19*31=589$. This number does not have a sum of two squares. We square it to get $N^2=589^2=0^2 + 589^2$. This 2sq rep provides no information on the original factors of N.
The question is this: can the sum of two squares get the factors of $N^2$ in a reasonable amount of time?
number-theory elementary-number-theory prime-numbers factoring sums-of-squares
number-theory elementary-number-theory prime-numbers factoring sums-of-squares
asked Jan 8 at 18:15
user25406user25406
3891413
asked Jan 8 at 18:15
user25406user25406
3891413
edited Jan 17 at 19:11
user25406
asked Jan 8 at 18:15
user25406user25406
3891413
asked Jan 8 at 18:15
user25406user25406
3891413
asked Jan 8 at 18:15
user25406user25406
3891413
3891413
$begingroup$
thanks for the edit.
$endgroup$
– user25406
Jan 8 at 18:28
$begingroup$
See Euler's factorization method
$endgroup$
– Robert Israel
Jan 8 at 18:49
$begingroup$
Yes, I am aware of Euler method but the above method is different. It does not need 2 "sum of 2 squares representation". The first example of $N^2=7^2*37^2= 84^2 + 245^2$ has only one 2sq representation yet we were able to factor the number. Euler's method would not have been able to factor this one.
$endgroup$
– user25406
Jan 8 at 18:58
1
$begingroup$
@user25406, I downloaded the PARI/GP source code for the tool you mentioned. When I ran it, I was able to compute the representation of 100 digit numbers as sums of squares. The only other step is to compute the gcd of each of the representations, which can be done fairly quickly (polynomial time).
$endgroup$
– coDE_RP
Jan 8 at 20:01
2
$begingroup$
A representation $N=x^2+y^2$ is called primitive if $gcd(x,y)=1$. It is well known that $N$ has no primitive representations if it is divisible by primes $pequiv 3 pmod 4$. What this means is if there are primes $pequiv 3 pmod 4$ that divides $N$ and you can find a sum of squares representation, $d =gcd(x,y)neq 1$ and $d$ always gives you a product of $p^2$. So yes you can factor certain integers efficiently this way. However for products of $pequiv 1 pmod 4$ I believe it is always possible to form primitive representations, so that $gcd(x,y)=1$.
$endgroup$
– Yong Hao Ng
Jan 9 at 9:49
|
show 19 more comments
$begingroup$
thanks for the edit.
$endgroup$
– user25406
Jan 8 at 18:28
$begingroup$
See Euler's factorization method
$endgroup$
– Robert Israel
Jan 8 at 18:49
$begingroup$
Yes, I am aware of Euler method but the above method is different. It does not need 2 "sum of 2 squares representation". The first example of $N^2=7^2*37^2= 84^2 + 245^2$ has only one 2sq representation yet we were able to factor the number. Euler's method would not have been able to factor this one.
$endgroup$
– user25406
Jan 8 at 18:58
1
$begingroup$
@user25406, I downloaded the PARI/GP source code for the tool you mentioned. When I ran it, I was able to compute the representation of 100 digit numbers as sums of squares. The only other step is to compute the gcd of each of the representations, which can be done fairly quickly (polynomial time).
$endgroup$
– coDE_RP
Jan 8 at 20:01
2
$begingroup$
A representation $N=x^2+y^2$ is called primitive if $gcd(x,y)=1$. It is well known that $N$ has no primitive representations if it is divisible by primes $pequiv 3 pmod 4$. What this means is if there are primes $pequiv 3 pmod 4$ that divides $N$ and you can find a sum of squares representation, $d =gcd(x,y)neq 1$ and $d$ always gives you a product of $p^2$. So yes you can factor certain integers efficiently this way. However for products of $pequiv 1 pmod 4$ I believe it is always possible to form primitive representations, so that $gcd(x,y)=1$.
$endgroup$
– Yong Hao Ng
Jan 9 at 9:49
$begingroup$
thanks for the edit.
$endgroup$
– user25406
Jan 8 at 18:28
$begingroup$
thanks for the edit.
$endgroup$
– user25406
Jan 8 at 18:28
$begingroup$
See Euler's factorization method
$endgroup$
– Robert Israel
Jan 8 at 18:49
$begingroup$
See Euler's factorization method
$endgroup$
– Robert Israel
Jan 8 at 18:49
$begingroup$
Yes, I am aware of Euler method but the above method is different. It does not need 2 "sum of 2 squares representation". The first example of $N^2=7^2*37^2= 84^2 + 245^2$ has only one 2sq representation yet we were able to factor the number. Euler's method would not have been able to factor this one.
$endgroup$
– user25406
Jan 8 at 18:58
$begingroup$
Yes, I am aware of Euler method but the above method is different. It does not need 2 "sum of 2 squares representation". The first example of $N^2=7^2*37^2= 84^2 + 245^2$ has only one 2sq representation yet we were able to factor the number. Euler's method would not have been able to factor this one.
$endgroup$
– user25406
Jan 8 at 18:58
1
1
$begingroup$
@user25406, I downloaded the PARI/GP source code for the tool you mentioned. When I ran it, I was able to compute the representation of 100 digit numbers as sums of squares. The only other step is to compute the gcd of each of the representations, which can be done fairly quickly (polynomial time).
$endgroup$
– coDE_RP
Jan 8 at 20:01
$begingroup$
@user25406, I downloaded the PARI/GP source code for the tool you mentioned. When I ran it, I was able to compute the representation of 100 digit numbers as sums of squares. The only other step is to compute the gcd of each of the representations, which can be done fairly quickly (polynomial time).
$endgroup$
– coDE_RP
Jan 8 at 20:01
2
2
$begingroup$
A representation $N=x^2+y^2$ is called primitive if $gcd(x,y)=1$. It is well known that $N$ has no primitive representations if it is divisible by primes $pequiv 3 pmod 4$. What this means is if there are primes $pequiv 3 pmod 4$ that divides $N$ and you can find a sum of squares representation, $d =gcd(x,y)neq 1$ and $d$ always gives you a product of $p^2$. So yes you can factor certain integers efficiently this way. However for products of $pequiv 1 pmod 4$ I believe it is always possible to form primitive representations, so that $gcd(x,y)=1$.
$endgroup$
– Yong Hao Ng
Jan 9 at 9:49
$begingroup$
A representation $N=x^2+y^2$ is called primitive if $gcd(x,y)=1$. It is well known that $N$ has no primitive representations if it is divisible by primes $pequiv 3 pmod 4$. What this means is if there are primes $pequiv 3 pmod 4$ that divides $N$ and you can find a sum of squares representation, $d =gcd(x,y)neq 1$ and $d$ always gives you a product of $p^2$. So yes you can factor certain integers efficiently this way. However for products of $pequiv 1 pmod 4$ I believe it is always possible to form primitive representations, so that $gcd(x,y)=1$.
$endgroup$
– Yong Hao Ng
Jan 9 at 9:49
|
show 19 more comments
0
active
oldest
votes
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3066531%2fcan-the-sum-of-two-squares-be-used-to-factor-large-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3066531%2fcan-the-sum-of-two-squares-be-used-to-factor-large-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
thanks for the edit.
$endgroup$
– user25406
Jan 8 at 18:28
$begingroup$
See Euler's factorization method
$endgroup$
– Robert Israel
Jan 8 at 18:49
$begingroup$
Yes, I am aware of Euler method but the above method is different. It does not need 2 "sum of 2 squares representation". The first example of $N^2=7^2*37^2= 84^2 + 245^2$ has only one 2sq representation yet we were able to factor the number. Euler's method would not have been able to factor this one.
$endgroup$
– user25406
Jan 8 at 18:58
1
$begingroup$
@user25406, I downloaded the PARI/GP source code for the tool you mentioned. When I ran it, I was able to compute the representation of 100 digit numbers as sums of squares. The only other step is to compute the gcd of each of the representations, which can be done fairly quickly (polynomial time).
$endgroup$
– coDE_RP
Jan 8 at 20:01
2
$begingroup$
A representation $N=x^2+y^2$ is called primitive if $gcd(x,y)=1$. It is well known that $N$ has no primitive representations if it is divisible by primes $pequiv 3 pmod 4$. What this means is if there are primes $pequiv 3 pmod 4$ that divides $N$ and you can find a sum of squares representation, $d =gcd(x,y)neq 1$ and $d$ always gives you a product of $p^2$. So yes you can factor certain integers efficiently this way. However for products of $pequiv 1 pmod 4$ I believe it is always possible to form primitive representations, so that $gcd(x,y)=1$.
$endgroup$
– Yong Hao Ng
Jan 9 at 9:49