Algorithm: Given a large semiprime number N, find the next perfect square that is a perfect square more than...
Trying to detect if any checked values contains a specific string
No option to ask a question in https://developer.salesforce.com discussion forums
What are some ways of extending a description of a scenery?
Insecure private-key encryption
Writing dialogues for characters whose first language is not English
smartctl reports overall health test as passed but the tests failed?
I have trouble understanding this fallacy: "If A, then B. Therefore if not-B, then not-A."
Plausible reason for gold-digging ant
What's the reason that we have a different number of days each month?
If angels and devils are the same species, why would their mortal offspring appear physically different?
Is the percentage symbol a constant?
Dealing with an internal ScriptKiddie
Why might frozen potatoes require a hechsher?
If I tried and failed to start my own business, how do I apply for a job without job experience?
Can I travel from country A to country B to country C without going back to country A?
Algorithm: Given a large semiprime number N, find the next perfect square that is a perfect square more than N
How can I automatically launch GPSD on startup?
What can I do to encourage my players to use their consumables?
Is it possible to detect 100% of SQLi with a simple regex?
What does an unprocessed RAW file look like?
Boss asked me to sign a resignation paper without a date on it along with my new contract
Modern Algebraic Geometry and Analytic Number Theory
What is the nature of, and syntactic distinction between, modifier and complement?
Solving the linear first order differential equation?
Algorithm: Given a large semiprime number N, find the next perfect square that is a perfect square more than N
The math behind converting from any base to any base without going through base 10?Constructing orthogonal latin square Parker/Knuth methodWhy is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?Finding the longest repeating subsequenceWhat is more efficient: gcd(x,y) or brute force, when x and y are a very big numbersHow to predict the next word in a sentence using N-gramsCheckers algorithm - find the best last move in the game given the positions of all piecesAlgorithm to find non-overlapping intervals that minimize standard deviationalgorithm to find all values that occur more than n/10 timesPolynomial time algorithms for rank 1 elliptic curves over Q
$begingroup$
I'm looking for an efficient algorithm that can find the next perfect square over a large (100+ digit) semiprime N that is a perfect square more than N. For example given N = 299, I need an efficient way to find s = 324 as 324 = 18^2 and 324 - 299 = 5^2. I have only been able to use guess and check thus far which is computationally intensive for larger values of N. Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.
algorithms
asked 2 hours ago
Nick JewettNick Jewett
112
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$
I'm looking for an efficient algorithm that can find the next perfect square over a large (100+ digit) semiprime N that is a perfect square more than N. For example given N = 299, I need an efficient way to find s = 324 as 324 = 18^2 and 324 - 299 = 5^2. I have only been able to use guess and check thus far which is computationally intensive for larger values of N. Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.
algorithms
asked 2 hours ago
Nick JewettNick Jewett
112
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$
I'm looking for an efficient algorithm that can find the next perfect square over a large (100+ digit) semiprime N that is a perfect square more than N. For example given N = 299, I need an efficient way to find s = 324 as 324 = 18^2 and 324 - 299 = 5^2. I have only been able to use guess and check thus far which is computationally intensive for larger values of N. Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.
algorithms
asked 2 hours ago
Nick JewettNick Jewett
112
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$
I'm looking for an efficient algorithm that can find the next perfect square over a large (100+ digit) semiprime N that is a perfect square more than N. For example given N = 299, I need an efficient way to find s = 324 as 324 = 18^2 and 324 - 299 = 5^2. I have only been able to use guess and check thus far which is computationally intensive for larger values of N. Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.
algorithms
algorithms
asked 2 hours ago
Nick JewettNick Jewett
112
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 2 hours ago
Nick JewettNick Jewett
112
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 2 hours ago
Nick JewettNick Jewett
112
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 2 hours ago
Nick JewettNick Jewett
112
asked 2 hours ago
Nick JewettNick Jewett
112
112
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.
add a comment |
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.
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 1 hour ago
GassaGassa
685310
$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
1 hour ago
$begingroup$
@NickJewett Just how large is your case? The pairs of divisors of $N$ can be found trivially in $O (sqrt{N})$, is that not enough?
$endgroup$
– Gassa
1 hour ago
$begingroup$
@NickJewett Conversely, if there's a fast solution to your problem, I believe it helps solving the factoring problem, which is hard.
$endgroup$
– Gassa
1 hour 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
1 hour ago
$begingroup$
@NickJewett Ow. Alright then, this answer surely doesn't help improve things on that scale. You might want to add the scale and the motivation to the question though. And with the simple formulas above, it looks like the relation between general factoring problem and your version is tight and straightforward.
$endgroup$
– Gassa
1 hour ago
|
show 1 more 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-next-perfect-square-that-i%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.
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 1 hour ago
GassaGassa
685310
$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
1 hour ago
$begingroup$
@NickJewett Just how large is your case? The pairs of divisors of $N$ can be found trivially in $O (sqrt{N})$, is that not enough?
$endgroup$
– Gassa
1 hour ago
$begingroup$
@NickJewett Conversely, if there's a fast solution to your problem, I believe it helps solving the factoring problem, which is hard.
$endgroup$
– Gassa
1 hour 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
1 hour ago
$begingroup$
@NickJewett Ow. Alright then, this answer surely doesn't help improve things on that scale. You might want to add the scale and the motivation to the question though. And with the simple formulas above, it looks like the relation between general factoring problem and your version is tight and straightforward.
$endgroup$
– Gassa
1 hour ago
|
show 1 more 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.
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 1 hour ago
GassaGassa
685310
$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
1 hour ago
$begingroup$
@NickJewett Just how large is your case? The pairs of divisors of $N$ can be found trivially in $O (sqrt{N})$, is that not enough?
$endgroup$
– Gassa
1 hour ago
$begingroup$
@NickJewett Conversely, if there's a fast solution to your problem, I believe it helps solving the factoring problem, which is hard.
$endgroup$
– Gassa
1 hour 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
1 hour ago
$begingroup$
@NickJewett Ow. Alright then, this answer surely doesn't help improve things on that scale. You might want to add the scale and the motivation to the question though. And with the simple formulas above, it looks like the relation between general factoring problem and your version is tight and straightforward.
$endgroup$
– Gassa
1 hour ago
|
show 1 more 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.
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 1 hour ago
GassaGassa
685310
$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.
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 1 hour ago
GassaGassa
685310
edited 52 mins ago
answered 1 hour ago
GassaGassa
685310
answered 1 hour ago
GassaGassa
685310
answered 1 hour ago
GassaGassa
685310
685310
$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
1 hour ago
$begingroup$
@NickJewett Just how large is your case? The pairs of divisors of $N$ can be found trivially in $O (sqrt{N})$, is that not enough?
$endgroup$
– Gassa
1 hour ago
$begingroup$
@NickJewett Conversely, if there's a fast solution to your problem, I believe it helps solving the factoring problem, which is hard.
$endgroup$
– Gassa
1 hour 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
1 hour ago
$begingroup$
@NickJewett Ow. Alright then, this answer surely doesn't help improve things on that scale. You might want to add the scale and the motivation to the question though. And with the simple formulas above, it looks like the relation between general factoring problem and your version is tight and straightforward.
$endgroup$
– Gassa
1 hour ago
|
show 1 more 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
1 hour ago
$begingroup$
@NickJewett Just how large is your case? The pairs of divisors of $N$ can be found trivially in $O (sqrt{N})$, is that not enough?
$endgroup$
– Gassa
1 hour ago
$begingroup$
@NickJewett Conversely, if there's a fast solution to your problem, I believe it helps solving the factoring problem, which is hard.
$endgroup$
– Gassa
1 hour 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
1 hour ago
$begingroup$
@NickJewett Ow. Alright then, this answer surely doesn't help improve things on that scale. You might want to add the scale and the motivation to the question though. And with the simple formulas above, it looks like the relation between general factoring problem and your version is tight and straightforward.
$endgroup$
– Gassa
1 hour 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
1 hour 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
1 hour ago
$begingroup$
@NickJewett Just how large is your case? The pairs of divisors of $N$ can be found trivially in $O (sqrt{N})$, is that not enough?
$endgroup$
– Gassa
1 hour ago
$begingroup$
@NickJewett Just how large is your case? The pairs of divisors of $N$ can be found trivially in $O (sqrt{N})$, is that not enough?
$endgroup$
– Gassa
1 hour ago
$begingroup$
@NickJewett Conversely, if there's a fast solution to your problem, I believe it helps solving the factoring problem, which is hard.
$endgroup$
– Gassa
1 hour ago
$begingroup$
@NickJewett Conversely, if there's a fast solution to your problem, I believe it helps solving the factoring problem, which is hard.
$endgroup$
– Gassa
1 hour 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
1 hour 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
1 hour ago
$begingroup$
@NickJewett Ow. Alright then, this answer surely doesn't help improve things on that scale. You might want to add the scale and the motivation to the question though. And with the simple formulas above, it looks like the relation between general factoring problem and your version is tight and straightforward.
$endgroup$
– Gassa
1 hour ago
$begingroup$
@NickJewett Ow. Alright then, this answer surely doesn't help improve things on that scale. You might want to add the scale and the motivation to the question though. And with the simple formulas above, it looks like the relation between general factoring problem and your version is tight and straightforward.
$endgroup$
– Gassa
1 hour ago
|
show 1 more 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-next-perfect-square-that-i%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
