Generating random (torsion) point on elliptic curve efficiently
$begingroup$
I am looking for an efficient way to generate a random point on an elliptic curve over a finite field, $E(mathbb{K})$.
I know that you can pick a random $x$, compute e.g. in Weierstrass coordinates $f=x^3+ax+b$, check if it is a quadratic residue and then solve $y^2=f$ using the Tonelli-Shanks or Cipolla algorithm. The former roughly has a complexity of $O(log^2_2|mathbb{K}|)$ multiplications on $mathbb{K}$, while the latter only conditionally runs faster. If your finite field is huge and your computational power weak, this can be a lot. Is there a way to do this faster?
Furthermore, what if I want the point to belong to a particular torsion group, e.g. let's say I want to generate a point $P$ with $[m]P=O$? Is there a shortcut for such points, or do I have to generate them, and then test?
EDIT:
In more detail, I am working with supersingular elliptic curves over finite field of characteristic $p=2^u3^vpm1$, such that $p$ prime. It roughly holds that $2^uapprox3^v$ such that there are two very large coprime torsion groups $E[2^u]$ and $E[3^v]$. The points I want to generate are in either of these torsion groups.
Thank you for any help!
finite-fields computational-complexity elliptic-curves cryptography torsion-groups
asked Jan 16 at 16:34
GemeisGemeis
133
$endgroup$
|
show 6 more comments
$begingroup$
I am looking for an efficient way to generate a random point on an elliptic curve over a finite field, $E(mathbb{K})$.
I know that you can pick a random $x$, compute e.g. in Weierstrass coordinates $f=x^3+ax+b$, check if it is a quadratic residue and then solve $y^2=f$ using the Tonelli-Shanks or Cipolla algorithm. The former roughly has a complexity of $O(log^2_2|mathbb{K}|)$ multiplications on $mathbb{K}$, while the latter only conditionally runs faster. If your finite field is huge and your computational power weak, this can be a lot. Is there a way to do this faster?
Furthermore, what if I want the point to belong to a particular torsion group, e.g. let's say I want to generate a point $P$ with $[m]P=O$? Is there a shortcut for such points, or do I have to generate them, and then test?
EDIT:
In more detail, I am working with supersingular elliptic curves over finite field of characteristic $p=2^u3^vpm1$, such that $p$ prime. It roughly holds that $2^uapprox3^v$ such that there are two very large coprime torsion groups $E[2^u]$ and $E[3^v]$. The points I want to generate are in either of these torsion groups.
Thank you for any help!
finite-fields computational-complexity elliptic-curves cryptography torsion-groups
asked Jan 16 at 16:34
GemeisGemeis
133
$endgroup$
$begingroup$
To generate a point with $[m]P=O$, it might be handy to know the order of the group.
$endgroup$
– Lord Shark the Unknown
Jan 16 at 16:37
$begingroup$
You can select random and encode it byKoblitz's encoding method. In Cryptography that is a problem of mapping messages to points.
$endgroup$
– kelalaka
Jan 16 at 16:39
$begingroup$
@LordSharktheUnknown Well, I am working on supersingular elliptic curves. In that case, the full torsion group $E[m]$ has order $m^2$, while the group generated by $P$ would be of order $m$. Or are you asking about the actual, numerical value of $m$?
$endgroup$
– Gemeis
Jan 16 at 16:41
$begingroup$
Finding the order of $E$ plus two generators shouldn't be much harder than computing the order of a single random point ?
$endgroup$
– reuns
Jan 16 at 18:14
$begingroup$
Torsion points are solutions to division polynomials, so maybe you can solve that instead? For any random $x$ you have $1/2$ chance of a solution $y$. This means on average only two tries. I tested that Tonelli-Shanks using Sage will complete this within tens of microseconds even if $|mathbb K|$ is around $2^{2000}$, is that fast enough?
$endgroup$
– Yong Hao Ng
Jan 17 at 3:08
|
show 6 more comments
$begingroup$
I am looking for an efficient way to generate a random point on an elliptic curve over a finite field, $E(mathbb{K})$.
I know that you can pick a random $x$, compute e.g. in Weierstrass coordinates $f=x^3+ax+b$, check if it is a quadratic residue and then solve $y^2=f$ using the Tonelli-Shanks or Cipolla algorithm. The former roughly has a complexity of $O(log^2_2|mathbb{K}|)$ multiplications on $mathbb{K}$, while the latter only conditionally runs faster. If your finite field is huge and your computational power weak, this can be a lot. Is there a way to do this faster?
Furthermore, what if I want the point to belong to a particular torsion group, e.g. let's say I want to generate a point $P$ with $[m]P=O$? Is there a shortcut for such points, or do I have to generate them, and then test?
EDIT:
In more detail, I am working with supersingular elliptic curves over finite field of characteristic $p=2^u3^vpm1$, such that $p$ prime. It roughly holds that $2^uapprox3^v$ such that there are two very large coprime torsion groups $E[2^u]$ and $E[3^v]$. The points I want to generate are in either of these torsion groups.
Thank you for any help!
finite-fields computational-complexity elliptic-curves cryptography torsion-groups
asked Jan 16 at 16:34
GemeisGemeis
133
$endgroup$
I am looking for an efficient way to generate a random point on an elliptic curve over a finite field, $E(mathbb{K})$.
I know that you can pick a random $x$, compute e.g. in Weierstrass coordinates $f=x^3+ax+b$, check if it is a quadratic residue and then solve $y^2=f$ using the Tonelli-Shanks or Cipolla algorithm. The former roughly has a complexity of $O(log^2_2|mathbb{K}|)$ multiplications on $mathbb{K}$, while the latter only conditionally runs faster. If your finite field is huge and your computational power weak, this can be a lot. Is there a way to do this faster?
Furthermore, what if I want the point to belong to a particular torsion group, e.g. let's say I want to generate a point $P$ with $[m]P=O$? Is there a shortcut for such points, or do I have to generate them, and then test?
EDIT:
In more detail, I am working with supersingular elliptic curves over finite field of characteristic $p=2^u3^vpm1$, such that $p$ prime. It roughly holds that $2^uapprox3^v$ such that there are two very large coprime torsion groups $E[2^u]$ and $E[3^v]$. The points I want to generate are in either of these torsion groups.
Thank you for any help!
finite-fields computational-complexity elliptic-curves cryptography torsion-groups
finite-fields computational-complexity elliptic-curves cryptography torsion-groups
asked Jan 16 at 16:34
GemeisGemeis
133
asked Jan 16 at 16:34
GemeisGemeis
133
edited Jan 21 at 10:38
Gemeis
asked Jan 16 at 16:34
GemeisGemeis
133
asked Jan 16 at 16:34
GemeisGemeis
133
asked Jan 16 at 16:34
GemeisGemeis
133
133
$begingroup$
To generate a point with $[m]P=O$, it might be handy to know the order of the group.
$endgroup$
– Lord Shark the Unknown
Jan 16 at 16:37
$begingroup$
You can select random and encode it byKoblitz's encoding method. In Cryptography that is a problem of mapping messages to points.
$endgroup$
– kelalaka
Jan 16 at 16:39
$begingroup$
@LordSharktheUnknown Well, I am working on supersingular elliptic curves. In that case, the full torsion group $E[m]$ has order $m^2$, while the group generated by $P$ would be of order $m$. Or are you asking about the actual, numerical value of $m$?
$endgroup$
– Gemeis
Jan 16 at 16:41
$begingroup$
Finding the order of $E$ plus two generators shouldn't be much harder than computing the order of a single random point ?
$endgroup$
– reuns
Jan 16 at 18:14
$begingroup$
Torsion points are solutions to division polynomials, so maybe you can solve that instead? For any random $x$ you have $1/2$ chance of a solution $y$. This means on average only two tries. I tested that Tonelli-Shanks using Sage will complete this within tens of microseconds even if $|mathbb K|$ is around $2^{2000}$, is that fast enough?
$endgroup$
– Yong Hao Ng
Jan 17 at 3:08
|
show 6 more comments
$begingroup$
To generate a point with $[m]P=O$, it might be handy to know the order of the group.
$endgroup$
– Lord Shark the Unknown
Jan 16 at 16:37
$begingroup$
You can select random and encode it byKoblitz's encoding method. In Cryptography that is a problem of mapping messages to points.
$endgroup$
– kelalaka
Jan 16 at 16:39
$begingroup$
@LordSharktheUnknown Well, I am working on supersingular elliptic curves. In that case, the full torsion group $E[m]$ has order $m^2$, while the group generated by $P$ would be of order $m$. Or are you asking about the actual, numerical value of $m$?
$endgroup$
– Gemeis
Jan 16 at 16:41
$begingroup$
Finding the order of $E$ plus two generators shouldn't be much harder than computing the order of a single random point ?
$endgroup$
– reuns
Jan 16 at 18:14
$begingroup$
Torsion points are solutions to division polynomials, so maybe you can solve that instead? For any random $x$ you have $1/2$ chance of a solution $y$. This means on average only two tries. I tested that Tonelli-Shanks using Sage will complete this within tens of microseconds even if $|mathbb K|$ is around $2^{2000}$, is that fast enough?
$endgroup$
– Yong Hao Ng
Jan 17 at 3:08
$begingroup$
To generate a point with $[m]P=O$, it might be handy to know the order of the group.
$endgroup$
– Lord Shark the Unknown
Jan 16 at 16:37
$begingroup$
To generate a point with $[m]P=O$, it might be handy to know the order of the group.
$endgroup$
– Lord Shark the Unknown
Jan 16 at 16:37
$begingroup$
You can select random and encode it by
Koblitz's encoding method. In Cryptography that is a problem of mapping messages to points.$endgroup$
– kelalaka
Jan 16 at 16:39
$begingroup$
You can select random and encode it by
Koblitz's encoding method. In Cryptography that is a problem of mapping messages to points.$endgroup$
– kelalaka
Jan 16 at 16:39
$begingroup$
@LordSharktheUnknown Well, I am working on supersingular elliptic curves. In that case, the full torsion group $E[m]$ has order $m^2$, while the group generated by $P$ would be of order $m$. Or are you asking about the actual, numerical value of $m$?
$endgroup$
– Gemeis
Jan 16 at 16:41
$begingroup$
@LordSharktheUnknown Well, I am working on supersingular elliptic curves. In that case, the full torsion group $E[m]$ has order $m^2$, while the group generated by $P$ would be of order $m$. Or are you asking about the actual, numerical value of $m$?
$endgroup$
– Gemeis
Jan 16 at 16:41
$begingroup$
Finding the order of $E$ plus two generators shouldn't be much harder than computing the order of a single random point ?
$endgroup$
– reuns
Jan 16 at 18:14
$begingroup$
Finding the order of $E$ plus two generators shouldn't be much harder than computing the order of a single random point ?
$endgroup$
– reuns
Jan 16 at 18:14
$begingroup$
Torsion points are solutions to division polynomials, so maybe you can solve that instead? For any random $x$ you have $1/2$ chance of a solution $y$. This means on average only two tries. I tested that Tonelli-Shanks using Sage will complete this within tens of microseconds even if $|mathbb K|$ is around $2^{2000}$, is that fast enough?
$endgroup$
– Yong Hao Ng
Jan 17 at 3:08
$begingroup$
Torsion points are solutions to division polynomials, so maybe you can solve that instead? For any random $x$ you have $1/2$ chance of a solution $y$. This means on average only two tries. I tested that Tonelli-Shanks using Sage will complete this within tens of microseconds even if $|mathbb K|$ is around $2^{2000}$, is that fast enough?
$endgroup$
– Yong Hao Ng
Jan 17 at 3:08
|
show 6 more comments
0
active
oldest
votes
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%2f3075947%2fgenerating-random-torsion-point-on-elliptic-curve-efficiently%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3075947%2fgenerating-random-torsion-point-on-elliptic-curve-efficiently%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$
To generate a point with $[m]P=O$, it might be handy to know the order of the group.
$endgroup$
– Lord Shark the Unknown
Jan 16 at 16:37
$begingroup$
You can select random and encode it by
Koblitz's encoding method. In Cryptography that is a problem of mapping messages to points.$endgroup$
– kelalaka
Jan 16 at 16:39
$begingroup$
@LordSharktheUnknown Well, I am working on supersingular elliptic curves. In that case, the full torsion group $E[m]$ has order $m^2$, while the group generated by $P$ would be of order $m$. Or are you asking about the actual, numerical value of $m$?
$endgroup$
– Gemeis
Jan 16 at 16:41
$begingroup$
Finding the order of $E$ plus two generators shouldn't be much harder than computing the order of a single random point ?
$endgroup$
– reuns
Jan 16 at 18:14
$begingroup$
Torsion points are solutions to division polynomials, so maybe you can solve that instead? For any random $x$ you have $1/2$ chance of a solution $y$. This means on average only two tries. I tested that Tonelli-Shanks using Sage will complete this within tens of microseconds even if $|mathbb K|$ is around $2^{2000}$, is that fast enough?
$endgroup$
– Yong Hao Ng
Jan 17 at 3:08