Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

secp256k1の群構造

secp256k1は素体 F_qで、
 q = 2^{256}-2^{32}-977
群位数は L = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 = 115792089237316195423570985008687907852837564279074904382605163141518161494337
であり素数ですから、巡回群(cyclic group)です。 つまり、すべての元は任意の元のべき乗で表せるということです。
Lは素数なので約数は持ちませんから、全ての点がL等分点であり、L以外の値の等分点はないということになります。

ついでに  L = q + 1 - a でaの値を求めておくと、
 a = q + 1 - L = 432420386565659656852420866390673177327

全く意味はありませんが、 F_q上の有理点の数が変わっている時、 F_{q^{n}} 上の有理点の数は容易に分かります。
 x^{2} - a x + q = (x - \alpha )( x - \beta ) とおくと、
Number of  E( F_{q^{n}} ) = q^{n} + 1 - { \alpha } ^ {n} - { \beta } ^ {n} で求められます。
n=2の場合をsagemathで求めてみます。

sage: a = 432420386565659656852420866390673177327
sage: q = 2 ** 256 - 2 ** 32 - 977
sage print(q)
115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: S = solve(x^2 - a * x + q == 0, x); S
[x == -303414439467246543595250775667605759171/2*I*sqrt(3) + 432420386565659656852420866390673177327/2, x == 303414439467246543595250775667605759171/2*I*sqrt(3) + 432420386565659656852420866390673177327/2]
sage: alpha = -303414439467246543595250775667605759171/2*I*sqrt(3) + 432420386565659656852420866390673177327/2
sage: beta = 303414439467246543595250775667605759171/2*I*sqrt(3) + 432420386565659656852420866390673177327/2
sage: qq = q ** 2 + 1 - alpha ** 2 - beta ** 2 
sage: print(qq)
-(303414439467246543595250775667605759171/2*I*sqrt(3) + 432420386565659656852420866390673177327/2)^2 - (-303414439467246543595250775667605759171/2*I*sqrt(3) + 432420386565659656852420866390673177327/2)^2 + 13407807929942597099574024998205846127479365820592393377723561443720769383374469661147847687812952081302854773939601805382211292725060150247698793015185570 
sage: qqq = qq.expand()
sage: print(qqq)
13407807929942597099574024998205846127479365820592393377723561443720769383374514257935604725673157749673323532586203008139449912321682334073867837097663967
sage: is_prime(qqq)
False