SageMath: elliptic curve - cofactor

# SageMathで楕円曲線のCofactorを見てみる

https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/constructor.html

このサイトを参考にSageMathで楕円曲線します。

## secp256k1

```
sage: E = EllipticCurve(GF(2 ** 256 - 2 ** 32 - 977), [0, 7])
```

するとこのように構築されます。

```
sage: print(E)
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
```

### スカラー倍算
ベースポイントGを設定し、スカラー倍算してみます。
```
sage: G = E([55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424])
```

1倍算
```
sage: 1 * G
(55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)
```

2倍算
```
sage: 2 * G
(89565891926547004231252920425935692360644145829622209833684329913297188986597 : 12158399299693830322967808612713398636155367887041628176798871954788371653930 : 1)
```

楕円曲線上に存在しない点をベースポイントとして定義しようとすると、、
```
sage: G = E([1,3])
```

このようにエラーが出力されます。
```
TypeError: Coordinates [1, 3, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
```

長いエラーが出力されますが、最後のメッセージ（上記の箇所）だけ見れば良さそう。
<details>
<summary>error message</summary>

```
G = E([1,3])
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/structure/category_object.pyx:839, in sage.structure.category_object.CategoryObject.getattr_from_category (build/cythonized/sage/structure/category_object.c:7204)()
    838 try:
--> 839     return self.__cached_methods[name]
    840 except KeyError:

KeyError: 'point_homset'

During handling of the above exception, another exception occurred:

AttributeError                            Traceback (most recent call last)
File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/projective/projective_subscheme.py:122, in AlgebraicScheme_subscheme_projective.point(self, v, check)
    121 try:
--> 122     return self._point(self.point_homset(), v, check=check)
    123 except AttributeError:  # legacy code without point_homset

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/elliptic_curves/ell_point.py:259, in EllipticCurvePoint_field.__init__(self, curve, v, check)
    238 """
    239 Constructor for a point on an elliptic curve.
    240 
   (...)
    257     (1 : -2 : 1)
    258 """
--> 259 point_homset = curve.point_homset()
    260 R = point_homset.value_ring()

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/structure/category_object.pyx:833, in sage.structure.category_object.CategoryObject.__getattr__ (build/cythonized/sage/structure/category_object.c:7123)()
    832 """
--> 833 return self.getattr_from_category(name)
    834 

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/structure/category_object.pyx:848, in sage.structure.category_object.CategoryObject.getattr_from_category (build/cythonized/sage/structure/category_object.c:7289)()
    847 
--> 848             attr = getattr_from_other_class(self, cls, name)
    849             self.__cached_methods[name] = attr

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/cpython/getattr.pyx:356, in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2706)()
    355     dummy_error_message.name = name
--> 356     raise AttributeError(dummy_error_message)
    357 cdef PyObject* attr = instance_getattr(cls, name)

AttributeError: 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp' object has no attribute '__custom_name'

During handling of the above exception, another exception occurred:

TypeError                                 Traceback (most recent call last)
Cell In [5], line 1
----> 1 G = E([Integer(1),Integer(3)])

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/elliptic_curves/ell_generic.py:582, in EllipticCurve_generic.__call__(self, *args, **kwds)
    579             return self._reduce_point(args[0], characteristic)
    580     args = tuple(args[0])
--> 582 return plane_curve.ProjectivePlaneCurve.__call__(self, *args, **kwds)

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/generic/scheme.py:266, in Scheme.__call__(self, *args)
    264             return S
    265         args = S
--> 266 return self.point(args)

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/projective/projective_subscheme.py:124, in AlgebraicScheme_subscheme_projective.point(self, v, check)
    122         return self._point(self.point_homset(), v, check=check)
    123     except AttributeError:  # legacy code without point_homset
--> 124         return self._point(self, v, check=check)
    126 return self.point_homset()(v, check=check)

File /private/var/tmp/sage-10.0-current/local/var/lib/sage/venv-python3.11.1/lib/python3.11/site-packages/sage/schemes/elliptic_curves/ell_point.py:298, in EllipticCurvePoint_field.__init__(self, curve, v, check)
    296         test = y**2 + (a1*x+a3)*y - (((x+a2)*x+a4)*x+a6)
    297     if not test == 0:
--> 298         raise TypeError("Coordinates %s do not define a point on %s" % (list(v), curve))
    300 SchemeMorphism_point_abelian_variety_field.__init__(self, point_homset, v, check=False)

TypeError: Coordinates [1, 3, 1] do not define a point on Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
```
</details>

### #Eを計算する
E(GF(F_p))の#Eを算出し、素因数分解します。

```
sage: E.cardinality().factor()
115792089237316195423570985008687907852837564279074904382605163141518161494337
```

これは$E(GF(F_p))$の元Gの位数と一致しています。
```
sage: G.order()
115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: 
```

### cofactor
secp256k1はcofactor = 1の曲線であることが簡単に確認できました。

cofactor = 1:
```math

\forall s \in E(GF(F_p)),\exists r \in \mathbb{N}, s.t. \space s^r = G \\

```
Then, r is called order and the following holds
```math
r =　\#E(GF(F_p))
```


## curve25519

ガロア体上にed25519を構築します。
```
sage: E = EllipticCurve(GF(2^255-19),[0,486662,0,1,0])
```

構築された方程式を見てみます。
```
sage: print(E)
Elliptic Curve defined by y^2 = x^3 + 486662*x^2 + x over Finite Field of size 57896044618658097711785492504343953926634992332820282019728792003956564819949
```

### スカラー倍算

```
sage: G = E([9, 14781619447589544791020593568409986887264606134616475288964881837755586237401])
sage: 1 * G
(9 : 14781619447589544791020593568409986887264606134616475288964881837755586237401 : 1)
sage: 2 * G
(14847277145635483483963372537557091634710985132825781088887140890597596352251 : 8914613091229147831277935472048643066880067899251840418855181793938505594211 : 1)
```

base pointが属する部分群の位数は素数
```
sage: G.order()
7237005577332262213973186563042994240857116359379907606001950938285454250989
```


### #Eを計算する
E(GF(F_p))の#Eを算出し、素因数分解します。

```
sage: E.cardinality().factor()
2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989
```

### cofactor
curve25519はcofactor = 2^3です。

cofactor > 1:
```math

\forall s \in E(GF(F_p)),\exists r \in \mathbb{N}, s.t. \space s^r = G \\

```
Then, 
```math
r \leq　　\#E(GF(F_p))
```


### elements in small subgroup
curve25519のsmall subgroupの点を20個列挙してみる。

```
sage: for i in range(20):
....:     P = E.random_element()
....:     Q = P.__mul__(2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed)
....:     print (Q.order(), Q)
....: 
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 25869741026945134960544184956460972567356779614910045322022475500191642319642 : 1)
1 (0 : 1 : 0)
4 (1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1)
2 (0 : 0 : 1)
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 32026303591712962751241307547882981359278212717910236697706316503764922500307 : 1)
4 (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)

2 (0 : 0 : 1)
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 32026303591712962751241307547882981359278212717910236697706316503764922500307 : 1)
8 (39382357235489614581723060781553021112529911719440698176882885853963445705823 : 10506421237558716435988711236408671798265365380393424752549290025458740468278 : 1)
4 (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 32026303591712962751241307547882981359278212717910236697706316503764922500307 : 1)
4 (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 32026303591712962751241307547882981359278212717910236697706316503764922500307 : 1)
8 (39382357235489614581723060781553021112529911719440698176882885853963445705823 : 10506421237558716435988711236408671798265365380393424752549290025458740468278 : 1)
8 (39382357235489614581723060781553021112529911719440698176882885853963445705823 : 10506421237558716435988711236408671798265365380393424752549290025458740468278 : 1)
1 (0 : 1 : 0)
8 (39382357235489614581723060781553021112529911719440698176882885853963445705823 : 10506421237558716435988711236408671798265365380393424752549290025458740468278 : 1)
4 (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)
8 (325606250916557431795983626356110631294008115727848805560023387167927233504 : 25869741026945134960544184956460972567356779614910045322022475500191642319642 : 1)
4 (1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1)
```

上記で算出された点集合のうち、位数4の点はこうなっている
```
sage: T = E([1 , 9094040566125962849133224048217411091405536248825867518642941381412595940312])
sage: T.order()
4

```





## ed25519
SageMathはツイストエドワーズ曲線をサポートしていません。

なので、次のような変換関数を定義して呼び出します。
```
sage: p = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
K = GF(p)
a = K(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec)
d = K(0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3)
E = EllipticCurve(K, (K(-1/48) * (a^2 + 14*a*d + d^2),K(1/864) * (a + d) * (-a^2 + 34*a*d - d^2)))
def to_weierstrass(a, d, x, y):
	return ((5*a + a*y - 5*d*y - d)/(12 - 12*y), (a + a*y - d*y -d)/(4*x - 4*x*y))
def to_twistededwards(a, d, u, v):
	y = (5*a - 12*u - d)/(-12*u - a + 5*d)
	x = (a + a*y - d*y -d)/(4*v - 4*v*y)
	return (x, y)
G = E(*to_weierstrass(a, d, K(0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A), K(0x6666666666666666666666666666666666666666666666666666666666666658)))
E.set_order(0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed * 0x08)
# This curve is a Weierstrass curve (SAGE does not support TwistedEdwards curves) birationally equivalent to the intended curve.
# You can use the to_weierstrass and to_twistededwards functions to convert the points.

```

### #Eを計算する

```
sage: E.cardinality().factor()
2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989
```

### cofactor
前出の結果からed25519のcofactorはcurve25519とおなじ2^3となります。


## BLS12-381

```
sage: E = EllipticCurve(GF(0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab), [0, 4])
```

```
sage: print(E)
Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
```

### #Eを計算する
```
sage: E.cardinality().factor()
3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513
```

cofactor
```
sage: 3 * 11^2 * 10177^2 * 859267^2 * 52437899^2
```

### cofactor
BLS12-381のEのcofactorは76329603384216526031706109802092473003(= 0x396C8C005555E1568C00AAAB0000AAAB)




## Links
https://tex2e.github.io/rfc-translater/html/rfc7748.html
https://en.wikipedia.org/wiki/Curve25519
https://tex2e.github.io/rfc-translater/html/rfc7748.html
https://datatracker.ietf.org/doc/draft-irtf-cfrg-pairing-friendly-curves/08/
https://qiita.com/tnakagawa/items/5c73763e420dc9baddf2
https://eprint.iacr.org/2019/403.pdf
https://hackmd.io/@benjaminion/bls12-381