Algorithm: Given a large semiprime number N, find the next perfect square that is a perfect square more than...
Why did Ylvis use "go" instead of "say" in phrases like "Dog goes 'woof'"?
How much light is too much?
Boss asked me to sign a resignation paper without a date on it along with my new contract
How can I deduce the power of a capacitor from its datasheet?
How can find the 2D Voronoi cell area distribution?
Why does this relation fail symmetry and transitivity properties?
Plausible reason for gold-digging ant
I have trouble understanding this fallacy: "If A, then B. Therefore if not-B, then not-A."
Is there a way to pause a running process on Linux systems and resume later?
How do I narratively explain how in-game circumstances do not mechanically allow a PC to instantly kill an NPC?
What is an efficient way to digitize a family photo collection?
How to put text above column in minipage?
Insecure private-key encryption
Does rolling friction increase speed of a wheel?
How many proficiencies and languages does a noble half-elf Knowledge Domain cleric start with?
How to not let the Identify spell spoil everything?
Critique vs nitpicking
Where does documentation like business and software requirement spec docs fit in an agile project?
Is it really OK to use "because of"?
Players preemptively rolling, even though their rolls are useless or are checking the wrong skills
What's the reason that we have a different number of days each month?
Planting on shale filled patch with weed underlay
Minimum Viable Product for RTS game?
Why do single electrical receptacles exist?
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 2 hours 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 2 hours 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 2 hours 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 2 hours 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 2 hours ago
GassaGassa
685310
edited 1 hour ago
answered 2 hours ago
GassaGassa
685310
answered 2 hours ago
GassaGassa
685310
answered 2 hours 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
