Mixing
Factorization and the difference of two squares
$begingroup$
While contemplating on the mathematics behind RSA cryptography, I tried to play around how to possibly find the factors $p,q$ in a rather more algebraic and elementary way. What I initially found out that I can manage to factor any odd number $c$ if I could somehow manage to find integer solutions to $a^2 – b^2 = c$. If non trivial solution exists, then if $c=p cdot q$ then $p=a-b$ and $q=a+b$. This is of course provided that $c$ is not a perfect square so that $p$ and $q$ will be distinct.
Example: $$c=15=3cdot5$$
$$p,q=3,5$$
$$a,b=4,1$$
$$4^2 – 1^2 = 15$$
My questions are:
Is this approach to factorization trivial and not at all new?
In terms of computational algorithms, is this more efficient or worse than other factorization algorithm?
PS: This technique can also be extended to factorization of any odd non perfect square number. The trivial solution will be: if $c=2k+1$, then $a=k+1$ is a solution.
number-theory prime-factorization
asked Jan 13 at 10:59
April Jashmer Carba AntingApril Jashmer Carba Anting
578
$endgroup$
add a comment |
$begingroup$
While contemplating on the mathematics behind RSA cryptography, I tried to play around how to possibly find the factors $p,q$ in a rather more algebraic and elementary way. What I initially found out that I can manage to factor any odd number $c$ if I could somehow manage to find integer solutions to $a^2 – b^2 = c$. If non trivial solution exists, then if $c=p cdot q$ then $p=a-b$ and $q=a+b$. This is of course provided that $c$ is not a perfect square so that $p$ and $q$ will be distinct.
Example: $$c=15=3cdot5$$
$$p,q=3,5$$
$$a,b=4,1$$
$$4^2 – 1^2 = 15$$
My questions are:
Is this approach to factorization trivial and not at all new?
In terms of computational algorithms, is this more efficient or worse than other factorization algorithm?
PS: This technique can also be extended to factorization of any odd non perfect square number. The trivial solution will be: if $c=2k+1$, then $a=k+1$ is a solution.
number-theory prime-factorization
asked Jan 13 at 10:59
April Jashmer Carba AntingApril Jashmer Carba Anting
578
$endgroup$
1
$begingroup$
Any expression of $c$ as the value of a reducible polynomial would work. If you could write $c=a^2+5ab+6b^2$, say, then you'd know that $c=(a+2b)(a+3b)$. But...so what? There's no apparent way to test $c$ for that property.
$endgroup$
– lulu
Jan 13 at 11:17
$begingroup$
Yes I understand that. But my question is definitely about using such argument as means to obtain an algorithm to find, say, the factors any odd number $c$. Example would be try to rearrange the equation into: $b^2=a^2+c$. Given $c$ iterate values to $a$ and then check if whether $a^2+c$ is a perfect square.
$endgroup$
– April Jashmer Carba Anting
Jan 13 at 11:24
$begingroup$
But, again, we could do that with any reducible polynomial. In the end, you are just doing a simple search through all the numbers less than $c$, and if you are going to do that then why not just ask, in turn, if each number you try is a factor of $c$? At least with that method you can restrict your search to primes which might save a lot of time.
$endgroup$
– lulu
Jan 13 at 11:28
$begingroup$
Take a look at Fermat factorization method. en.wikipedia.org/wiki/Fermat%27s_factorization_method
$endgroup$
– user25406
Jan 13 at 12:35
1
$begingroup$
It is hopeless to find a non-trivial difference of two squares equal to a huge composite number, unless the number is very special, for example having almost equal prime factors. In general, the mehod will be inferior to a usual factorization plan.
$endgroup$
– Peter
Jan 13 at 19:09
add a comment |
$begingroup$
While contemplating on the mathematics behind RSA cryptography, I tried to play around how to possibly find the factors $p,q$ in a rather more algebraic and elementary way. What I initially found out that I can manage to factor any odd number $c$ if I could somehow manage to find integer solutions to $a^2 – b^2 = c$. If non trivial solution exists, then if $c=p cdot q$ then $p=a-b$ and $q=a+b$. This is of course provided that $c$ is not a perfect square so that $p$ and $q$ will be distinct.
Example: $$c=15=3cdot5$$
$$p,q=3,5$$
$$a,b=4,1$$
$$4^2 – 1^2 = 15$$
My questions are:
Is this approach to factorization trivial and not at all new?
In terms of computational algorithms, is this more efficient or worse than other factorization algorithm?
PS: This technique can also be extended to factorization of any odd non perfect square number. The trivial solution will be: if $c=2k+1$, then $a=k+1$ is a solution.
number-theory prime-factorization
asked Jan 13 at 10:59
April Jashmer Carba AntingApril Jashmer Carba Anting
578
$endgroup$
While contemplating on the mathematics behind RSA cryptography, I tried to play around how to possibly find the factors $p,q$ in a rather more algebraic and elementary way. What I initially found out that I can manage to factor any odd number $c$ if I could somehow manage to find integer solutions to $a^2 – b^2 = c$. If non trivial solution exists, then if $c=p cdot q$ then $p=a-b$ and $q=a+b$. This is of course provided that $c$ is not a perfect square so that $p$ and $q$ will be distinct.
Example: $$c=15=3cdot5$$
$$p,q=3,5$$
$$a,b=4,1$$
$$4^2 – 1^2 = 15$$
My questions are:
Is this approach to factorization trivial and not at all new?
In terms of computational algorithms, is this more efficient or worse than other factorization algorithm?
PS: This technique can also be extended to factorization of any odd non perfect square number. The trivial solution will be: if $c=2k+1$, then $a=k+1$ is a solution.
number-theory prime-factorization
number-theory prime-factorization
asked Jan 13 at 10:59
April Jashmer Carba AntingApril Jashmer Carba Anting
578
asked Jan 13 at 10:59
April Jashmer Carba AntingApril Jashmer Carba Anting
578
asked Jan 13 at 10:59
April Jashmer Carba AntingApril Jashmer Carba Anting
578
asked Jan 13 at 10:59
April Jashmer Carba AntingApril Jashmer Carba Anting
578
asked Jan 13 at 10:59
April Jashmer Carba AntingApril Jashmer Carba Anting
578
578
1
$begingroup$
Any expression of $c$ as the value of a reducible polynomial would work. If you could write $c=a^2+5ab+6b^2$, say, then you'd know that $c=(a+2b)(a+3b)$. But...so what? There's no apparent way to test $c$ for that property.
$endgroup$
– lulu
Jan 13 at 11:17
$begingroup$
Yes I understand that. But my question is definitely about using such argument as means to obtain an algorithm to find, say, the factors any odd number $c$. Example would be try to rearrange the equation into: $b^2=a^2+c$. Given $c$ iterate values to $a$ and then check if whether $a^2+c$ is a perfect square.
$endgroup$
– April Jashmer Carba Anting
Jan 13 at 11:24
$begingroup$
But, again, we could do that with any reducible polynomial. In the end, you are just doing a simple search through all the numbers less than $c$, and if you are going to do that then why not just ask, in turn, if each number you try is a factor of $c$? At least with that method you can restrict your search to primes which might save a lot of time.
$endgroup$
– lulu
Jan 13 at 11:28
$begingroup$
Take a look at Fermat factorization method. en.wikipedia.org/wiki/Fermat%27s_factorization_method
$endgroup$
– user25406
Jan 13 at 12:35
1
$begingroup$
It is hopeless to find a non-trivial difference of two squares equal to a huge composite number, unless the number is very special, for example having almost equal prime factors. In general, the mehod will be inferior to a usual factorization plan.
$endgroup$
– Peter
Jan 13 at 19:09
add a comment |
1
$begingroup$
Any expression of $c$ as the value of a reducible polynomial would work. If you could write $c=a^2+5ab+6b^2$, say, then you'd know that $c=(a+2b)(a+3b)$. But...so what? There's no apparent way to test $c$ for that property.
$endgroup$
– lulu
Jan 13 at 11:17
$begingroup$
Yes I understand that. But my question is definitely about using such argument as means to obtain an algorithm to find, say, the factors any odd number $c$. Example would be try to rearrange the equation into: $b^2=a^2+c$. Given $c$ iterate values to $a$ and then check if whether $a^2+c$ is a perfect square.
$endgroup$
– April Jashmer Carba Anting
Jan 13 at 11:24
$begingroup$
But, again, we could do that with any reducible polynomial. In the end, you are just doing a simple search through all the numbers less than $c$, and if you are going to do that then why not just ask, in turn, if each number you try is a factor of $c$? At least with that method you can restrict your search to primes which might save a lot of time.
$endgroup$
– lulu
Jan 13 at 11:28
$begingroup$
Take a look at Fermat factorization method. en.wikipedia.org/wiki/Fermat%27s_factorization_method
$endgroup$
– user25406
Jan 13 at 12:35
1
$begingroup$
It is hopeless to find a non-trivial difference of two squares equal to a huge composite number, unless the number is very special, for example having almost equal prime factors. In general, the mehod will be inferior to a usual factorization plan.
$endgroup$
– Peter
Jan 13 at 19:09
1
1
$begingroup$
Any expression of $c$ as the value of a reducible polynomial would work. If you could write $c=a^2+5ab+6b^2$, say, then you'd know that $c=(a+2b)(a+3b)$. But...so what? There's no apparent way to test $c$ for that property.
$endgroup$
– lulu
Jan 13 at 11:17
$begingroup$
Any expression of $c$ as the value of a reducible polynomial would work. If you could write $c=a^2+5ab+6b^2$, say, then you'd know that $c=(a+2b)(a+3b)$. But...so what? There's no apparent way to test $c$ for that property.
$endgroup$
– lulu
Jan 13 at 11:17
$begingroup$
Yes I understand that. But my question is definitely about using such argument as means to obtain an algorithm to find, say, the factors any odd number $c$. Example would be try to rearrange the equation into: $b^2=a^2+c$. Given $c$ iterate values to $a$ and then check if whether $a^2+c$ is a perfect square.
$endgroup$
– April Jashmer Carba Anting
Jan 13 at 11:24
$begingroup$
Yes I understand that. But my question is definitely about using such argument as means to obtain an algorithm to find, say, the factors any odd number $c$. Example would be try to rearrange the equation into: $b^2=a^2+c$. Given $c$ iterate values to $a$ and then check if whether $a^2+c$ is a perfect square.
$endgroup$
– April Jashmer Carba Anting
Jan 13 at 11:24
$begingroup$
But, again, we could do that with any reducible polynomial. In the end, you are just doing a simple search through all the numbers less than $c$, and if you are going to do that then why not just ask, in turn, if each number you try is a factor of $c$? At least with that method you can restrict your search to primes which might save a lot of time.
$endgroup$
– lulu
Jan 13 at 11:28
$begingroup$
But, again, we could do that with any reducible polynomial. In the end, you are just doing a simple search through all the numbers less than $c$, and if you are going to do that then why not just ask, in turn, if each number you try is a factor of $c$? At least with that method you can restrict your search to primes which might save a lot of time.
$endgroup$
– lulu
Jan 13 at 11:28
$begingroup$
Take a look at Fermat factorization method. en.wikipedia.org/wiki/Fermat%27s_factorization_method
$endgroup$
– user25406
Jan 13 at 12:35
$begingroup$
Take a look at Fermat factorization method. en.wikipedia.org/wiki/Fermat%27s_factorization_method
$endgroup$
– user25406
Jan 13 at 12:35
1
1
$begingroup$
It is hopeless to find a non-trivial difference of two squares equal to a huge composite number, unless the number is very special, for example having almost equal prime factors. In general, the mehod will be inferior to a usual factorization plan.
$endgroup$
– Peter
Jan 13 at 19:09
$begingroup$
It is hopeless to find a non-trivial difference of two squares equal to a huge composite number, unless the number is very special, for example having almost equal prime factors. In general, the mehod will be inferior to a usual factorization plan.
$endgroup$
– Peter
Jan 13 at 19:09
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f3071881%2ffactorization-and-the-difference-of-two-squares%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%2f3071881%2ffactorization-and-the-difference-of-two-squares%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
1
$begingroup$
Any expression of $c$ as the value of a reducible polynomial would work. If you could write $c=a^2+5ab+6b^2$, say, then you'd know that $c=(a+2b)(a+3b)$. But...so what? There's no apparent way to test $c$ for that property.
$endgroup$
– lulu
Jan 13 at 11:17
$begingroup$
Yes I understand that. But my question is definitely about using such argument as means to obtain an algorithm to find, say, the factors any odd number $c$. Example would be try to rearrange the equation into: $b^2=a^2+c$. Given $c$ iterate values to $a$ and then check if whether $a^2+c$ is a perfect square.
$endgroup$
– April Jashmer Carba Anting
Jan 13 at 11:24
$begingroup$
But, again, we could do that with any reducible polynomial. In the end, you are just doing a simple search through all the numbers less than $c$, and if you are going to do that then why not just ask, in turn, if each number you try is a factor of $c$? At least with that method you can restrict your search to primes which might save a lot of time.
$endgroup$
– lulu
Jan 13 at 11:28
$begingroup$
Take a look at Fermat factorization method. en.wikipedia.org/wiki/Fermat%27s_factorization_method
$endgroup$
– user25406
Jan 13 at 12:35
1
$begingroup$
It is hopeless to find a non-trivial difference of two squares equal to a huge composite number, unless the number is very special, for example having almost equal prime factors. In general, the mehod will be inferior to a usual factorization plan.
$endgroup$
– Peter
Jan 13 at 19:09