Ed25519のベースポイントを計算する

## Ed25519について
Montgomery 型の Curve25519 と双有理同値の Twisted Edwards 型曲線を使った EdDSA

### ベースになっているフィールド
$ q = 2^{255} - 19 $　という素数が位数のフィールド $F_q$

### 楕円曲線の式
Twisted Edwards curve の式は
$ E = \lbrace (x,y) \in F_q \times F_q : -x^2 + y^2 = 1 + dx^2y^2 \rbrace $

で、$d$ が、
$ d = -121665 / 121666 \in F_q $ （これは実数ではなくて、$F_q$ に含まれる整数）
のもの。

## ベースポイント B
$ B = (x, 4/5) \in E $ の内、$x$ がポジティブな方の点。

## 具体的にベースポイントをどう計算するのか？
### y の計算
$ y = 4/5 $　なので、

```
y = 4 * inv(5) mod 2^255 - 19 
  = 46316835694926478169428394003475163141307993866256225615783033603165251855960
```

### x の計算

曲線の式 $ -x^2 + y^2 = 1 + dx^2y^2 $ を $x^2$ について整理すると、

$ -x^2 + y^2 = 1 + dx^2y^2 $
$ y^2 - 1 = x^2 + dx^2y^2 $
$ y^2 - 1 = x^2 (1 + dy^2) $
$ x^2 = \frac{y^2 - 1}{1 + dy^2} $

となる。

$ a = \frac{y^2 - 1}{1 + dy^2} $

と置き換えて、

$ x^2 = a$

この平方剰余 $a$ の根を計算する。

#### 平方剰余 a の根の計算

存在する曲線上の点の x 座標を求めているので、$x^2 = a$ となるような $x$ は存在する。
また、$q$ は素数なので、$a$ と $q$ は互いに素になり、フェルマーの小定理 $a^{q-1} \equiv 1 \bmod q $
が成り立つ。

$a$ と $x^2$ を置き換えて、

$(x^2)^{q-1} \equiv 1 \bmod q $
$x^{\frac{q-1}{2}} \equiv 1 \bmod q \ \ ...\ (ア)$ 

ところで、素数 $q = 2^{255} - 19$ は、
$q \bmod 8 = 5$ という特徴があるので、ある整数 $k$ について、$q = 8k + 5$

また、そこから、$q \bmod 4 = 1$ なので、$q-1$ が $4$ で割り切れて、$\frac{q-1}{4}$ が整数になる。
これを使って$(ア)$ を変形すると

$x^{\frac{q-1}{2}} \equiv 1 \bmod q$ 
$(x^{\frac{q-1}{4}})^2 \equiv 1 \bmod q$ 

とかける。
$ x^{\frac{q-1}{4}} $ は、自乗すると $1$ になる整数なので、$1$ か $-1$ になる。

まず、どちらのケースでも必要になる $k$ を $q = 8k + 5$ から計算する。

$q = 8k + 5$ 
$8k = q - 5$ 
$k = \frac{q-5}{8}$


##### 1 の場合
$x = a^{k+1} = a^{(\frac{q-5}{8})+1} = a^{\frac{q+3}{8}} $ で $a$ の根が計算できる。
以下のように、$(a^{k+1})^2 = a$ となる。

$(a^{k+1})^2 = a^{2k+2} = a^{2(\frac{q-5}{8}) + 2} = a^{\frac{q-5}{4} + 2} = a^{\frac{q-1}{4} + 1} = a^{\frac{q-1}{4}} a$

$ x^{\frac{q-1}{4}} = 1$ なので、

$ a^{\frac{q-1}{4}} a = 1 a = a $　

##### -1 の場合
$x = 2^{2k+1} a^{k+1} = 2^{2(\frac{q-5}{8})+1} a^{(\frac{q-5}{8})+1} = 2^{\frac{q-1}{4}} a^{\frac{q+3}{8}}$ で $a$ の根が計算できる。
以下のように、$(2^{2k+1} a^{k+1})^2 = a$ となる。

$(2^{2k+1} a^{k+1})^2 = 2^{4k+2} a^{2k+2} = 2^{4(\frac{q-5}{8})+2} a^{2(\frac{q-5}{8})+2} = 2^{\frac{q-5}{2}+2} a^{\frac{q-5}{4}+2} = 2^{\frac{q-1}{2}} a^{\frac{q-1}{4}+1} = 2^{\frac{q-1}{2}} a^{\frac{q-1}{4}}a$ 

$ x^{\frac{q-1}{4}} = -1$ なので、
$ 2^{\frac{q-1}{2}} a^{\frac{q-1}{4}}a = 2^{\frac{q-1}{2}} (-1) a \ \ ...(イ)$

オイラーの基準 $(\frac{a}{q}) = a^{\frac{q-1}{2}} \bmod p $ の $a$ を $2$ に置き換えて、
$(\frac{2}{q}) = 2^{\frac{q-1}{2}} \bmod q $

平方剰余の第２補充法則の、$q \equiv 5 \bmod{8}$ の場合の

$(\frac{2}{q}) = -1 \bmod q $

組み合わせると、

$2^{\frac{q-1}{2}}  = -1 \bmod q $

これを $(イ)$ に代入すると、

$ 2^{\frac{q-1}{2}} (-1) a = (-1)(-1)a = 1a = a$

##### 計算方法のまとめ
$x = a^{\frac{q+3}{8}} \ \ ...(ウ)$ 

か、
$x = 2^{\frac{q-1}{4}} a^{\frac{q+3}{8}} \ \ ...(エ)$ 

のいずれかで計算できる。

##### 正負の調整
ベースポイントの $x$ は、$y=4/5$ に対応する２つの $x$ のうち正の値の方なので、計算した平方根が負の値だった場合には、正の値に変換する。

Ed25519のフィールドでは、最下位ビットが $1$ である数を負の値に紐づけているので、$x$ の最下位ビットをチェックして、正負の判断をする。

フィールドの位数から $x$ を引くことで正負の反転ができる。位数は素数なので、反転することで、奇数であれば偶数に、偶数であれば奇数に変換される。

##### 計算結果
計算すると「1 の場合」が当てはまり、負の値の $x$ が出てくるので、正の値に戻すと、

```
x = 15112221349535400772501151409588531511454012693041857206046113283949847762202
```
になる。

#### Pythonでのリファレンス実装
「[ここ](https://ed25519.cr.yp.to/python/ed25519.py)」にある、Pythonでのリファレンス実装では、
`xrecover`という関数に、この計算が実装されている。

```python
I = expmod(2,(q-1)/4,q) #(ウ)に掛けると(エ）になる数

def xrecover(y):
  xx = (y*y-1) * inv(d*y*y+1) # 楕円曲線の式を x^2 について整理した式
  x = expmod(xx,(q+3)/8,q) # (ウ)を計算
  if (x*x - xx) % q != 0: x = (x*I) % q # (ウ)が一致しなければ(エ)を計算
  if x % 2 != 0: x = q-x # x が負なら正に　※y の最下位ビットが x の parity なので、if x % 2 != y % 2 が正しい気がする 
  return x
```

## 参考文献
[Ed25519の論文](https://ed25519.cr.yp.to/ed25519-20110926.pdf)
[mod pでの平方剰余を計算する(p mod 8 = 5の場合)](https://pebble8888.hatenablog.com/entry/2017/07/29/233633)