-
Notifications
You must be signed in to change notification settings - Fork 0
/
test_character_enumeration.py
119 lines (92 loc) · 3.89 KB
/
test_character_enumeration.py
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
118
119
"""test_character_enumeration.py
Tests for the ICE filter.
====================================================================
This file is part of Isogeny Primes.
Copyright (C) 2022 Barinder S. Banwait and Maarten Derickx
Isogeny Primes is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>.
The authors can be reached at: barinder.s.banwait@gmail.com and
maarten@mderickx.nl.
====================================================================
"""
import pytest
from sage.all import GF, NumberField, QQ
from sage.misc.misc_c import prod
from sage.rings.polynomial.polynomial_ring import polygen
from sage_code.character_enumeration import (
filter_possible_values,
lifts_in_hasse_range,
get_prime_gens,
)
@pytest.mark.parametrize(
"possible_values_list, q, e, prime, result",
[
# +/-1 and +/-q^e should always be allowed
([1, 2, -1, -2], 2, 1, 271, [1, 2, -1, -2]),
([1, 4, -1, -4], 2, 2, 271, [1, 4, -1, -4]),
# test_isogeny_character_values_12 shows these are valid
([13, 57], 11, 1, 73, [13, 57]),
],
)
def test_filter_possible_values(possible_values_list, q, e, prime, result):
prime_field = GF(prime)
possible_values_list = [prime_field(v) for v in possible_values_list]
possible_values = filter_possible_values(possible_values_list, q, e, prime_field)
assert possible_values == result
@pytest.mark.parametrize(
"fq, res_class, expected_range",
[
(11, GF(3)(0), [0, -3, -6, 3, 6]),
# make sure we include +/-2sqrt(fq) but not +/-(2sqrt(fq)+1),
(145757**2, GF(357686312646216567629137)(2 * 145757), [2 * 145757]),
(145757**2, GF(357686312646216567629137)(-2 * 145757), [-2 * 145757]),
(145757**2, GF(357686312646216567629137)(2 * 145757 + 1), []),
(145757**2, GF(357686312646216567629137)(-2 * 145757 - 1), []),
],
)
def test_lifts_in_hasse_range(fq, res_class, expected_range):
result = lifts_in_hasse_range(fq, res_class)
assert result == expected_range
x = polygen(QQ)
@pytest.mark.parametrize(
"f, q",
[
(x**2 - x + 1007, 13),
(x**2 - x + 1007, 17),
(x**2 - x + 1007, 19),
(x**2 - 11 * 17 * 9011 * 23629, 17),
(x**2 - 11 * 17 * 9011 * 23629, 47),
(x**2 - 11 * 17 * 9011 * 23629, 89),
],
)
@pytest.mark.skip(reason="Only for profiling putative faster solution")
def test_ideal_log_relation_prime_gens(f, q):
# also tests get_prime_gens
# x = polygen(QQ)
# f = x ** 2 - x + 1007
# q = 13
K = NumberField(f, "b")
C_K = K.class_group()
qq = (q * K).factor()[0][0]
prime_gens, relations = get_prime_gens(C_K)
ideal_gens = C_K.gens_ideals()
for prime, ideal, relation in zip(prime_gens, ideal_gens, relations):
assert prime * relation == ideal
exponents = C_K(qq).exponents()
t = qq.ideal_log_relation()
alpha_new = t * prod([(relation**e) for relation, e in zip(relations, exponents)])
sanity_check = prod([Q**a for Q, a in zip(prime_gens, exponents)])
assert C_K(sanity_check) == C_K(qq)
the_principal_ideal = qq * prod([Q ** (-a) for Q, a in zip(prime_gens, exponents)])
alphas = the_principal_ideal.gens_reduced()
assert len(alphas) == 1, "the principal ideal isn't principal!!!"
alpha = alphas[0]
assert alpha == alpha_new or (alpha / alpha_new).is_unit()