Calculate the number of points of an elliptic curve in medium Weierstrass form over finite field
$begingroup$
Let $E$ be the elliptic curve over $mathbb{F}_3$ in medium Weierstrass form $E:y^2=x^3+x^2+x+1$. How to compute the number of points $|E(mathbb{F}_{3^k})|$? I read that there are some formulas for computing number of points for short Weierstrass form by Frobenius endomorphism. But they don't work in this case.
number-theory elliptic-curves
$endgroup$
add a comment |
$begingroup$
Let $E$ be the elliptic curve over $mathbb{F}_3$ in medium Weierstrass form $E:y^2=x^3+x^2+x+1$. How to compute the number of points $|E(mathbb{F}_{3^k})|$? I read that there are some formulas for computing number of points for short Weierstrass form by Frobenius endomorphism. But they don't work in this case.
number-theory elliptic-curves
$endgroup$
add a comment |
$begingroup$
Let $E$ be the elliptic curve over $mathbb{F}_3$ in medium Weierstrass form $E:y^2=x^3+x^2+x+1$. How to compute the number of points $|E(mathbb{F}_{3^k})|$? I read that there are some formulas for computing number of points for short Weierstrass form by Frobenius endomorphism. But they don't work in this case.
number-theory elliptic-curves
$endgroup$
Let $E$ be the elliptic curve over $mathbb{F}_3$ in medium Weierstrass form $E:y^2=x^3+x^2+x+1$. How to compute the number of points $|E(mathbb{F}_{3^k})|$? I read that there are some formulas for computing number of points for short Weierstrass form by Frobenius endomorphism. But they don't work in this case.
number-theory elliptic-curves
number-theory elliptic-curves
asked 5 hours ago
NickyNicky
736
736
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let $phi^k(x,y)= (x^{3^k},y^{3^k})$ then $#E(mathbb{F}_{3^k}) =deg_s(phi^k-1)$. Is the endomorphism $phi^k-1$ separable ? Yes because inserapable endomorphisms are of the form $rho circ phi$. Then $$deg_s(phi^k-1) = deg(phi^k-1)=((phi^*)^k-1)(phi^k-1)\= (phi^*phi)^k+1-(phi^*)^k-phi^k = 3^k+1-alpha^k-(alpha^*)^k$$ where $phi^*$ is the dual isogeny such that $phi^* phi = deg(phi) = 3$ and $phi+phi^* = t = 3+1-#E(mathbb{F}_{3})$ and $alpha$ is the root of the minimal polynomial $X^2-t X + 3 = 0$ of the Frobenius
magma code
F := FiniteField(3); A<x,y> := AffineSpace(F,2);
C := Curve(A,y^2-x^3-x^2-x-1);
t :=3+1- #Points(ProjectiveClosure(C));
P<z> := PolynomialRing(Integers()); K<a> := NumberField(z^2-t*z+3); aa := Norm(a)/a;
for k in [2..10] do
Ck := BaseChange(C,FiniteField(3^k));
Ek := #Points(ProjectiveClosure(Ck));
[Ek,3^k+1-a^k-aa^k];
end for;
To obtain the minimal polynomial of endomorphisms :
Write that $E(overline{mathbb{F}_3}) $ is a subgroup of $mathbb{Q}/mathbb{Z}times mathbb{Q}/mathbb{Z}$ so any group homomorphism acts as a matrix
$A=pmatrix{a & b \c & d} in M_2(widehat{mathbb{Z}})$ (matrix of profinite integers). Then the dual homomorphism is $A^*=pmatrix{d & -b \-c & a}$ so that $A^* A = pmatrix{ad-bc& 0 \ 0 & ad-bc}$ and $A + A^* = pmatrix{a+d & 0 \0 & a+d}$, so they both act as direct multiplication by an element in $widehat{mathbb{Z}}$. If $A$ is an endomorphism (defined by polynomial equations) then so are $A^*,A + A^*,A^*A$ so the latter must act as multiplication by elements in $mathbb{Z}$.
$endgroup$
add a comment |
$begingroup$
This is, indeed, easy after you have calculated the number of points over the prime field. It is straightforward to list them
$$
E(Bbb{F}_3)={(0,1),(0,-1),(1,1),(1,-1),(-1,0),infty}.
$$
In other words $|E(Bbb{F}_3)|=6.$ This piece of information gives us the complex numbers
$alpha,overline{alpha}$
(see reuns's post for their interpretation as eigenvalues of Frobenius on the Tate module) as they are known to safisfy the equations $|alpha|^2=3$ and
$$
alpha+overline{alpha}=3+1-|E(Bbb{F}_3)|=-2.
$$
The real part of $alpha$ is thus equal to $-1$, so $alpha=-1pm isqrt2$.
The formula for the number of rational poinst on the extension field then reads
$$
|E(Bbb{F}_{3^k})|=3^k+1-alpha^k-overline{alpha}^k=3^k+1-2operatorname{Re}(-1+isqrt2)^k.
$$
For example, when $k=2$, $alpha^2=(-1+isqrt2)^2=-1-2isqrt2$
implying that $|E(Bbb{F}_9)|=9+1+2=12$. This passes the litmus test of being divisible by $|E(Bbb{F}_3)|$ (Lagrange's theorem from elementary group theory), possibly adding to our confidence in the correctness of the result.
$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%2f3129575%2fcalculate-the-number-of-points-of-an-elliptic-curve-in-medium-weierstrass-form-o%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$
Let $phi^k(x,y)= (x^{3^k},y^{3^k})$ then $#E(mathbb{F}_{3^k}) =deg_s(phi^k-1)$. Is the endomorphism $phi^k-1$ separable ? Yes because inserapable endomorphisms are of the form $rho circ phi$. Then $$deg_s(phi^k-1) = deg(phi^k-1)=((phi^*)^k-1)(phi^k-1)\= (phi^*phi)^k+1-(phi^*)^k-phi^k = 3^k+1-alpha^k-(alpha^*)^k$$ where $phi^*$ is the dual isogeny such that $phi^* phi = deg(phi) = 3$ and $phi+phi^* = t = 3+1-#E(mathbb{F}_{3})$ and $alpha$ is the root of the minimal polynomial $X^2-t X + 3 = 0$ of the Frobenius
magma code
F := FiniteField(3); A<x,y> := AffineSpace(F,2);
C := Curve(A,y^2-x^3-x^2-x-1);
t :=3+1- #Points(ProjectiveClosure(C));
P<z> := PolynomialRing(Integers()); K<a> := NumberField(z^2-t*z+3); aa := Norm(a)/a;
for k in [2..10] do
Ck := BaseChange(C,FiniteField(3^k));
Ek := #Points(ProjectiveClosure(Ck));
[Ek,3^k+1-a^k-aa^k];
end for;
To obtain the minimal polynomial of endomorphisms :
Write that $E(overline{mathbb{F}_3}) $ is a subgroup of $mathbb{Q}/mathbb{Z}times mathbb{Q}/mathbb{Z}$ so any group homomorphism acts as a matrix
$A=pmatrix{a & b \c & d} in M_2(widehat{mathbb{Z}})$ (matrix of profinite integers). Then the dual homomorphism is $A^*=pmatrix{d & -b \-c & a}$ so that $A^* A = pmatrix{ad-bc& 0 \ 0 & ad-bc}$ and $A + A^* = pmatrix{a+d & 0 \0 & a+d}$, so they both act as direct multiplication by an element in $widehat{mathbb{Z}}$. If $A$ is an endomorphism (defined by polynomial equations) then so are $A^*,A + A^*,A^*A$ so the latter must act as multiplication by elements in $mathbb{Z}$.
$endgroup$
add a comment |
$begingroup$
Let $phi^k(x,y)= (x^{3^k},y^{3^k})$ then $#E(mathbb{F}_{3^k}) =deg_s(phi^k-1)$. Is the endomorphism $phi^k-1$ separable ? Yes because inserapable endomorphisms are of the form $rho circ phi$. Then $$deg_s(phi^k-1) = deg(phi^k-1)=((phi^*)^k-1)(phi^k-1)\= (phi^*phi)^k+1-(phi^*)^k-phi^k = 3^k+1-alpha^k-(alpha^*)^k$$ where $phi^*$ is the dual isogeny such that $phi^* phi = deg(phi) = 3$ and $phi+phi^* = t = 3+1-#E(mathbb{F}_{3})$ and $alpha$ is the root of the minimal polynomial $X^2-t X + 3 = 0$ of the Frobenius
magma code
F := FiniteField(3); A<x,y> := AffineSpace(F,2);
C := Curve(A,y^2-x^3-x^2-x-1);
t :=3+1- #Points(ProjectiveClosure(C));
P<z> := PolynomialRing(Integers()); K<a> := NumberField(z^2-t*z+3); aa := Norm(a)/a;
for k in [2..10] do
Ck := BaseChange(C,FiniteField(3^k));
Ek := #Points(ProjectiveClosure(Ck));
[Ek,3^k+1-a^k-aa^k];
end for;
To obtain the minimal polynomial of endomorphisms :
Write that $E(overline{mathbb{F}_3}) $ is a subgroup of $mathbb{Q}/mathbb{Z}times mathbb{Q}/mathbb{Z}$ so any group homomorphism acts as a matrix
$A=pmatrix{a & b \c & d} in M_2(widehat{mathbb{Z}})$ (matrix of profinite integers). Then the dual homomorphism is $A^*=pmatrix{d & -b \-c & a}$ so that $A^* A = pmatrix{ad-bc& 0 \ 0 & ad-bc}$ and $A + A^* = pmatrix{a+d & 0 \0 & a+d}$, so they both act as direct multiplication by an element in $widehat{mathbb{Z}}$. If $A$ is an endomorphism (defined by polynomial equations) then so are $A^*,A + A^*,A^*A$ so the latter must act as multiplication by elements in $mathbb{Z}$.
$endgroup$
add a comment |
$begingroup$
Let $phi^k(x,y)= (x^{3^k},y^{3^k})$ then $#E(mathbb{F}_{3^k}) =deg_s(phi^k-1)$. Is the endomorphism $phi^k-1$ separable ? Yes because inserapable endomorphisms are of the form $rho circ phi$. Then $$deg_s(phi^k-1) = deg(phi^k-1)=((phi^*)^k-1)(phi^k-1)\= (phi^*phi)^k+1-(phi^*)^k-phi^k = 3^k+1-alpha^k-(alpha^*)^k$$ where $phi^*$ is the dual isogeny such that $phi^* phi = deg(phi) = 3$ and $phi+phi^* = t = 3+1-#E(mathbb{F}_{3})$ and $alpha$ is the root of the minimal polynomial $X^2-t X + 3 = 0$ of the Frobenius
magma code
F := FiniteField(3); A<x,y> := AffineSpace(F,2);
C := Curve(A,y^2-x^3-x^2-x-1);
t :=3+1- #Points(ProjectiveClosure(C));
P<z> := PolynomialRing(Integers()); K<a> := NumberField(z^2-t*z+3); aa := Norm(a)/a;
for k in [2..10] do
Ck := BaseChange(C,FiniteField(3^k));
Ek := #Points(ProjectiveClosure(Ck));
[Ek,3^k+1-a^k-aa^k];
end for;
To obtain the minimal polynomial of endomorphisms :
Write that $E(overline{mathbb{F}_3}) $ is a subgroup of $mathbb{Q}/mathbb{Z}times mathbb{Q}/mathbb{Z}$ so any group homomorphism acts as a matrix
$A=pmatrix{a & b \c & d} in M_2(widehat{mathbb{Z}})$ (matrix of profinite integers). Then the dual homomorphism is $A^*=pmatrix{d & -b \-c & a}$ so that $A^* A = pmatrix{ad-bc& 0 \ 0 & ad-bc}$ and $A + A^* = pmatrix{a+d & 0 \0 & a+d}$, so they both act as direct multiplication by an element in $widehat{mathbb{Z}}$. If $A$ is an endomorphism (defined by polynomial equations) then so are $A^*,A + A^*,A^*A$ so the latter must act as multiplication by elements in $mathbb{Z}$.
$endgroup$
Let $phi^k(x,y)= (x^{3^k},y^{3^k})$ then $#E(mathbb{F}_{3^k}) =deg_s(phi^k-1)$. Is the endomorphism $phi^k-1$ separable ? Yes because inserapable endomorphisms are of the form $rho circ phi$. Then $$deg_s(phi^k-1) = deg(phi^k-1)=((phi^*)^k-1)(phi^k-1)\= (phi^*phi)^k+1-(phi^*)^k-phi^k = 3^k+1-alpha^k-(alpha^*)^k$$ where $phi^*$ is the dual isogeny such that $phi^* phi = deg(phi) = 3$ and $phi+phi^* = t = 3+1-#E(mathbb{F}_{3})$ and $alpha$ is the root of the minimal polynomial $X^2-t X + 3 = 0$ of the Frobenius
magma code
F := FiniteField(3); A<x,y> := AffineSpace(F,2);
C := Curve(A,y^2-x^3-x^2-x-1);
t :=3+1- #Points(ProjectiveClosure(C));
P<z> := PolynomialRing(Integers()); K<a> := NumberField(z^2-t*z+3); aa := Norm(a)/a;
for k in [2..10] do
Ck := BaseChange(C,FiniteField(3^k));
Ek := #Points(ProjectiveClosure(Ck));
[Ek,3^k+1-a^k-aa^k];
end for;
To obtain the minimal polynomial of endomorphisms :
Write that $E(overline{mathbb{F}_3}) $ is a subgroup of $mathbb{Q}/mathbb{Z}times mathbb{Q}/mathbb{Z}$ so any group homomorphism acts as a matrix
$A=pmatrix{a & b \c & d} in M_2(widehat{mathbb{Z}})$ (matrix of profinite integers). Then the dual homomorphism is $A^*=pmatrix{d & -b \-c & a}$ so that $A^* A = pmatrix{ad-bc& 0 \ 0 & ad-bc}$ and $A + A^* = pmatrix{a+d & 0 \0 & a+d}$, so they both act as direct multiplication by an element in $widehat{mathbb{Z}}$. If $A$ is an endomorphism (defined by polynomial equations) then so are $A^*,A + A^*,A^*A$ so the latter must act as multiplication by elements in $mathbb{Z}$.
edited 35 mins ago
answered 3 hours ago
reunsreuns
20.7k21148
20.7k21148
add a comment |
add a comment |
$begingroup$
This is, indeed, easy after you have calculated the number of points over the prime field. It is straightforward to list them
$$
E(Bbb{F}_3)={(0,1),(0,-1),(1,1),(1,-1),(-1,0),infty}.
$$
In other words $|E(Bbb{F}_3)|=6.$ This piece of information gives us the complex numbers
$alpha,overline{alpha}$
(see reuns's post for their interpretation as eigenvalues of Frobenius on the Tate module) as they are known to safisfy the equations $|alpha|^2=3$ and
$$
alpha+overline{alpha}=3+1-|E(Bbb{F}_3)|=-2.
$$
The real part of $alpha$ is thus equal to $-1$, so $alpha=-1pm isqrt2$.
The formula for the number of rational poinst on the extension field then reads
$$
|E(Bbb{F}_{3^k})|=3^k+1-alpha^k-overline{alpha}^k=3^k+1-2operatorname{Re}(-1+isqrt2)^k.
$$
For example, when $k=2$, $alpha^2=(-1+isqrt2)^2=-1-2isqrt2$
implying that $|E(Bbb{F}_9)|=9+1+2=12$. This passes the litmus test of being divisible by $|E(Bbb{F}_3)|$ (Lagrange's theorem from elementary group theory), possibly adding to our confidence in the correctness of the result.
$endgroup$
add a comment |
$begingroup$
This is, indeed, easy after you have calculated the number of points over the prime field. It is straightforward to list them
$$
E(Bbb{F}_3)={(0,1),(0,-1),(1,1),(1,-1),(-1,0),infty}.
$$
In other words $|E(Bbb{F}_3)|=6.$ This piece of information gives us the complex numbers
$alpha,overline{alpha}$
(see reuns's post for their interpretation as eigenvalues of Frobenius on the Tate module) as they are known to safisfy the equations $|alpha|^2=3$ and
$$
alpha+overline{alpha}=3+1-|E(Bbb{F}_3)|=-2.
$$
The real part of $alpha$ is thus equal to $-1$, so $alpha=-1pm isqrt2$.
The formula for the number of rational poinst on the extension field then reads
$$
|E(Bbb{F}_{3^k})|=3^k+1-alpha^k-overline{alpha}^k=3^k+1-2operatorname{Re}(-1+isqrt2)^k.
$$
For example, when $k=2$, $alpha^2=(-1+isqrt2)^2=-1-2isqrt2$
implying that $|E(Bbb{F}_9)|=9+1+2=12$. This passes the litmus test of being divisible by $|E(Bbb{F}_3)|$ (Lagrange's theorem from elementary group theory), possibly adding to our confidence in the correctness of the result.
$endgroup$
add a comment |
$begingroup$
This is, indeed, easy after you have calculated the number of points over the prime field. It is straightforward to list them
$$
E(Bbb{F}_3)={(0,1),(0,-1),(1,1),(1,-1),(-1,0),infty}.
$$
In other words $|E(Bbb{F}_3)|=6.$ This piece of information gives us the complex numbers
$alpha,overline{alpha}$
(see reuns's post for their interpretation as eigenvalues of Frobenius on the Tate module) as they are known to safisfy the equations $|alpha|^2=3$ and
$$
alpha+overline{alpha}=3+1-|E(Bbb{F}_3)|=-2.
$$
The real part of $alpha$ is thus equal to $-1$, so $alpha=-1pm isqrt2$.
The formula for the number of rational poinst on the extension field then reads
$$
|E(Bbb{F}_{3^k})|=3^k+1-alpha^k-overline{alpha}^k=3^k+1-2operatorname{Re}(-1+isqrt2)^k.
$$
For example, when $k=2$, $alpha^2=(-1+isqrt2)^2=-1-2isqrt2$
implying that $|E(Bbb{F}_9)|=9+1+2=12$. This passes the litmus test of being divisible by $|E(Bbb{F}_3)|$ (Lagrange's theorem from elementary group theory), possibly adding to our confidence in the correctness of the result.
$endgroup$
This is, indeed, easy after you have calculated the number of points over the prime field. It is straightforward to list them
$$
E(Bbb{F}_3)={(0,1),(0,-1),(1,1),(1,-1),(-1,0),infty}.
$$
In other words $|E(Bbb{F}_3)|=6.$ This piece of information gives us the complex numbers
$alpha,overline{alpha}$
(see reuns's post for their interpretation as eigenvalues of Frobenius on the Tate module) as they are known to safisfy the equations $|alpha|^2=3$ and
$$
alpha+overline{alpha}=3+1-|E(Bbb{F}_3)|=-2.
$$
The real part of $alpha$ is thus equal to $-1$, so $alpha=-1pm isqrt2$.
The formula for the number of rational poinst on the extension field then reads
$$
|E(Bbb{F}_{3^k})|=3^k+1-alpha^k-overline{alpha}^k=3^k+1-2operatorname{Re}(-1+isqrt2)^k.
$$
For example, when $k=2$, $alpha^2=(-1+isqrt2)^2=-1-2isqrt2$
implying that $|E(Bbb{F}_9)|=9+1+2=12$. This passes the litmus test of being divisible by $|E(Bbb{F}_3)|$ (Lagrange's theorem from elementary group theory), possibly adding to our confidence in the correctness of the result.
answered 8 mins ago
Jyrki LahtonenJyrki Lahtonen
109k13170377
109k13170377
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%2f3129575%2fcalculate-the-number-of-points-of-an-elliptic-curve-in-medium-weierstrass-form-o%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