# Subgroup Order

给定某个子群 $\mathbb{G}_1$，但是 $\mathbb{G}_1$ 的 order 很大，不利于求解 ECDLP，怎么将该过程映射到较小的子群里面。

给定一个椭圆曲线群：

$y^2 = x^3 + 4 \mod 11$

With the help of [this excellent interactive tool](https://andrea.corbellini.name/ecc/interactive/modk-mul.html) we can explicitly view its composition:


p = 11
Fp = GF(p)

E = EllipticCurve(Fp, [0, 4])

E.order()
# 12
factor(E.order())
# 2^2 * 3

sub_orders = set()
for p in E.points():
     sub_orders.add(p.order())

sub_orders
# {1, 2, 3, 4, 6, 12}

根据[拉格朗日定理](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)), 子群的 order 能够整除群的 order。这个例子有点特殊，它的子群的 order 取到了群的 order 的所有的因子。有的只能去到部分因子，比如缺少 order = 4 的子群等。

那群里面的元素是怎么生成子群的？

for p in E.points():
     print("====", p)
     for i in range(1, p.order()+1):
         print(i, i*p, (i*p).order())

输出：

==== (0 : 1 : 0)
1 (0 : 1 : 0) 1
==== (0 : 2 : 1)
1 (0 : 2 : 1) 3
2 (0 : 9 : 1) 3
3 (0 : 1 : 0) 1
==== (0 : 9 : 1)
1 (0 : 9 : 1) 3
2 (0 : 2 : 1) 3
3 (0 : 1 : 0) 1
==== (1 : 4 : 1)
1 (1 : 4 : 1) 12
2 (10 : 5 : 1) 6
3 (3 : 8 : 1) 4
4 (0 : 9 : 1) 3
5 (2 : 1 : 1) 12
6 (6 : 0 : 1) 2
7 (2 : 10 : 1) 12
8 (0 : 2 : 1) 3
9 (3 : 3 : 1) 4
10 (10 : 6 : 1) 6
11 (1 : 7 : 1) 12
12 (0 : 1 : 0) 1
==== (1 : 7 : 1)
1 (1 : 7 : 1) 12
2 (10 : 6 : 1) 6
3 (3 : 3 : 1) 4
4 (0 : 2 : 1) 3
5 (2 : 10 : 1) 12
6 (6 : 0 : 1) 2
7 (2 : 1 : 1) 12
8 (0 : 9 : 1) 3
9 (3 : 8 : 1) 4
10 (10 : 5 : 1) 6
11 (1 : 4 : 1) 12
12 (0 : 1 : 0) 1
==== (2 : 1 : 1)
1 (2 : 1 : 1) 12
2 (10 : 6 : 1) 6
3 (3 : 8 : 1) 4
4 (0 : 2 : 1) 3
5 (1 : 4 : 1) 12
6 (6 : 0 : 1) 2
7 (1 : 7 : 1) 12
8 (0 : 9 : 1) 3
9 (3 : 3 : 1) 4
10 (10 : 5 : 1) 6
11 (2 : 10 : 1) 12
12 (0 : 1 : 0) 1
==== (2 : 10 : 1)
1 (2 : 10 : 1) 12
2 (10 : 5 : 1) 6
3 (3 : 3 : 1) 4
4 (0 : 9 : 1) 3
5 (1 : 7 : 1) 12
6 (6 : 0 : 1) 2
7 (1 : 4 : 1) 12
8 (0 : 2 : 1) 3
9 (3 : 8 : 1) 4
10 (10 : 6 : 1) 6
11 (2 : 1 : 1) 12
12 (0 : 1 : 0) 1
==== (3 : 3 : 1)
1 (3 : 3 : 1) 4
2 (6 : 0 : 1) 2
3 (3 : 8 : 1) 4
4 (0 : 1 : 0) 1
==== (3 : 8 : 1)
1 (3 : 8 : 1) 4
2 (6 : 0 : 1) 2
3 (3 : 3 : 1) 4
4 (0 : 1 : 0) 1
==== (6 : 0 : 1)
1 (6 : 0 : 1) 2
2 (0 : 1 : 0) 1
==== (10 : 5 : 1)
1 (10 : 5 : 1) 6
2 (0 : 9 : 1) 3
3 (6 : 0 : 1) 2
4 (0 : 2 : 1) 3
5 (10 : 6 : 1) 6
6 (0 : 1 : 0) 1
==== (10 : 6 : 1)
1 (10 : 6 : 1) 6
2 (0 : 2 : 1) 3
3 (6 : 0 : 1) 2
4 (0 : 9 : 1) 3
5 (10 : 5 : 1) 6
6 (0 : 1 : 0) 1


设 $G = (10, 5)$, $xG = (10, 6)$，怎么求出 $x = 5$
- $G$ 生成的子群的 order 为 6，太大了，$6 = 2 \times 3$，我们把求解过程映射到 order 为 3 的子群上去。
- $P= 2G = (0,9)$ 的 order 为 3。
- $2xG = (0,2) = xP$
- 很容易求出 $x = 2 + 3k$
- 搜索 $k$，
- $k = 0$ 时，$x = 2$, $xG \neq (10, 6)$
- $k = 1$ 时，$x = 5$, $xG = (10, 6)$，即 $x = 5$
- 新的子群不能太大也不能太小，太大了在新的子群里面求解离散对数会比较麻烦，太小了最后一步的搜索效率不高。