1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
# ================================================== #
# Code to check whether a group element has order D #
# ================================================== #
"""
This code has been taken from:
https://github.com/FESTA-PKE/FESTA-SageMath
Copyright (c) 2023 Andrea Basso, Luciano Maino and Giacomo Pope.
"""
from sage.all import(
ZZ,
prod,
cached_function
)
def batch_cofactor_mul_generic(G_list, pis, group_action, lower, upper):
"""
Input: A list of elements `G_list`, such that
G is the first entry and the rest is empty
in the sublist G_list[lower:upper]
A list `pis` of primes p such that
their product is D
The `group_action` of the group
Indices lower and upper
Output: None
NOTE: G_list is created in place
"""
# check that indices are valid
if lower > upper:
raise ValueError(f"Wrong input to cofactor_multiples()")
# last recursion step does not need any further splitting
if upper - lower == 1:
return
# Split list in two parts,
# multiply to get new start points for the two sublists,
# and call the function recursively for both sublists.
mid = lower + (upper - lower + 1) // 2
cl, cu = 1, 1
for i in range(lower, mid):
cu = cu * pis[i]
for i in range(mid, upper):
cl = cl * pis[i]
# cl = prod(pis[lower:mid])
# cu = prod(pis[mid:upper])
G_list[mid] = group_action(G_list[lower], cu)
G_list[lower] = group_action(G_list[lower], cl)
batch_cofactor_mul_generic(G_list, pis, group_action, lower, mid)
batch_cofactor_mul_generic(G_list, pis, group_action, mid, upper)
@cached_function
def has_order_constants(D):
"""
Helper function, finds constants to
help with has_order_D
"""
D = ZZ(D)
pis = [p for p, _ in D.factor()]
D_radical = prod(pis)
Dtop = D // D_radical
return Dtop, pis
def has_order_D(G, D, multiplicative=False):
"""
Given an element G in a group, checks if the
element has order exactly D. This is much faster
than determining its order, and is enough for
many checks we need when computing the torsion
basis.
We allow both additive and multiplicative groups
which means we can use this when computing the order
of points and elements in Fp^k when checking the
multiplicative order of the Weil pairing output
"""
# For the case when we work with elements of Fp^k
if multiplicative:
group_action = lambda a, k: a**k
is_identity = lambda a: a == 1
identity = 1
# For the case when we work with elements of E / Fp^k
else:
group_action = lambda a, k: k * a
is_identity = lambda a: a.is_zero()
identity = G.curve()(0)
if is_identity(G):
return False
D_top, pis = has_order_constants(D)
# If G is the identity after clearing the top
# factors, we can abort early
Gtop = group_action(G, D_top)
if is_identity(Gtop):
return False
G_list = [identity for _ in range(len(pis))]
G_list[0] = Gtop
# Lastly we have to determine whether removing any prime
# factors of the order gives the identity of the group
if len(pis) > 1:
batch_cofactor_mul_generic(G_list, pis, group_action, 0, len(pis))
if not all([not is_identity(G) for G in G_list]):
return False
return True
|
