楕円曲線における離散対数問題

例として、
$F_{43}$
$y^{2} = x^{3} + 7$
を考えます。
$F_{43}$ というのは数として、43で割った余り、つまり、0,1,2,3,...,42 だけの世界を考えるということです。
x, y の値として0,1,2,3,...,42だけを考えます。
42よりも大きな値は43で割った余りと同一の値であるとみなします。
すると $y^{2} = x^{3} + 7$ の式を満たすx, yの値は有限個に限られます。
例えば、 $12^{2} = 144 = 43 \times 3 + 15 = 15$
$2^{3} + 7 = 9 + 7 = 15$
なので(x, y) = (2, 12)は上の式を満たします。
上の式を満たす点(x, y)のことを有理点と呼びます。

上の式を満たす点の数は下に示すように31個あります。
これらの点に対して加法を定義することができます。
点Pと点Qを加えて点Rとなる(P+Q=R)時、点P,Q,Rは全てこの式を満たします。
この加法は群をなします。

有理点の数(群位数)は31で素数です。
点の加法群の位数が31ということは部分群が存在せず、巡回群つまり一つの元を足し合わせることで全ての元が表現できるということです。
全ての点が位数31となります。
ちなみに、無限遠点O以外の30個の点(x, y)を図にしたものがこちらです。

P1:(2,12)
P2:(2,31)
P3:(7,7)
P4:(7,36)
P5:(12,12)
P6:(12,31)
P7:(13,21)
P8:(13,22)
P9:(20,3)
P10:(20,40)
P11:(21,18)
P12:(21,25)
P13:(25,18)
P14:(25,25)
P15:(29,12)
P16:(29,31)
P17:(32,3)
P18:(32,40)
P19:(34,3)
P20:(34,40)
P21:(35,21)
P22:(35,22)
P23:(37,7)
P24:(37,36)
P25:(38,21)
P26:(38,22)
P27:(40,18)
P28:(40,25)
P29:(42,7)
P30:(42,36)
O

まず、どれでもよいので基準の点をO以外から選びます。これをベースポイントと呼びます。
ここでは、P13:(25, 18)を選びます。
この点を点の加算公式を用いて整数倍していった結果がこちらです。

P13:(25,18)
2*P13:(34,40) = P20
3*P13:(42,36) = P30
4*P13:(35,22) = P22
5*P13:(21,18) = P11
6*P13:(40,25) = P28
7*P13:(13,22) = P8
8*P13:(29,12) = P15
9*P13:(2,12) = P1
10*P13:(32,40) = P18
11*P13:(38,21) = P25
12*P13:(20,3) = P9
13*P13:(7,36) = P4
14*P13:(12,12) = P5
15*P13:(37,36) = P24
16*P13:(37,7) = P23
17*P13:(12,31) = P6
18*P13:(7,7) = P3
19*P13:(20,40) = P10
20*P13:(38,22) = P26
21*P13:(32,3) = P17
22*P13:(2,31) = P2
23*P13:(29,31) = P16
24*P13:(13,21) = P7
25*P13:(40,18) = P27
26*P13:(21,25) = P12
27*P13:(35,21) = P21
28*P13:(42,7) = P29
29*P13:(34,3) = P19
30*P13:(25,25) = P14
31*P13:O

右辺の点は全て重複がありません。
整数を使った離散対数問題と同じように、
$n \times P = Q$
としたとき、Qの点を与えたときにnの値を求めるのは時間的に困難となります。
これが楕円曲線における離散対数問題です。
同じ楕円曲線 $y^{2} = x^{3} + 7$ を用いて $F_{2^{256} - 2^{32} - 977}$
ベースポイント
(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
としたのがsecp256k1の楕円曲線です。
群位数は 115792089237316195423570985008687907852837564279074904382605163141518161494337
で素数です。