Mixing
Finding Prime numbers given Germain quadratic equation
$begingroup$
I have a large number $n$ (1250 decimal digits), which is a product of 2 prime numbers, which happen to be Germain prime numbers. I have to find the two prime numbers, have been given a quadratic equation $2x^2+x-n = 0$.
To apply the quadratic formula, you will need to find the square root of the discriminant D as an exact integer.
How do I find the discriminant without knowing the Phi value, which I cannot calculate since n is too large, cannot use Factorization either.
Any help would be much appreciated. Stuck on this problem for a while.
prime-numbers cryptography
edited Oct 17 '18 at 15:05
jameselmore
4,41932035
asked Oct 17 '18 at 14:54
mathrook1243mathrook1243
203
$endgroup$
|
show 1 more comment
$begingroup$
I have a large number $n$ (1250 decimal digits), which is a product of 2 prime numbers, which happen to be Germain prime numbers. I have to find the two prime numbers, have been given a quadratic equation $2x^2+x-n = 0$.
To apply the quadratic formula, you will need to find the square root of the discriminant D as an exact integer.
How do I find the discriminant without knowing the Phi value, which I cannot calculate since n is too large, cannot use Factorization either.
Any help would be much appreciated. Stuck on this problem for a while.
prime-numbers cryptography
edited Oct 17 '18 at 15:05
jameselmore
4,41932035
asked Oct 17 '18 at 14:54
mathrook1243mathrook1243
203
$endgroup$
$begingroup$
You have $n$ , so you can solve the quadratic equation
$endgroup$
– Peter
Oct 17 '18 at 17:02
$begingroup$
Search for online quadratic equation solvers for large $n$. If there are non, then search for code for programming one
$endgroup$
– unseen_rider
Oct 21 '18 at 11:26
$begingroup$
What is the relevance of the quadratic equation in $n$? Is it true that $n=pq$ where $p$ and $q$ are Germain primes and both are roots of that equation? That would be pretty trivial.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:56
1
$begingroup$
If you give us the $n$ I could give the determinant easily: it's just the square root of $8n + 1$, and exact integer roots are easy to find. A small C program suffices with some libgmp help.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:58
$begingroup$
@HennoBrandsma Oh my, I thought the n is not known.
$endgroup$
– kelalaka
Oct 23 '18 at 20:13
|
show 1 more comment
$begingroup$
I have a large number $n$ (1250 decimal digits), which is a product of 2 prime numbers, which happen to be Germain prime numbers. I have to find the two prime numbers, have been given a quadratic equation $2x^2+x-n = 0$.
To apply the quadratic formula, you will need to find the square root of the discriminant D as an exact integer.
How do I find the discriminant without knowing the Phi value, which I cannot calculate since n is too large, cannot use Factorization either.
Any help would be much appreciated. Stuck on this problem for a while.
prime-numbers cryptography
edited Oct 17 '18 at 15:05
jameselmore
4,41932035
asked Oct 17 '18 at 14:54
mathrook1243mathrook1243
203
$endgroup$
I have a large number $n$ (1250 decimal digits), which is a product of 2 prime numbers, which happen to be Germain prime numbers. I have to find the two prime numbers, have been given a quadratic equation $2x^2+x-n = 0$.
To apply the quadratic formula, you will need to find the square root of the discriminant D as an exact integer.
How do I find the discriminant without knowing the Phi value, which I cannot calculate since n is too large, cannot use Factorization either.
Any help would be much appreciated. Stuck on this problem for a while.
prime-numbers cryptography
prime-numbers cryptography
edited Oct 17 '18 at 15:05
jameselmore
4,41932035
asked Oct 17 '18 at 14:54
mathrook1243mathrook1243
203
edited Oct 17 '18 at 15:05
jameselmore
4,41932035
asked Oct 17 '18 at 14:54
mathrook1243mathrook1243
203
edited Oct 17 '18 at 15:05
jameselmore
4,41932035
edited Oct 17 '18 at 15:05
jameselmore
4,41932035
edited Oct 17 '18 at 15:05
jameselmore
4,41932035
4,41932035
asked Oct 17 '18 at 14:54
mathrook1243mathrook1243
203
asked Oct 17 '18 at 14:54
mathrook1243mathrook1243
203
asked Oct 17 '18 at 14:54
mathrook1243mathrook1243
203
203
$begingroup$
You have $n$ , so you can solve the quadratic equation
$endgroup$
– Peter
Oct 17 '18 at 17:02
$begingroup$
Search for online quadratic equation solvers for large $n$. If there are non, then search for code for programming one
$endgroup$
– unseen_rider
Oct 21 '18 at 11:26
$begingroup$
What is the relevance of the quadratic equation in $n$? Is it true that $n=pq$ where $p$ and $q$ are Germain primes and both are roots of that equation? That would be pretty trivial.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:56
1
$begingroup$
If you give us the $n$ I could give the determinant easily: it's just the square root of $8n + 1$, and exact integer roots are easy to find. A small C program suffices with some libgmp help.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:58
$begingroup$
@HennoBrandsma Oh my, I thought the n is not known.
$endgroup$
– kelalaka
Oct 23 '18 at 20:13
|
show 1 more comment
$begingroup$
You have $n$ , so you can solve the quadratic equation
$endgroup$
– Peter
Oct 17 '18 at 17:02
$begingroup$
Search for online quadratic equation solvers for large $n$. If there are non, then search for code for programming one
$endgroup$
– unseen_rider
Oct 21 '18 at 11:26
$begingroup$
What is the relevance of the quadratic equation in $n$? Is it true that $n=pq$ where $p$ and $q$ are Germain primes and both are roots of that equation? That would be pretty trivial.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:56
1
$begingroup$
If you give us the $n$ I could give the determinant easily: it's just the square root of $8n + 1$, and exact integer roots are easy to find. A small C program suffices with some libgmp help.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:58
$begingroup$
@HennoBrandsma Oh my, I thought the n is not known.
$endgroup$
– kelalaka
Oct 23 '18 at 20:13
$begingroup$
You have $n$ , so you can solve the quadratic equation
$endgroup$
– Peter
Oct 17 '18 at 17:02
$begingroup$
You have $n$ , so you can solve the quadratic equation
$endgroup$
– Peter
Oct 17 '18 at 17:02
$begingroup$
Search for online quadratic equation solvers for large $n$. If there are non, then search for code for programming one
$endgroup$
– unseen_rider
Oct 21 '18 at 11:26
$begingroup$
Search for online quadratic equation solvers for large $n$. If there are non, then search for code for programming one
$endgroup$
– unseen_rider
Oct 21 '18 at 11:26
$begingroup$
What is the relevance of the quadratic equation in $n$? Is it true that $n=pq$ where $p$ and $q$ are Germain primes and both are roots of that equation? That would be pretty trivial.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:56
$begingroup$
What is the relevance of the quadratic equation in $n$? Is it true that $n=pq$ where $p$ and $q$ are Germain primes and both are roots of that equation? That would be pretty trivial.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:56
1
1
$begingroup$
If you give us the $n$ I could give the determinant easily: it's just the square root of $8n + 1$, and exact integer roots are easy to find. A small C program suffices with some libgmp help.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:58
$begingroup$
If you give us the $n$ I could give the determinant easily: it's just the square root of $8n + 1$, and exact integer roots are easy to find. A small C program suffices with some libgmp help.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:58
$begingroup$
@HennoBrandsma Oh my, I thought the n is not known.
$endgroup$
– kelalaka
Oct 23 '18 at 20:13
$begingroup$
@HennoBrandsma Oh my, I thought the n is not known.
$endgroup$
– kelalaka
Oct 23 '18 at 20:13
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
As Henno says in the comments, square roots that happen to be exact integers are easy to find. The reason is this: not-so-bad approximations of square roots are easy to find and once you have a non-so-bad approximation, you can just test which of the most nearby integers is the squareroot by trial and error (i.e. squaring them).
There are various algorithms for approximating square roots. I like the following one (allegedly invented by the ancient Babylonians) because it is easy to understand why it works:
1) Guess a first approximation $a_1$. It need not be a good guess, even something that is obviously wrong like $a_1 = 54$ might do.
2) Compute a second approximation $b_1$ by $b_1 = D/a_1$, where $D$ is the number you want to take the square root of. (So in your case $D = 8n + 1$)
If $a_1$ was too small (that is $a_1 < sqrt{D}$), then $b_1$ is too big and if $a_1$ was too big then $b_1$ is to small. This suggest a way to find a second approximation $a_2$ that is a better approximation of $sqrt{D}$ than $a_1$ was:
3) Compute $a_2 = frac{a_1 + b_1}{2}$
4) Compute $b_2 = D/a_2$
Just as we like to believe that $a_2$ is closer to $sqrt{D}$ than $a_1$ was, we believe that $b_2$ is closer to $sqrt{D}$ than $b_1$ was. And again, if $a_2$ was an underestimation of $sqrt{D}$ then $b_2$ is an overestimation and vice versa, so we can get an even better approximation by computing:
5) $a_3 = frac{a_2 + b_2}{2}$
6) $b_3 = D/a_3$
7) $a_4 = frac{a_3 + b_3}{2}$
etc etc.
You will be surprised how quickly these approximations of $sqrt{D}$ get better, as can be seen for instance from the shrinking distance between $a_i$ and $b_i$.
Of course once you arrive at a point that there is only a single integer between $a_i$ and $b_i$ you know that this integer must be your answer (unless you made computing error somewhere).
answered Feb 1 at 8:52
VincentVincent
3,33811231
$endgroup$
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: "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%2f2959425%2ffinding-prime-numbers-given-germain-quadratic-equation%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$
As Henno says in the comments, square roots that happen to be exact integers are easy to find. The reason is this: not-so-bad approximations of square roots are easy to find and once you have a non-so-bad approximation, you can just test which of the most nearby integers is the squareroot by trial and error (i.e. squaring them).
There are various algorithms for approximating square roots. I like the following one (allegedly invented by the ancient Babylonians) because it is easy to understand why it works:
1) Guess a first approximation $a_1$. It need not be a good guess, even something that is obviously wrong like $a_1 = 54$ might do.
2) Compute a second approximation $b_1$ by $b_1 = D/a_1$, where $D$ is the number you want to take the square root of. (So in your case $D = 8n + 1$)
If $a_1$ was too small (that is $a_1 < sqrt{D}$), then $b_1$ is too big and if $a_1$ was too big then $b_1$ is to small. This suggest a way to find a second approximation $a_2$ that is a better approximation of $sqrt{D}$ than $a_1$ was:
3) Compute $a_2 = frac{a_1 + b_1}{2}$
4) Compute $b_2 = D/a_2$
Just as we like to believe that $a_2$ is closer to $sqrt{D}$ than $a_1$ was, we believe that $b_2$ is closer to $sqrt{D}$ than $b_1$ was. And again, if $a_2$ was an underestimation of $sqrt{D}$ then $b_2$ is an overestimation and vice versa, so we can get an even better approximation by computing:
5) $a_3 = frac{a_2 + b_2}{2}$
6) $b_3 = D/a_3$
7) $a_4 = frac{a_3 + b_3}{2}$
etc etc.
You will be surprised how quickly these approximations of $sqrt{D}$ get better, as can be seen for instance from the shrinking distance between $a_i$ and $b_i$.
Of course once you arrive at a point that there is only a single integer between $a_i$ and $b_i$ you know that this integer must be your answer (unless you made computing error somewhere).
answered Feb 1 at 8:52
VincentVincent
3,33811231
$endgroup$
add a comment |
$begingroup$
As Henno says in the comments, square roots that happen to be exact integers are easy to find. The reason is this: not-so-bad approximations of square roots are easy to find and once you have a non-so-bad approximation, you can just test which of the most nearby integers is the squareroot by trial and error (i.e. squaring them).
There are various algorithms for approximating square roots. I like the following one (allegedly invented by the ancient Babylonians) because it is easy to understand why it works:
1) Guess a first approximation $a_1$. It need not be a good guess, even something that is obviously wrong like $a_1 = 54$ might do.
2) Compute a second approximation $b_1$ by $b_1 = D/a_1$, where $D$ is the number you want to take the square root of. (So in your case $D = 8n + 1$)
If $a_1$ was too small (that is $a_1 < sqrt{D}$), then $b_1$ is too big and if $a_1$ was too big then $b_1$ is to small. This suggest a way to find a second approximation $a_2$ that is a better approximation of $sqrt{D}$ than $a_1$ was:
3) Compute $a_2 = frac{a_1 + b_1}{2}$
4) Compute $b_2 = D/a_2$
Just as we like to believe that $a_2$ is closer to $sqrt{D}$ than $a_1$ was, we believe that $b_2$ is closer to $sqrt{D}$ than $b_1$ was. And again, if $a_2$ was an underestimation of $sqrt{D}$ then $b_2$ is an overestimation and vice versa, so we can get an even better approximation by computing:
5) $a_3 = frac{a_2 + b_2}{2}$
6) $b_3 = D/a_3$
7) $a_4 = frac{a_3 + b_3}{2}$
etc etc.
You will be surprised how quickly these approximations of $sqrt{D}$ get better, as can be seen for instance from the shrinking distance between $a_i$ and $b_i$.
Of course once you arrive at a point that there is only a single integer between $a_i$ and $b_i$ you know that this integer must be your answer (unless you made computing error somewhere).
answered Feb 1 at 8:52
VincentVincent
3,33811231
$endgroup$
add a comment |
$begingroup$
As Henno says in the comments, square roots that happen to be exact integers are easy to find. The reason is this: not-so-bad approximations of square roots are easy to find and once you have a non-so-bad approximation, you can just test which of the most nearby integers is the squareroot by trial and error (i.e. squaring them).
There are various algorithms for approximating square roots. I like the following one (allegedly invented by the ancient Babylonians) because it is easy to understand why it works:
1) Guess a first approximation $a_1$. It need not be a good guess, even something that is obviously wrong like $a_1 = 54$ might do.
2) Compute a second approximation $b_1$ by $b_1 = D/a_1$, where $D$ is the number you want to take the square root of. (So in your case $D = 8n + 1$)
If $a_1$ was too small (that is $a_1 < sqrt{D}$), then $b_1$ is too big and if $a_1$ was too big then $b_1$ is to small. This suggest a way to find a second approximation $a_2$ that is a better approximation of $sqrt{D}$ than $a_1$ was:
3) Compute $a_2 = frac{a_1 + b_1}{2}$
4) Compute $b_2 = D/a_2$
Just as we like to believe that $a_2$ is closer to $sqrt{D}$ than $a_1$ was, we believe that $b_2$ is closer to $sqrt{D}$ than $b_1$ was. And again, if $a_2$ was an underestimation of $sqrt{D}$ then $b_2$ is an overestimation and vice versa, so we can get an even better approximation by computing:
5) $a_3 = frac{a_2 + b_2}{2}$
6) $b_3 = D/a_3$
7) $a_4 = frac{a_3 + b_3}{2}$
etc etc.
You will be surprised how quickly these approximations of $sqrt{D}$ get better, as can be seen for instance from the shrinking distance between $a_i$ and $b_i$.
Of course once you arrive at a point that there is only a single integer between $a_i$ and $b_i$ you know that this integer must be your answer (unless you made computing error somewhere).
answered Feb 1 at 8:52
VincentVincent
3,33811231
$endgroup$
As Henno says in the comments, square roots that happen to be exact integers are easy to find. The reason is this: not-so-bad approximations of square roots are easy to find and once you have a non-so-bad approximation, you can just test which of the most nearby integers is the squareroot by trial and error (i.e. squaring them).
There are various algorithms for approximating square roots. I like the following one (allegedly invented by the ancient Babylonians) because it is easy to understand why it works:
1) Guess a first approximation $a_1$. It need not be a good guess, even something that is obviously wrong like $a_1 = 54$ might do.
2) Compute a second approximation $b_1$ by $b_1 = D/a_1$, where $D$ is the number you want to take the square root of. (So in your case $D = 8n + 1$)
If $a_1$ was too small (that is $a_1 < sqrt{D}$), then $b_1$ is too big and if $a_1$ was too big then $b_1$ is to small. This suggest a way to find a second approximation $a_2$ that is a better approximation of $sqrt{D}$ than $a_1$ was:
3) Compute $a_2 = frac{a_1 + b_1}{2}$
4) Compute $b_2 = D/a_2$
Just as we like to believe that $a_2$ is closer to $sqrt{D}$ than $a_1$ was, we believe that $b_2$ is closer to $sqrt{D}$ than $b_1$ was. And again, if $a_2$ was an underestimation of $sqrt{D}$ then $b_2$ is an overestimation and vice versa, so we can get an even better approximation by computing:
5) $a_3 = frac{a_2 + b_2}{2}$
6) $b_3 = D/a_3$
7) $a_4 = frac{a_3 + b_3}{2}$
etc etc.
You will be surprised how quickly these approximations of $sqrt{D}$ get better, as can be seen for instance from the shrinking distance between $a_i$ and $b_i$.
Of course once you arrive at a point that there is only a single integer between $a_i$ and $b_i$ you know that this integer must be your answer (unless you made computing error somewhere).
answered Feb 1 at 8:52
VincentVincent
3,33811231
answered Feb 1 at 8:52
VincentVincent
3,33811231
answered Feb 1 at 8:52
VincentVincent
3,33811231
answered Feb 1 at 8:52
VincentVincent
3,33811231
3,33811231
add a comment |
add a comment |
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%2f2959425%2ffinding-prime-numbers-given-germain-quadratic-equation%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$
You have $n$ , so you can solve the quadratic equation
$endgroup$
– Peter
Oct 17 '18 at 17:02
$begingroup$
Search for online quadratic equation solvers for large $n$. If there are non, then search for code for programming one
$endgroup$
– unseen_rider
Oct 21 '18 at 11:26
$begingroup$
What is the relevance of the quadratic equation in $n$? Is it true that $n=pq$ where $p$ and $q$ are Germain primes and both are roots of that equation? That would be pretty trivial.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:56
1
$begingroup$
If you give us the $n$ I could give the determinant easily: it's just the square root of $8n + 1$, and exact integer roots are easy to find. A small C program suffices with some libgmp help.
$endgroup$
– Henno Brandsma
Oct 23 '18 at 11:58
$begingroup$
@HennoBrandsma Oh my, I thought the n is not known.
$endgroup$
– kelalaka
Oct 23 '18 at 20:13