Algorithm: Given a large semiprime number N, find the smallest value of $A$ such that $N + A^2$ is a square
$begingroup$
Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)
Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.
Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.
algorithms
asked 4 hours ago
Nick JewettNick Jewett
113
New contributor
Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)
Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.
Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.
algorithms
asked 4 hours ago
Nick JewettNick Jewett
113
New contributor
Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
What does "that is a perfect square more than N" mean? How can N be more than N?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
@D.W. Sorry for the confusion, I meant that the square to be found is more than N by a perfect square such that s - N = B^2.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Can you edit the question to clarify it? We want questions to stand on their own, so that people dont' need to read the comments to understand the question. Are you looking to find the smallest A such that N + A^2 is a perfect square?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
Yes, precisely. I will update the question to clarify.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Interesting question. I've just suggested a clearer title :)
$endgroup$
– Pedro A
1 hour ago
add a comment |
$begingroup$
Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)
Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.
Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.
algorithms
asked 4 hours ago
Nick JewettNick Jewett
113
New contributor
Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)
Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.
Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.
algorithms
algorithms
asked 4 hours ago
Nick JewettNick Jewett
113
New contributor
Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Nick JewettNick Jewett
113
New contributor
Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 1 hour ago
Nick Jewett
asked 4 hours ago
Nick JewettNick Jewett
113
New contributor
Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Nick JewettNick Jewett
113
asked 4 hours ago
Nick JewettNick Jewett
113
113
New contributor
Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Nick Jewett is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
What does "that is a perfect square more than N" mean? How can N be more than N?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
@D.W. Sorry for the confusion, I meant that the square to be found is more than N by a perfect square such that s - N = B^2.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Can you edit the question to clarify it? We want questions to stand on their own, so that people dont' need to read the comments to understand the question. Are you looking to find the smallest A such that N + A^2 is a perfect square?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
Yes, precisely. I will update the question to clarify.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Interesting question. I've just suggested a clearer title :)
$endgroup$
– Pedro A
1 hour ago
add a comment |
$begingroup$
What does "that is a perfect square more than N" mean? How can N be more than N?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
@D.W. Sorry for the confusion, I meant that the square to be found is more than N by a perfect square such that s - N = B^2.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Can you edit the question to clarify it? We want questions to stand on their own, so that people dont' need to read the comments to understand the question. Are you looking to find the smallest A such that N + A^2 is a perfect square?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
Yes, precisely. I will update the question to clarify.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Interesting question. I've just suggested a clearer title :)
$endgroup$
– Pedro A
1 hour ago
$begingroup$
What does "that is a perfect square more than N" mean? How can N be more than N?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
What does "that is a perfect square more than N" mean? How can N be more than N?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
@D.W. Sorry for the confusion, I meant that the square to be found is more than N by a perfect square such that s - N = B^2.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
@D.W. Sorry for the confusion, I meant that the square to be found is more than N by a perfect square such that s - N = B^2.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Can you edit the question to clarify it? We want questions to stand on their own, so that people dont' need to read the comments to understand the question. Are you looking to find the smallest A such that N + A^2 is a perfect square?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
Can you edit the question to clarify it? We want questions to stand on their own, so that people dont' need to read the comments to understand the question. Are you looking to find the smallest A such that N + A^2 is a perfect square?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
Yes, precisely. I will update the question to clarify.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Yes, precisely. I will update the question to clarify.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Interesting question. I've just suggested a clearer title :)
$endgroup$
– Pedro A
1 hour ago
$begingroup$
Interesting question. I've just suggested a clearer title :)
$endgroup$
– Pedro A
1 hour ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
Then we have $N + B^2 = A^2$.
Thus $N = A^2 - B^2 = (A - B) cdot (A + B)$.
What's left is to look at the pairs of divisors of $N$.
If $N = X cdot Y$, we have $A - B = X$ and $A + B = Y$.
So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.
The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
Looks like one is not easier or harder than the other.
In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$.
So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.
Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
(Link suggested by Apass.Jack)
answered 4 hours ago
GassaGassa
695310
$endgroup$
$begingroup$
Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
$endgroup$
– Nick Jewett
4 hours ago
$begingroup$
I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
$endgroup$
– Nick Jewett
4 hours ago
add a comment |
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: "419"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Nick Jewett is a new contributor. Be nice, and check out our Code of Conduct.
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%2fcs.stackexchange.com%2fquestions%2f104795%2falgorithm-given-a-large-semiprime-number-n-find-the-smallest-value-of-a-such%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
Then we have $N + B^2 = A^2$.
Thus $N = A^2 - B^2 = (A - B) cdot (A + B)$.
What's left is to look at the pairs of divisors of $N$.
If $N = X cdot Y$, we have $A - B = X$ and $A + B = Y$.
So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.
The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
Looks like one is not easier or harder than the other.
In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$.
So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.
Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
(Link suggested by Apass.Jack)
answered 4 hours ago
GassaGassa
695310
$endgroup$
$begingroup$
Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
$endgroup$
– Nick Jewett
4 hours ago
$begingroup$
I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
$endgroup$
– Nick Jewett
4 hours ago
add a comment |
$begingroup$
In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
Then we have $N + B^2 = A^2$.
Thus $N = A^2 - B^2 = (A - B) cdot (A + B)$.
What's left is to look at the pairs of divisors of $N$.
If $N = X cdot Y$, we have $A - B = X$ and $A + B = Y$.
So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.
The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
Looks like one is not easier or harder than the other.
In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$.
So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.
Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
(Link suggested by Apass.Jack)
answered 4 hours ago
GassaGassa
695310
$endgroup$
$begingroup$
Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
$endgroup$
– Nick Jewett
4 hours ago
$begingroup$
I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
$endgroup$
– Nick Jewett
4 hours ago
add a comment |
$begingroup$
In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
Then we have $N + B^2 = A^2$.
Thus $N = A^2 - B^2 = (A - B) cdot (A + B)$.
What's left is to look at the pairs of divisors of $N$.
If $N = X cdot Y$, we have $A - B = X$ and $A + B = Y$.
So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.
The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
Looks like one is not easier or harder than the other.
In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$.
So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.
Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
(Link suggested by Apass.Jack)
answered 4 hours ago
GassaGassa
695310
$endgroup$
In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$.
Then we have $N + B^2 = A^2$.
Thus $N = A^2 - B^2 = (A - B) cdot (A + B)$.
What's left is to look at the pairs of divisors of $N$.
If $N = X cdot Y$, we have $A - B = X$ and $A + B = Y$.
So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.
The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization.
Looks like one is not easier or harder than the other.
In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$.
So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.
Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is.
(Link suggested by Apass.Jack)
answered 4 hours ago
GassaGassa
695310
edited 1 hour ago
answered 4 hours ago
GassaGassa
695310
answered 4 hours ago
GassaGassa
695310
answered 4 hours ago
GassaGassa
695310
695310
$begingroup$
Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
$endgroup$
– Nick Jewett
4 hours ago
$begingroup$
I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
$endgroup$
– Nick Jewett
4 hours ago
add a comment |
$begingroup$
Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
$endgroup$
– Nick Jewett
4 hours ago
$begingroup$
I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
$endgroup$
– Nick Jewett
4 hours ago
$begingroup$
Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
$endgroup$
– Nick Jewett
4 hours ago
$begingroup$
Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown.
$endgroup$
– Nick Jewett
4 hours ago
$begingroup$
I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
$endgroup$
– Nick Jewett
4 hours ago
$begingroup$
I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits).
$endgroup$
– Nick Jewett
4 hours ago
add a comment |
Nick Jewett is a new contributor. Be nice, and check out our Code of Conduct.
Nick Jewett is a new contributor. Be nice, and check out our Code of Conduct.
Nick Jewett is a new contributor. Be nice, and check out our Code of Conduct.
Nick Jewett is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science 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%2fcs.stackexchange.com%2fquestions%2f104795%2falgorithm-given-a-large-semiprime-number-n-find-the-smallest-value-of-a-such%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$
What does "that is a perfect square more than N" mean? How can N be more than N?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
@D.W. Sorry for the confusion, I meant that the square to be found is more than N by a perfect square such that s - N = B^2.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Can you edit the question to clarify it? We want questions to stand on their own, so that people dont' need to read the comments to understand the question. Are you looking to find the smallest A such that N + A^2 is a perfect square?
$endgroup$
– D.W.♦
2 hours ago
$begingroup$
Yes, precisely. I will update the question to clarify.
$endgroup$
– Nick Jewett
2 hours ago
$begingroup$
Interesting question. I've just suggested a clearer title :)
$endgroup$
– Pedro A
1 hour ago