Subgroup Order

给定某个子群

${\mathbb{G}}_1$，但是

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

给定一个椭圆曲线群：

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

With the help of this excellent interactive tool 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}

根据拉格朗日定理, 子群的 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\ne (10,6)$
  • $k=1$ 时，
    $x=5$,
    $xG=(10,6)$，即
    $x=5$
• 新的子群不能太大也不能太小，太大了在新的子群里面求解离散对数会比较麻烦，太小了最后一步的搜索效率不高。