Loading...
Searching...
No Matches
basefield_chain3 Namespace Reference
Functions | |
| get_order3_points_fp (A_, setup) | |
| isogeny_3_mont (t, setup) | |
| to_mont (t) | |
| radical_walk3 (a, exponent, setup) | |
Function Documentation
◆ get_order3_points_fp()
| get_order3_points_fp | ( | A_, | |
| setup ) |
Definition at line 5 of file basefield_chain3.py.
5def get_order3_points_fp(A_, setup):
6 [A, C] = deepcopy(A_)
7 Fq = setup['Fp']
8 # Constants
9 one_half = 1 / Fq(2)
10 one_third = 1 / Fq(3)
11 one_ninth = one_third**2
12 one_by_27 = one_third * one_ninth
13
14 A_times_one_third = A * one_third # M𝒸
15 A_squared = A**2 # S
16 C_squared = C**2 # S
17 t = (3 * C_squared - A_squared) * one_ninth # M𝒸 + 3A
18 r = 16 * (A_squared * A) * one_by_27 # M + M𝒸 + 4A
19 s = 8 * A_times_one_third # 3A
20 u = r - s * C_squared # M + A
21
22 aux = C_squared**2 # S
23 tmp = A_squared * aux # M
24 aux = aux * C_squared # M
25 y = t + \
26 one_third * \
27 setup['curt'](-2 * tmp + 8 * aux) # M𝒸 + 3A + E
28
29 r = 2 * y # A
30 s = 6 * t # 3A
31
32 s0 = setup['sqrt'](r - s) # A + E
33 # Below assert is for sanity check (not required)
34 assert(s0**2 == (r - s))
36
37 s0_squared = s0**2 # S
38 v = -(r + s) # 2A
39 s1 = setup['sqrt'](v * s0_squared + u * s0) # 2M + A + E
40 s2 = setup['sqrt'](v * s0_squared - u * s0) # 2M + A + E
41
42 z = []
43 if s2 is None:
45 assert(s1**2 == (v * s0**2 + u * s0))
46 z.append((-s0_squared + s1) * one_half) # M𝒸 + A
47 z.append((-s0_squared - s1) * one_half) # M𝒸 + 2A
48 else:
50 assert(s2**2 == (v * s0**2 - u * s0))
51 z.append((s0_squared + s2) * one_half) # M𝒸 + A
52 z.append((s0_squared - s2) * one_half) # M𝒸 + A
53
54 num = [zk - s0*A_times_one_third for zk in z] # M + 4A
55 den = s0 * C
56
57 p = Fq.characteristic()
58
59 # Below check takes 7M + 2S
60 x = num[0]
61 y_squared = ((C * x**3) + (A * x**2 * den) + (C * den**2 * x)) * (den**3 * C)
62 if y_squared**((p - 1) // 2) != Fq(1): # E
63 num = num[::-1]
64
65
66 # Below assert is for sanity check
67 inv = 1 / den
68 x = num[0] * inv
69 coeff = A * inv * s0
70 y_squared = x**3 + coeff * x**2 + x
71 assert(y_squared**((p - 1) // 2) == Fq(1))
72
73 return num, den # Total cost: 15M + 6S + 8M𝒸 + 32A + 5E
74
assert(var1 eq var2)
References assert().
Referenced by radical_walk3().
Here is the call graph for this function:
Here is the caller graph for this function:
◆ isogeny_3_mont()
| isogeny_3_mont | ( | t, | |
| setup ) |
Definition at line 76 of file basefield_chain3.py.
76def isogeny_3_mont(t, setup):
77 # This function assumes the input and output determines an order-3
78 # point on Montgomery curves (i.e., y²= x³ + Ax² + x)
79 (r, s) = deepcopy(t)
80 r_squared = r**2
81 s_squared = s**2
82 r_cubed = r_squared * r
83 s_cubed = s_squared * s
84 aux = r * s_squared
85
86 alpha_cubed = r * (r_squared - s_squared)
87 alpha = setup['curt'](alpha_cubed)
88 assert alpha**3 == alpha_cubed
89 rd = 3 * r * alpha**2
90 rd += (3*r_squared - s_squared) * alpha
91 rd += (3*r_cubed - 2*aux)
92 return [rd, s_cubed]
93
Referenced by radical_walk3().
Here is the caller graph for this function:
◆ radical_walk3()
| radical_walk3 | ( | a, | |
| exponent, | |||
| setup ) |
Definition at line 108 of file basefield_chain3.py.
108def radical_walk3(a, exponent, setup):
109 # This function assumes the input and output determines Montgomery
110 # curves (i.e., y²= x³ + Ax² + x)
111 Fp = setup['Fp']
112 p = Fp.characteristic()
113 # scalar = Fp(127)
114 scalar = Fp.random_element()
115 while not scalar:
116 scalar = Fp.random_element()
117 num, den = get_order3_points_fp([scalar*a, scalar], setup)
118 sign = lambda x: -1 if x < 0 else (1 if x > 0 else 0)
119 choice = sign(exponent)
120 t = [num[(choice + 1) // 2], den]
121 for _ in range(0, choice * exponent, 1):
122 t = isogeny_3_mont(t, setup)
123
124 a_ = to_mont(t)
126 return a_
References assert(), get_order3_points_fp(), isogeny_3_mont(), and to_mont().
Here is the call graph for this function:
◆ to_mont()
| to_mont | ( | t | ) |
Definition at line 95 of file basefield_chain3.py.
95def to_mont(t):
96 (r, s) = deepcopy(t)
97 r_squared = r**2
98 r_at_four = r_squared**2
99 s_squared = s**2
100 s_at_four = s_squared**2
101
102 num = -3 * r_at_four - 6 * r_squared * s_squared + s_at_four
103 den = 4 * r_squared * r * s
104 a = num/den
105 return a
106
Referenced by radical_walk3().
Here is the caller graph for this function:
