Solving $y^2 = 4x^3 - p$, with prime $p equiv 7 (text{mod } 8)$
$begingroup$
I'm trying to find integer solutions to equations of the form
$$y^2 = 4x^3 - p tag{1}$$
where $p$ is a prime and $p equiv 7 (text{mod } 8)$.
1) Is there a simple way to check if solutions do not exist for a given $p$?
2) Is there a computationally efficient way to find at least one solution? or maybe for a subset of $p$ by assuming some additional property?
Eventually I'd like to solve for some large $p$ ( > 1000 bits). I do not know if this can be done efficiently, but I'm starting with smaller $p$ to try to understand properties of the equation better.
For reasonable sized values, I can use magma to test out some values of $p$. I do this by noting that if there is an integer solution to $Y^2 = X^3 - 16p$ with $X$ a multiple of 4, then I have solved the original equation. This has helped me see that sometimes there are no solutions, but I haven't figured out if there is a simple way to determine when this occurs.
number-theory diophantine-equations elliptic-curves mordell-curves
asked Dec 24 '18 at 10:46
JustinBalentiJustinBalenti
263
$endgroup$
add a comment |
$begingroup$
I'm trying to find integer solutions to equations of the form
$$y^2 = 4x^3 - p tag{1}$$
where $p$ is a prime and $p equiv 7 (text{mod } 8)$.
1) Is there a simple way to check if solutions do not exist for a given $p$?
2) Is there a computationally efficient way to find at least one solution? or maybe for a subset of $p$ by assuming some additional property?
Eventually I'd like to solve for some large $p$ ( > 1000 bits). I do not know if this can be done efficiently, but I'm starting with smaller $p$ to try to understand properties of the equation better.
For reasonable sized values, I can use magma to test out some values of $p$. I do this by noting that if there is an integer solution to $Y^2 = X^3 - 16p$ with $X$ a multiple of 4, then I have solved the original equation. This has helped me see that sometimes there are no solutions, but I haven't figured out if there is a simple way to determine when this occurs.
number-theory diophantine-equations elliptic-curves mordell-curves
asked Dec 24 '18 at 10:46
JustinBalentiJustinBalenti
263
$endgroup$
1
$begingroup$
@Jyrki sage can be downloaded for free, and does mordell curves. I don't know whether it places bounds, or how much it slows down if no bound are imposed and large entries are given. The other one I know is Magma, it has an online calculator, but there is a time limit, computation stops after some two (human) minutes.
$endgroup$
– Will Jagy
Dec 24 '18 at 18:48
$begingroup$
All, sorry about the bungled link (ctrl+Cis not reliable on this sorry excuse of a laptop). A new attempt. OEIS, Wikipedia on Mordell curves.
$endgroup$
– Jyrki Lahtonen
Dec 24 '18 at 19:21
add a comment |
$begingroup$
I'm trying to find integer solutions to equations of the form
$$y^2 = 4x^3 - p tag{1}$$
where $p$ is a prime and $p equiv 7 (text{mod } 8)$.
1) Is there a simple way to check if solutions do not exist for a given $p$?
2) Is there a computationally efficient way to find at least one solution? or maybe for a subset of $p$ by assuming some additional property?
Eventually I'd like to solve for some large $p$ ( > 1000 bits). I do not know if this can be done efficiently, but I'm starting with smaller $p$ to try to understand properties of the equation better.
For reasonable sized values, I can use magma to test out some values of $p$. I do this by noting that if there is an integer solution to $Y^2 = X^3 - 16p$ with $X$ a multiple of 4, then I have solved the original equation. This has helped me see that sometimes there are no solutions, but I haven't figured out if there is a simple way to determine when this occurs.
number-theory diophantine-equations elliptic-curves mordell-curves
asked Dec 24 '18 at 10:46
JustinBalentiJustinBalenti
263
$endgroup$
I'm trying to find integer solutions to equations of the form
$$y^2 = 4x^3 - p tag{1}$$
where $p$ is a prime and $p equiv 7 (text{mod } 8)$.
1) Is there a simple way to check if solutions do not exist for a given $p$?
2) Is there a computationally efficient way to find at least one solution? or maybe for a subset of $p$ by assuming some additional property?
Eventually I'd like to solve for some large $p$ ( > 1000 bits). I do not know if this can be done efficiently, but I'm starting with smaller $p$ to try to understand properties of the equation better.
For reasonable sized values, I can use magma to test out some values of $p$. I do this by noting that if there is an integer solution to $Y^2 = X^3 - 16p$ with $X$ a multiple of 4, then I have solved the original equation. This has helped me see that sometimes there are no solutions, but I haven't figured out if there is a simple way to determine when this occurs.
number-theory diophantine-equations elliptic-curves mordell-curves
number-theory diophantine-equations elliptic-curves mordell-curves
asked Dec 24 '18 at 10:46
JustinBalentiJustinBalenti
263
asked Dec 24 '18 at 10:46
JustinBalentiJustinBalenti
263
asked Dec 24 '18 at 10:46
JustinBalentiJustinBalenti
263
asked Dec 24 '18 at 10:46
JustinBalentiJustinBalenti
263
asked Dec 24 '18 at 10:46
JustinBalentiJustinBalenti
263
263
1
$begingroup$
@Jyrki sage can be downloaded for free, and does mordell curves. I don't know whether it places bounds, or how much it slows down if no bound are imposed and large entries are given. The other one I know is Magma, it has an online calculator, but there is a time limit, computation stops after some two (human) minutes.
$endgroup$
– Will Jagy
Dec 24 '18 at 18:48
$begingroup$
All, sorry about the bungled link (ctrl+Cis not reliable on this sorry excuse of a laptop). A new attempt. OEIS, Wikipedia on Mordell curves.
$endgroup$
– Jyrki Lahtonen
Dec 24 '18 at 19:21
add a comment |
1
$begingroup$
@Jyrki sage can be downloaded for free, and does mordell curves. I don't know whether it places bounds, or how much it slows down if no bound are imposed and large entries are given. The other one I know is Magma, it has an online calculator, but there is a time limit, computation stops after some two (human) minutes.
$endgroup$
– Will Jagy
Dec 24 '18 at 18:48
$begingroup$
All, sorry about the bungled link (ctrl+Cis not reliable on this sorry excuse of a laptop). A new attempt. OEIS, Wikipedia on Mordell curves.
$endgroup$
– Jyrki Lahtonen
Dec 24 '18 at 19:21
1
1
$begingroup$
@Jyrki sage can be downloaded for free, and does mordell curves. I don't know whether it places bounds, or how much it slows down if no bound are imposed and large entries are given. The other one I know is Magma, it has an online calculator, but there is a time limit, computation stops after some two (human) minutes.
$endgroup$
– Will Jagy
Dec 24 '18 at 18:48
$begingroup$
@Jyrki sage can be downloaded for free, and does mordell curves. I don't know whether it places bounds, or how much it slows down if no bound are imposed and large entries are given. The other one I know is Magma, it has an online calculator, but there is a time limit, computation stops after some two (human) minutes.
$endgroup$
– Will Jagy
Dec 24 '18 at 18:48
$begingroup$
All, sorry about the bungled link (
ctrl+C is not reliable on this sorry excuse of a laptop). A new attempt. OEIS, Wikipedia on Mordell curves.$endgroup$
– Jyrki Lahtonen
Dec 24 '18 at 19:21
$begingroup$
All, sorry about the bungled link (
ctrl+C is not reliable on this sorry excuse of a laptop). A new attempt. OEIS, Wikipedia on Mordell curves.$endgroup$
– Jyrki Lahtonen
Dec 24 '18 at 19:21
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
47 fails. I don't know how much sage would slow down with larger $p$
jagy@phobeusjunior:~$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.9, Release Date: 2015-10-10 │
│ Type "notebook()" for the browser-based notebook interface. │
│ Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
sage: E = EllipticCurve([0,0,0, 0, -112])
sage: E.integral_points()
[(8 : 20 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -368])
sage: E.integral_points()
[(8 : 12 : 1),
(9 : 19 : 1),
(24 : 116 : 1),
(32 : 180 : 1),
(48 : 332 : 1),
(944 : 29004 : 1),
(1313 : 47577 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -496])
sage: E.integral_points()
[(8 : 4 : 1),
(16 : 60 : 1),
(25 : 123 : 1),
(40 : 252 : 1),
(113 : 1201 : 1),
(560 : 13252 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -752])
sage: E.integral_points()
sage: E = EllipticCurve([0,0,0, 0, -1136])
sage: E.integral_points()
[(96 : 940 : 1)]
sage:
answered Dec 24 '18 at 18:42
Will JagyWill Jagy
103k5101200
$endgroup$
add a comment |
$begingroup$
Partial result:
If $x$ is odd then we have modulo 8:
$$ -1equiv 4-y^2implies y ^2 equiv 5$$ which is impossible.
So, if there is a solution then $x$ must be even.
answered Dec 24 '18 at 11:07
greedoidgreedoid
41.5k1150102
$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%2f3051148%2fsolving-y2-4x3-p-with-prime-p-equiv-7-textmod-8%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
47 fails. I don't know how much sage would slow down with larger $p$
jagy@phobeusjunior:~$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.9, Release Date: 2015-10-10 │
│ Type "notebook()" for the browser-based notebook interface. │
│ Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
sage: E = EllipticCurve([0,0,0, 0, -112])
sage: E.integral_points()
[(8 : 20 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -368])
sage: E.integral_points()
[(8 : 12 : 1),
(9 : 19 : 1),
(24 : 116 : 1),
(32 : 180 : 1),
(48 : 332 : 1),
(944 : 29004 : 1),
(1313 : 47577 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -496])
sage: E.integral_points()
[(8 : 4 : 1),
(16 : 60 : 1),
(25 : 123 : 1),
(40 : 252 : 1),
(113 : 1201 : 1),
(560 : 13252 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -752])
sage: E.integral_points()
sage: E = EllipticCurve([0,0,0, 0, -1136])
sage: E.integral_points()
[(96 : 940 : 1)]
sage:
answered Dec 24 '18 at 18:42
Will JagyWill Jagy
103k5101200
$endgroup$
add a comment |
$begingroup$
47 fails. I don't know how much sage would slow down with larger $p$
jagy@phobeusjunior:~$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.9, Release Date: 2015-10-10 │
│ Type "notebook()" for the browser-based notebook interface. │
│ Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
sage: E = EllipticCurve([0,0,0, 0, -112])
sage: E.integral_points()
[(8 : 20 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -368])
sage: E.integral_points()
[(8 : 12 : 1),
(9 : 19 : 1),
(24 : 116 : 1),
(32 : 180 : 1),
(48 : 332 : 1),
(944 : 29004 : 1),
(1313 : 47577 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -496])
sage: E.integral_points()
[(8 : 4 : 1),
(16 : 60 : 1),
(25 : 123 : 1),
(40 : 252 : 1),
(113 : 1201 : 1),
(560 : 13252 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -752])
sage: E.integral_points()
sage: E = EllipticCurve([0,0,0, 0, -1136])
sage: E.integral_points()
[(96 : 940 : 1)]
sage:
answered Dec 24 '18 at 18:42
Will JagyWill Jagy
103k5101200
$endgroup$
add a comment |
$begingroup$
47 fails. I don't know how much sage would slow down with larger $p$
jagy@phobeusjunior:~$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.9, Release Date: 2015-10-10 │
│ Type "notebook()" for the browser-based notebook interface. │
│ Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
sage: E = EllipticCurve([0,0,0, 0, -112])
sage: E.integral_points()
[(8 : 20 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -368])
sage: E.integral_points()
[(8 : 12 : 1),
(9 : 19 : 1),
(24 : 116 : 1),
(32 : 180 : 1),
(48 : 332 : 1),
(944 : 29004 : 1),
(1313 : 47577 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -496])
sage: E.integral_points()
[(8 : 4 : 1),
(16 : 60 : 1),
(25 : 123 : 1),
(40 : 252 : 1),
(113 : 1201 : 1),
(560 : 13252 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -752])
sage: E.integral_points()
sage: E = EllipticCurve([0,0,0, 0, -1136])
sage: E.integral_points()
[(96 : 940 : 1)]
sage:
answered Dec 24 '18 at 18:42
Will JagyWill Jagy
103k5101200
$endgroup$
47 fails. I don't know how much sage would slow down with larger $p$
jagy@phobeusjunior:~$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath Version 6.9, Release Date: 2015-10-10 │
│ Type "notebook()" for the browser-based notebook interface. │
│ Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
sage: E = EllipticCurve([0,0,0, 0, -112])
sage: E.integral_points()
[(8 : 20 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -368])
sage: E.integral_points()
[(8 : 12 : 1),
(9 : 19 : 1),
(24 : 116 : 1),
(32 : 180 : 1),
(48 : 332 : 1),
(944 : 29004 : 1),
(1313 : 47577 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -496])
sage: E.integral_points()
[(8 : 4 : 1),
(16 : 60 : 1),
(25 : 123 : 1),
(40 : 252 : 1),
(113 : 1201 : 1),
(560 : 13252 : 1)]
sage: E = EllipticCurve([0,0,0, 0, -752])
sage: E.integral_points()
sage: E = EllipticCurve([0,0,0, 0, -1136])
sage: E.integral_points()
[(96 : 940 : 1)]
sage:
answered Dec 24 '18 at 18:42
Will JagyWill Jagy
103k5101200
answered Dec 24 '18 at 18:42
Will JagyWill Jagy
103k5101200
answered Dec 24 '18 at 18:42
Will JagyWill Jagy
103k5101200
answered Dec 24 '18 at 18:42
Will JagyWill Jagy
103k5101200
103k5101200
add a comment |
add a comment |
$begingroup$
Partial result:
If $x$ is odd then we have modulo 8:
$$ -1equiv 4-y^2implies y ^2 equiv 5$$ which is impossible.
So, if there is a solution then $x$ must be even.
answered Dec 24 '18 at 11:07
greedoidgreedoid
41.5k1150102
$endgroup$
add a comment |
$begingroup$
Partial result:
If $x$ is odd then we have modulo 8:
$$ -1equiv 4-y^2implies y ^2 equiv 5$$ which is impossible.
So, if there is a solution then $x$ must be even.
answered Dec 24 '18 at 11:07
greedoidgreedoid
41.5k1150102
$endgroup$
add a comment |
$begingroup$
Partial result:
If $x$ is odd then we have modulo 8:
$$ -1equiv 4-y^2implies y ^2 equiv 5$$ which is impossible.
So, if there is a solution then $x$ must be even.
answered Dec 24 '18 at 11:07
greedoidgreedoid
41.5k1150102
$endgroup$
Partial result:
If $x$ is odd then we have modulo 8:
$$ -1equiv 4-y^2implies y ^2 equiv 5$$ which is impossible.
So, if there is a solution then $x$ must be even.
answered Dec 24 '18 at 11:07
greedoidgreedoid
41.5k1150102
answered Dec 24 '18 at 11:07
greedoidgreedoid
41.5k1150102
answered Dec 24 '18 at 11:07
greedoidgreedoid
41.5k1150102
answered Dec 24 '18 at 11:07
greedoidgreedoid
41.5k1150102
41.5k1150102
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%2f3051148%2fsolving-y2-4x3-p-with-prime-p-equiv-7-textmod-8%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$
@Jyrki sage can be downloaded for free, and does mordell curves. I don't know whether it places bounds, or how much it slows down if no bound are imposed and large entries are given. The other one I know is Magma, it has an online calculator, but there is a time limit, computation stops after some two (human) minutes.
$endgroup$
– Will Jagy
Dec 24 '18 at 18:48
$begingroup$
All, sorry about the bungled link (
ctrl+Cis not reliable on this sorry excuse of a laptop). A new attempt. OEIS, Wikipedia on Mordell curves.$endgroup$
– Jyrki Lahtonen
Dec 24 '18 at 19:21