1const std = @import("std");
2const crypto = std.crypto;
3const debug = std.debug;
4const mem = std.mem;
5
6const NonCanonicalError = crypto.errors.NonCanonicalError;
7const NotSquareError = crypto.errors.NotSquareError;
8
9/// Parameters to create a finite field type.
10pub const FieldParams = struct {
11 fiat: type,
12 field_order: comptime_int,
13 field_bits: comptime_int,
14 saturated_bits: comptime_int,
15 encoded_length: comptime_int,
16};
17
18/// A field element, internally stored in Montgomery domain.
19pub fn Field(comptime params: FieldParams) type {
20 const fiat = params.fiat;
21 const MontgomeryDomainFieldElement = fiat.MontgomeryDomainFieldElement;
22 const NonMontgomeryDomainFieldElement = fiat.NonMontgomeryDomainFieldElement;
23
24 return struct {
25 const Fe = @This();
26
27 limbs: MontgomeryDomainFieldElement,
28
29 /// Field size.
30 pub const field_order = params.field_order;
31
32 /// Number of bits to represent the set of all elements.
33 pub const field_bits = params.field_bits;
34
35 /// Number of bits that can be saturated without overflowing.
36 pub const saturated_bits = params.saturated_bits;
37
38 /// Number of bytes required to encode an element.
39 pub const encoded_length = params.encoded_length;
40
41 /// Zero.
42 pub const zero: Fe = Fe{ .limbs = mem.zeroes(MontgomeryDomainFieldElement) };
43
44 /// One.
45 pub const one = one: {
46 var fe: Fe = undefined;
47 fiat.setOne(&fe.limbs);
48 break :one fe;
49 };
50
51 /// Reject non-canonical encodings of an element.
52 pub fn rejectNonCanonical(s_: [encoded_length]u8, endian: std.builtin.Endian) NonCanonicalError!void {
53 var s = if (endian == .little) s_ else orderSwap(s_);
54 const field_order_s = comptime fos: {
55 var fos: [encoded_length]u8 = undefined;
56 mem.writeInt(@Int(.unsigned, encoded_length * 8), &fos, field_order, .little);
57 break :fos fos;
58 };
59 if (crypto.timing_safe.compare(u8, &s, &field_order_s, .little) != .lt) {
60 return error.NonCanonical;
61 }
62 }
63
64 /// Swap the endianness of an encoded element.
65 pub fn orderSwap(s: [encoded_length]u8) [encoded_length]u8 {
66 var t = s;
67 for (s, 0..) |x, i| t[t.len - 1 - i] = x;
68 return t;
69 }
70
71 /// Unpack a field element.
72 pub fn fromBytes(s_: [encoded_length]u8, endian: std.builtin.Endian) NonCanonicalError!Fe {
73 const s = if (endian == .little) s_ else orderSwap(s_);
74 try rejectNonCanonical(s, .little);
75 var limbs_z: NonMontgomeryDomainFieldElement = undefined;
76 fiat.fromBytes(&limbs_z, s);
77 var limbs: MontgomeryDomainFieldElement = undefined;
78 fiat.toMontgomery(&limbs, limbs_z);
79 return Fe{ .limbs = limbs };
80 }
81
82 /// Pack a field element.
83 pub fn toBytes(fe: Fe, endian: std.builtin.Endian) [encoded_length]u8 {
84 var limbs_z: NonMontgomeryDomainFieldElement = undefined;
85 fiat.fromMontgomery(&limbs_z, fe.limbs);
86 var s: [encoded_length]u8 = undefined;
87 fiat.toBytes(&s, limbs_z);
88 return if (endian == .little) s else orderSwap(s);
89 }
90
91 /// Element as an integer.
92 pub const IntRepr = @Int(.unsigned, params.field_bits);
93
94 /// Create a field element from an integer.
95 pub fn fromInt(comptime x: IntRepr) NonCanonicalError!Fe {
96 var s: [encoded_length]u8 = undefined;
97 mem.writeInt(IntRepr, &s, x, .little);
98 return fromBytes(s, .little);
99 }
100
101 /// Return the field element as an integer.
102 pub fn toInt(fe: Fe) IntRepr {
103 const s = fe.toBytes(.little);
104 return mem.readInt(IntRepr, &s, .little);
105 }
106
107 /// Return true if the field element is zero.
108 pub fn isZero(fe: Fe) bool {
109 var z: @TypeOf(fe.limbs[0]) = undefined;
110 fiat.nonzero(&z, fe.limbs);
111 return z == 0;
112 }
113
114 /// Return true if both field elements are equivalent.
115 pub fn equivalent(a: Fe, b: Fe) bool {
116 return a.sub(b).isZero();
117 }
118
119 /// Return true if the element is odd.
120 pub fn isOdd(fe: Fe) bool {
121 const s = fe.toBytes(.little);
122 return @as(u1, @truncate(s[0])) != 0;
123 }
124
125 /// Conditonally replace a field element with `a` if `c` is positive.
126 pub fn cMov(fe: *Fe, a: Fe, c: u1) void {
127 fiat.selectznz(&fe.limbs, c, fe.limbs, a.limbs);
128 }
129
130 /// Add field elements.
131 pub fn add(a: Fe, b: Fe) Fe {
132 var fe: Fe = undefined;
133 fiat.add(&fe.limbs, a.limbs, b.limbs);
134 return fe;
135 }
136
137 /// Subtract field elements.
138 pub fn sub(a: Fe, b: Fe) Fe {
139 var fe: Fe = undefined;
140 fiat.sub(&fe.limbs, a.limbs, b.limbs);
141 return fe;
142 }
143
144 /// Double a field element.
145 pub fn dbl(a: Fe) Fe {
146 var fe: Fe = undefined;
147 fiat.add(&fe.limbs, a.limbs, a.limbs);
148 return fe;
149 }
150
151 /// Multiply field elements.
152 pub fn mul(a: Fe, b: Fe) Fe {
153 var fe: Fe = undefined;
154 fiat.mul(&fe.limbs, a.limbs, b.limbs);
155 return fe;
156 }
157
158 /// Square a field element.
159 pub fn sq(a: Fe) Fe {
160 var fe: Fe = undefined;
161 fiat.square(&fe.limbs, a.limbs);
162 return fe;
163 }
164
165 /// Square a field element n times.
166 fn sqn(a: Fe, comptime n: comptime_int) Fe {
167 var i: usize = 0;
168 var fe = a;
169 while (i < n) : (i += 1) {
170 fe = fe.sq();
171 }
172 return fe;
173 }
174
175 /// Compute a^n.
176 pub fn pow(a: Fe, comptime T: type, comptime n: T) Fe {
177 var fe = one;
178 var x: T = n;
179 var t = a;
180 while (true) {
181 if (@as(u1, @truncate(x)) != 0) fe = fe.mul(t);
182 x >>= 1;
183 if (x == 0) break;
184 t = t.sq();
185 }
186 return fe;
187 }
188
189 /// Negate a field element.
190 pub fn neg(a: Fe) Fe {
191 var fe: Fe = undefined;
192 fiat.opp(&fe.limbs, a.limbs);
193 return fe;
194 }
195
196 /// Return the inverse of a field element, or 0 if a=0.
197 // Field inversion from https://eprint.iacr.org/2021/549.pdf
198 pub fn invert(a: Fe) Fe {
199 const iterations = (49 * field_bits + if (field_bits < 46) 80 else 57) / 17;
200 const Limbs = @TypeOf(a.limbs);
201 const Word = @TypeOf(a.limbs[0]);
202 const XLimbs = [a.limbs.len + 1]Word;
203
204 var d: Word = 1;
205 var f = comptime blk: {
206 var f: XLimbs = undefined;
207 fiat.msat(&f);
208 break :blk f;
209 };
210 var g: XLimbs = undefined;
211 fiat.fromMontgomery(g[0..a.limbs.len], a.limbs);
212 g[g.len - 1] = 0;
213
214 var r = Fe.one.limbs;
215 var v = Fe.zero.limbs;
216
217 var out1: Word = undefined;
218 var out2: XLimbs = undefined;
219 var out3: XLimbs = undefined;
220 var out4: Limbs = undefined;
221 var out5: Limbs = undefined;
222
223 var i: usize = 0;
224 while (i < iterations - iterations % 2) : (i += 2) {
225 fiat.divstep(&out1, &out2, &out3, &out4, &out5, d, f, g, v, r);
226 fiat.divstep(&d, &f, &g, &v, &r, out1, out2, out3, out4, out5);
227 }
228 if (iterations % 2 != 0) {
229 fiat.divstep(&out1, &out2, &out3, &out4, &out5, d, f, g, v, r);
230 v = out4;
231 f = out2;
232 }
233 var v_opp: Limbs = undefined;
234 fiat.opp(&v_opp, v);
235 fiat.selectznz(&v, @as(u1, @truncate(f[f.len - 1] >> (@bitSizeOf(Word) - 1))), v, v_opp);
236
237 const precomp = blk: {
238 var precomp: Limbs = undefined;
239 fiat.divstepPrecomp(&precomp);
240 break :blk precomp;
241 };
242 var fe: Fe = undefined;
243 fiat.mul(&fe.limbs, v, precomp);
244 return fe;
245 }
246
247 /// Return true if the field element is a square.
248 pub fn isSquare(x2: Fe) bool {
249 if (field_order == 115792089210356248762697446949407573530086143415290314195533631308867097853951) {
250 const t110 = x2.mul(x2.sq()).sq();
251 const t111 = x2.mul(t110);
252 const t111111 = t111.mul(x2.mul(t110).sqn(3));
253 const x15 = t111111.sqn(6).mul(t111111).sqn(3).mul(t111);
254 const x16 = x15.sq().mul(x2);
255 const x53 = x16.sqn(16).mul(x16).sqn(15);
256 const x47 = x15.mul(x53);
257 const ls = x47.mul(((x53.sqn(17).mul(x2)).sqn(143).mul(x47)).sqn(47)).sq().mul(x2);
258 return ls.equivalent(Fe.one);
259 } else if (field_order == 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319) {
260 const t111 = x2.mul(x2.mul(x2.sq()).sq());
261 const t111111 = t111.mul(t111.sqn(3));
262 const t1111110 = t111111.sq();
263 const t1111111 = x2.mul(t1111110);
264 const x12 = t1111110.sqn(5).mul(t111111);
265 const x31 = x12.sqn(12).mul(x12).sqn(7).mul(t1111111);
266 const x32 = x31.sq().mul(x2);
267 const x63 = x32.sqn(31).mul(x31);
268 const x126 = x63.sqn(63).mul(x63);
269 const ls = x126.sqn(126).mul(x126).sqn(3).mul(t111).sqn(33).mul(x32).sqn(95).mul(x31);
270 return ls.equivalent(Fe.one);
271 } else {
272 const ls = x2.pow(@Int(.unsigned, field_bits), (field_order - 1) / 2); // Legendre symbol
273 return ls.equivalent(Fe.one);
274 }
275 }
276
277 // x=x2^((field_order+1)/4) w/ field order=3 (mod 4).
278 fn uncheckedSqrt(x2: Fe) Fe {
279 if (field_order % 4 != 3) @compileError("unimplemented");
280 if (field_order == 115792089210356248762697446949407573530086143415290314195533631308867097853951) {
281 const t11 = x2.mul(x2.sq());
282 const t1111 = t11.mul(t11.sqn(2));
283 const t11111111 = t1111.mul(t1111.sqn(4));
284 const x16 = t11111111.sqn(8).mul(t11111111);
285 return x16.sqn(16).mul(x16).sqn(32).mul(x2).sqn(96).mul(x2).sqn(94);
286 } else if (field_order == 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319) {
287 const t111 = x2.mul(x2.mul(x2.sq()).sq());
288 const t111111 = t111.mul(t111.sqn(3));
289 const t1111110 = t111111.sq();
290 const t1111111 = x2.mul(t1111110);
291 const x12 = t1111110.sqn(5).mul(t111111);
292 const x31 = x12.sqn(12).mul(x12).sqn(7).mul(t1111111);
293 const x32 = x31.sq().mul(x2);
294 const x63 = x32.sqn(31).mul(x31);
295 const x126 = x63.sqn(63).mul(x63);
296 return x126.sqn(126).mul(x126).sqn(3).mul(t111).sqn(33).mul(x32).sqn(64).mul(x2).sqn(30);
297 } else if (field_order == 115792089237316195423570985008687907853269984665640564039457584007908834671663) {
298 const t11 = x2.mul(x2.sq());
299 const t1111 = t11.mul(t11.sqn(2));
300 const t11111 = x2.mul(t1111.sq());
301 const t1111111 = t11.mul(t11111.sqn(2));
302 const x11 = t1111111.sqn(4).mul(t1111);
303 const x22 = x11.sqn(11).mul(x11);
304 const x27 = x22.sqn(5).mul(t11111);
305 const x54 = x27.sqn(27).mul(x27);
306 const x108 = x54.sqn(54).mul(x54);
307 return x108.sqn(108).mul(x108).sqn(7).mul(t1111111).sqn(23).mul(x22).sqn(6).mul(t11).sqn(2);
308 } else {
309 return x2.pow(@Int(.unsigned, field_bits), (field_order + 1) / 4);
310 }
311 }
312
313 /// Compute the square root of `x2`, returning `error.NotSquare` if `x2` was not a square.
314 pub fn sqrt(x2: Fe) NotSquareError!Fe {
315 const x = x2.uncheckedSqrt();
316 if (x.sq().equivalent(x2)) {
317 return x;
318 }
319 return error.NotSquare;
320 }
321 };
322}