p3_goldilocks/
mds.rs

Help
1//! MDS matrices over the Goldilocks field, and permutations defined by them.
2//!
3//! NB: Not all sizes have fast implementations of their permutations.
4//! Supported sizes: 8, 12, 16, 24, 32, 64, 68.
5//! Sizes 8 and 12 are from Plonky2, size 16 was found as part of concurrent
6//! work by Angus Gruen and Hamish Ivey-Law. Other sizes are from Ulrich Haböck's
7//! database.
8
9use p3_dft::Radix2Bowers;
10use p3_mds::karatsuba_convolution::Convolve;
11use p3_mds::util::{apply_circulant, apply_circulant_fft, first_row_to_first_col};
12use p3_mds::MdsPermutation;
13use p3_symmetric::Permutation;
14
15use crate::{reduce128, Goldilocks};
16
17#[derive(Clone, Debug, Default)]
18pub struct MdsMatrixGoldilocks;
19
20/// Instantiate convolution for "small" RHS vectors over Goldilocks.
21///
22/// Here "small" means N = len(rhs) <= 16 and sum(r for r in rhs) <
23/// 2^51, though in practice the sum will be less than 2^9.
24#[derive(Debug)]
25pub struct SmallConvolveGoldilocks;
26impl Convolve<Goldilocks, i128, i64, i128> for SmallConvolveGoldilocks {
27    /// Return the lift of a Goldilocks element, 0 <= input.value <= P
28    /// < 2^64. We widen immediately, since some valid Goldilocks elements
29    /// don't fit in an i64, and since in any case overflow can occur
30    /// for even the smallest convolutions.
31    #[inline(always)]
32    fn read(input: Goldilocks) -> i128 {
33        input.value as i128
34    }
35
36    /// For a convolution of size N, |x| < N * 2^64 and (as per the
37    /// assumption above), |y| < 2^51. So the product is at most N *
38    /// 2^115 which will not overflow for N <= 16. We widen `y` at
39    /// this point to perform the multiplication.
40    #[inline(always)]
41    fn parity_dot<const N: usize>(u: [i128; N], v: [i64; N]) -> i128 {
42        let mut s = 0i128;
43        for i in 0..N {
44            s += u[i] * v[i] as i128;
45        }
46        s
47    }
48
49    /// The assumptions above mean z < N^2 * 2^115, which is at most
50    /// 2^123 when N <= 16.
51    ///
52    /// NB: Even though intermediate values could be negative, the
53    /// output must be non-negative since the inputs were
54    /// non-negative.
55    #[inline(always)]
56    fn reduce(z: i128) -> Goldilocks {
57        debug_assert!(z >= 0);
58        reduce128(z as u128)
59    }
60}
61
62const FFT_ALGO: Radix2Bowers = Radix2Bowers;
63
64pub(crate) const MATRIX_CIRC_MDS_8_SML_ROW: [i64; 8] = [7, 1, 3, 8, 8, 3, 4, 9];
65
66impl Permutation<[Goldilocks; 8]> for MdsMatrixGoldilocks {
67    fn permute(&self, input: [Goldilocks; 8]) -> [Goldilocks; 8] {
68        const MATRIX_CIRC_MDS_8_SML_COL: [i64; 8] =
69            first_row_to_first_col(&MATRIX_CIRC_MDS_8_SML_ROW);
70        SmallConvolveGoldilocks::apply(
71            input,
72            MATRIX_CIRC_MDS_8_SML_COL,
73            SmallConvolveGoldilocks::conv8,
74        )
75    }
76
77    fn permute_mut(&self, input: &mut [Goldilocks; 8]) {
78        *input = self.permute(*input);
79    }
80}
81impl MdsPermutation<Goldilocks, 8> for MdsMatrixGoldilocks {}
82
83pub(crate) const MATRIX_CIRC_MDS_12_SML_ROW: [i64; 12] = [1, 1, 2, 1, 8, 9, 10, 7, 5, 9, 4, 10];
84
85impl Permutation<[Goldilocks; 12]> for MdsMatrixGoldilocks {
86    fn permute(&self, input: [Goldilocks; 12]) -> [Goldilocks; 12] {
87        const MATRIX_CIRC_MDS_12_SML_COL: [i64; 12] =
88            first_row_to_first_col(&MATRIX_CIRC_MDS_12_SML_ROW);
89        SmallConvolveGoldilocks::apply(
90            input,
91            MATRIX_CIRC_MDS_12_SML_COL,
92            SmallConvolveGoldilocks::conv12,
93        )
94    }
95
96    fn permute_mut(&self, input: &mut [Goldilocks; 12]) {
97        *input = self.permute(*input);
98    }
99}
100impl MdsPermutation<Goldilocks, 12> for MdsMatrixGoldilocks {}
101
102pub(crate) const MATRIX_CIRC_MDS_16_SML_ROW: [i64; 16] =
103    [1, 1, 51, 1, 11, 17, 2, 1, 101, 63, 15, 2, 67, 22, 13, 3];
104
105impl Permutation<[Goldilocks; 16]> for MdsMatrixGoldilocks {
106    fn permute(&self, input: [Goldilocks; 16]) -> [Goldilocks; 16] {
107        const MATRIX_CIRC_MDS_16_SML_COL: [i64; 16] =
108            first_row_to_first_col(&MATRIX_CIRC_MDS_16_SML_ROW);
109        SmallConvolveGoldilocks::apply(
110            input,
111            MATRIX_CIRC_MDS_16_SML_COL,
112            SmallConvolveGoldilocks::conv16,
113        )
114    }
115
116    fn permute_mut(&self, input: &mut [Goldilocks; 16]) {
117        *input = self.permute(*input);
118    }
119}
120impl MdsPermutation<Goldilocks, 16> for MdsMatrixGoldilocks {}
121
122#[rustfmt::skip]
123pub(crate) const MATRIX_CIRC_MDS_24_GOLDILOCKS: [u64; 24] = [
124    0x5FFFFFFFA00AAAAB, 0x24021AB75BBFE656, 0x7BE9082D73B06DF5, 0x2282863E9C3A5A62,
125    0xE0071C70DFFC71C8, 0x796CB65AB42A1A63, 0xDBBBBFFADFFDDDE3, 0x23B88EE217C5C9C2,
126    0x20030C309FFB6DB7, 0x23C3C64763BE1E1D, 0x0F93B7C9CC51362E, 0xC697A1094BD0850A,
127    0xDFFFFFFF1FFC71C8, 0xC15A4FD614950302, 0xC41D883A4C4DEDF2, 0x187879BC23C46462,
128    0x5FFCF3CEDFFE79E8, 0x1C41DF105B82398E, 0x64444003DFFDDDDA, 0x76EDDBB6F7E51F95,
129    0x1FF8E38E20038E39, 0x214139BD5C40A09D, 0x3065B7CCF3B3B621, 0x23B6F4622485CEDC,
130];
131
132impl Permutation<[Goldilocks; 24]> for MdsMatrixGoldilocks {
133    fn permute(&self, input: [Goldilocks; 24]) -> [Goldilocks; 24] {
134        apply_circulant(&MATRIX_CIRC_MDS_24_GOLDILOCKS, input)
135    }
136
137    fn permute_mut(&self, input: &mut [Goldilocks; 24]) {
138        *input = self.permute(*input);
139    }
140}
141impl MdsPermutation<Goldilocks, 24> for MdsMatrixGoldilocks {}
142
143#[rustfmt::skip]
144const MATRIX_CIRC_MDS_32_GOLDILOCKS: [u64; 32] = [
145    0x0800000000000000, 0x69249248B4924925, 0x3ABD5EAF15EAF57B, 0x294A5294739CE73A,
146    0x59E2D2CEB4B3C5A6, 0x087FBE00FF7C0220, 0xA554AA94A554AA96, 0xF00080FEFFDF8005,
147    0x64CCCCCC6666699A, 0x5B13AD8973B139D9, 0xAD4A55ACA54AD5AA, 0xDA496DA3B492DB8A,
148    0x4AD696955A5694B5, 0xA4A6B29A25B496D3, 0xA74EA162162BD3A9, 0xC698B3A5662CE98C,
149    0xA7FFFFFF55555556, 0x4AAAAAAA5AAAAAAB, 0xB047DC113DC11F71, 0x8BA2E8B99B26C9B3,
150    0xD259696C5A5B4D2E, 0xA7D540AA557EA9F6, 0x8B6E922D26DB249C, 0xFAAA805455602AAD,
151    0xCB33333266666334, 0xD13B17619B13B277, 0x45B26D9326E9374A, 0x52AB552A5AA9556B,
152    0x68ED2D2DB4B87697, 0x8B264C98A74E9D3B, 0x09EC23D83D847B09, 0x2C9A4D26669349A5,
153];
154
155impl Permutation<[Goldilocks; 32]> for MdsMatrixGoldilocks {
156    fn permute(&self, input: [Goldilocks; 32]) -> [Goldilocks; 32] {
157        const ENTRIES: [u64; 32] = first_row_to_first_col(&MATRIX_CIRC_MDS_32_GOLDILOCKS);
158        apply_circulant_fft(FFT_ALGO, ENTRIES, &input)
159    }
160
161    fn permute_mut(&self, input: &mut [Goldilocks; 32]) {
162        *input = self.permute(*input);
163    }
164}
165impl MdsPermutation<Goldilocks, 32> for MdsMatrixGoldilocks {}
166
167#[rustfmt::skip]
168const MATRIX_CIRC_MDS_64_GOLDILOCKS: [u64; 64] = [
169    0x07FFFFFFFC000000, 0xFBFFFFFF04000001, 0x436DB6DB25B6DB6E, 0x4AAAAAAA5AAAAAAB,
170    0x45B2D96C6D96CB66, 0x3BC7BC7B87BC7BC8, 0x6318C63125294A53, 0xCB3672CCCD9CB368,
171    0xB43CB5A12D68796C, 0xFBFBFBFAFBFBFBFD, 0x883DBF107B7E2210, 0x8A7689B59B629DA3,
172    0xF7FEFFDF00000001, 0x7B7C83BBC83BC47C, 0xEFF0410107EF7F83, 0x2CD8B3629CB272CA,
173    0x9800019900CCCE67, 0xFBFFFBFF07FFFC01, 0x94EC4A758C4EC628, 0xDA5A5B4A6D2D2E1F,
174    0xFFEFC080FC003FFF, 0xBC387BC2C783BC79, 0xB492DB686D24B6F3, 0x1DB6925B4B6E2477,
175    0x7801E0EF87BFFF10, 0xFC0803FAFBFC0409, 0x3780FE03C086F21C, 0x8B749B224DB22D94,
176    0x32648B36B76E9923, 0x3BC3C3C387C3C3C4, 0x79AF286B4FCA1AF3, 0x9E2762758B627628,
177    0x52AAAAAA56AAAAAB, 0xFBFFFFFEFC000001, 0xF7FFFFFF08000001, 0x2CCCCCCC9CCCCCCD,
178    0xCF286BC946BCA1B0, 0xBC483B7B883B7C49, 0xD9364D9287C1F07D, 0xAD5A94A8A95AD5AA,
179    0xFF871002C400F1E1, 0xFC03FC02FC03FC05, 0xD29495A4D6D4B4A6, 0x6C926DD1DD24DB65,
180    0x1EDC247B4DB64937, 0x7C7B843B47BC437D, 0xA55A95AAAD5AD52C, 0x4A96D5A45AD694A6,
181    0xFE6664CBCD999801, 0xFC0003FF08000401, 0x1EC4F09D64EC4D8A, 0x9E1E1D2C8B4B4A5B,
182    0xD9270937709B64DC, 0x3BB77C4448843B78, 0xFFFFFFDF03FF0021, 0x59D8761D2D8A6299,
183    0xC3496878A5E5A4B5, 0xFBF80402FC0403F9, 0x5ECD9B360E142851, 0x6D925D6429D64976,
184    0xA8AE615C19CC2B99, 0xBC44444388444445, 0xDFE3F1F81CFC7E40, 0xDA4924916D24924A,
185];
186
187impl Permutation<[Goldilocks; 64]> for MdsMatrixGoldilocks {
188    fn permute(&self, input: [Goldilocks; 64]) -> [Goldilocks; 64] {
189        const ENTRIES: [u64; 64] = first_row_to_first_col(&MATRIX_CIRC_MDS_64_GOLDILOCKS);
190        apply_circulant_fft(FFT_ALGO, ENTRIES, &input)
191    }
192
193    fn permute_mut(&self, input: &mut [Goldilocks; 64]) {
194        *input = self.permute(*input);
195    }
196}
197impl MdsPermutation<Goldilocks, 64> for MdsMatrixGoldilocks {}
198
199#[rustfmt::skip]
200const MATRIX_CIRC_MDS_68_GOLDILOCKS: [u64; 68] = [
201    0x03C3C3C3FC3C3C3C, 0x6799AFC54A69BC7D, 0xDA8C2C496A74B03B, 0x1E641D7AB35ED229,
202    0x9239DA20DA3A2686, 0x6E23D41459EBA8C4, 0x7BC412896E2A6B3A, 0x9082059089ABD4FC,
203    0x94A16FA8B0339EEE, 0x85650EC91BB519C9, 0x1600745267E94DE1, 0xFFFD8405C82020AB,
204    0x21BDE80429DCED6A, 0x8ACE123AF754E343, 0xFFC7211605D2BDAE, 0xC21187AE15900F4D,
205    0x9C4A889708568DC6, 0x65A5A726B5758D8E, 0x949DB90B9AC0D11A, 0x23B6CF7C368BBE52,
206    0xD5128DDF59CB5A35, 0xF53BCC5BDADF3A0A, 0xBA7C5112F4BAB1CD, 0x4B93989C5B729351,
207    0x6534B7E50E4AD1CB, 0x640061B54C918405, 0x0E66E1F90D2C9311, 0x31C8649B0FE7557F,
208    0x0E9190D165F4A8F3, 0x52DF336BB708F919, 0x3C0F6697F14065A5, 0xBE8190942EC50031,
209    0x60038E9ACC701118, 0x73F105909A55A88B, 0xFEBEBEBDABEBEBED, 0x6F52163A64B03467,
210    0xFBAE131F23A12F56, 0x1950493BC70D0676, 0x2886550DB5A1BBBF, 0x15B003D6E58181D7,
211    0x3A4E7D9D44F100F8, 0x6CC3AB896025E6A0, 0x7E23E68456F825E5, 0x079CDD570B591A16,
212    0xEC15A830C3D2CCD1, 0xCF4C722D2C0F8A0E, 0xC1BB6F5591B59A26, 0xB63A5931A607BDE0,
213    0x43A0AD0B71040187, 0x7E4B492889D1CEE0, 0x734153F3F0C31C5B, 0x98D8D756B2725A5B,
214    0x5589D20D74BA00B8, 0xB2DF58DF0A312509, 0xFABC378690D64A3A, 0x700640AFC244B695,
215    0xFFA652236547F3BE, 0x2B9CA498A001D059, 0x7DACA6F16787D5DE, 0xAAAD774FAC613EA3,
216    0xA88583816975CD56, 0x78B71DC516FF49CA, 0xC7BF095DF702FFA6, 0x78A60B3F971783B3,
217    0xCB158EF40BC75CAC, 0xA97E818DBC152B4C, 0x9FC8339D415C3999, 0x006A88C0A0D8201C,
218];
219
220impl Permutation<[Goldilocks; 68]> for MdsMatrixGoldilocks {
221    fn permute(&self, input: [Goldilocks; 68]) -> [Goldilocks; 68] {
222        apply_circulant(&MATRIX_CIRC_MDS_68_GOLDILOCKS, input)
223    }
224
225    fn permute_mut(&self, input: &mut [Goldilocks; 68]) {
226        *input = self.permute(*input);
227    }
228}
229impl MdsPermutation<Goldilocks, 68> for MdsMatrixGoldilocks {}
230
231#[cfg(test)]
232mod tests {
233    use p3_symmetric::Permutation;
234
235    use super::{Goldilocks, MdsMatrixGoldilocks};
236
237    #[test]
238    fn goldilocks8() {
239        let input: [Goldilocks; 8] = Goldilocks::new_array([
240            2434589605738284713,
241            4817685620989478889,
242            13397079175138649456,
243            11944520631108649751,
244            1033251468644039632,
245            3092099742268329866,
246            7160548811622790454,
247            9959569614427134344,
248        ]);
249
250        let output = MdsMatrixGoldilocks.permute(input);
251
252        let expected: [Goldilocks; 8] = Goldilocks::new_array([
253            16726687146516531007,
254            14721040752765534861,
255            15566838577475948790,
256            9095485010737904250,
257            11353934351835864222,
258            11056556168691087893,
259            4199602889124860181,
260            315643510993921470,
261        ]);
262
263        assert_eq!(output, expected);
264    }
265
266    #[test]
267    fn goldilocks12() {
268        let input: [Goldilocks; 12] = Goldilocks::new_array([
269            14847187883725400244,
270            969392934980971521,
271            6996647758016470432,
272            4674844440624672154,
273            264841656685969785,
274            1246852265697711623,
275            18223868478428473484,
276            12122736699239070772,
277            11263701854732819430,
278            12739925508864285577,
279            11648637570857932167,
280            14090978315217600393,
281        ]);
282
283        let output = MdsMatrixGoldilocks.permute(input);
284
285        let expected: [Goldilocks; 12] = Goldilocks::new_array([
286            9322351889214742299,
287            8700136572060418355,
288            4881757876459003977,
289            9899544690241851021,
290            480548822895830465,
291            5445915149371405525,
292            14955363277757168581,
293            6672733082273363313,
294            190938676320003294,
295            1613225933948270736,
296            3549006224849989171,
297            12169032187873197425,
298        ]);
299
300        assert_eq!(output, expected);
301    }
302
303    #[test]
304    fn goldilocks16() {
305        let input: [Goldilocks; 16] = Goldilocks::new_array([
306            13216135600341032847,
307            15626390207663319651,
308            2052474569300149934,
309            4375663431730581786,
310            16596827905941257435,
311            10019626608444427271,
312            7831946179065963230,
313            17104499871144693506,
314            9021930732511690478,
315            6899419210615882449,
316            8131182521761419514,
317            432489675596019804,
318            8508050013409958723,
319            14134506582804571789,
320            13283546413390931641,
321            14711125975653831032,
322        ]);
323
324        let output = MdsMatrixGoldilocks.permute(input);
325
326        let expected: [Goldilocks; 16] = Goldilocks::new_array([
327            9484392671298797780,
328            149770626972189150,
329            12125722600598304117,
330            15945232149672903756,
331            13199929870021500593,
332            18443980893262804946,
333            317150800081307627,
334            16910019239751125049,
335            1996802739033818490,
336            11668458913264624237,
337            11078800762167869397,
338            13758408662406282356,
339            11119677412113674380,
340            7344117715971661026,
341            4202436890275702092,
342            681166793519210465,
343        ]);
344
345        assert_eq!(output, expected);
346    }
347
348    #[test]
349    fn goldilocks24() {
350        let input: [Goldilocks; 24] = Goldilocks::new_array([
351            11426771245122339662,
352            5975488243963332229,
353            11441424994503305651,
354            5755561333702259678,
355            7295454168648181339,
356            16724279929816174064,
357            32359231037136391,
358            3713621595270370753,
359            8421765959140936778,
360            12370571593326246544,
361            8633733294559731287,
362            12765436832373161027,
363            15606692828890413034,
364            8068160018166226874,
365            10719661629577139538,
366            13036735610140127982,
367            10213543772818211674,
368            8041886705706266368,
369            12022983417703446028,
370            4179370708601587579,
371            11125302089484330465,
372            9904943018174649533,
373            16178194376951442671,
374            1545799842160818502,
375        ]);
376
377        let output = MdsMatrixGoldilocks.permute(input);
378
379        let expected: [Goldilocks; 24] = Goldilocks::new_array([
380            18431075688485197060,
381            14823984346528185622,
382            7262979358411339215,
383            14816911393874702213,
384            6721523710303409972,
385            10829861327716364029,
386            2456948878733883601,
387            11088379938350287658,
388            3820735023521527858,
389            9062288923770492958,
390            5159244568306327366,
391            1401669669887165869,
392            11908734248351870182,
393            10640195377186320543,
394            6552733980894593378,
395            17103376282032495459,
396            5204287788603805758,
397            17783185518697631139,
398            9006863878586007300,
399            11122535637762904803,
400            5271621316102699962,
401            9734499541452484536,
402            11778274360927642637,
403            3217831681350496533,
404        ]);
405
406        assert_eq!(output, expected);
407    }
408
409    #[test]
410    fn goldilocks32() {
411        let input: [Goldilocks; 32] = Goldilocks::new_array([
412            8401806579759049284,
413            14709608922272986544,
414            8130995604641968478,
415            7833133203357642391,
416            10700492548100684406,
417            3941105252506602047,
418            8122370916776133262,
419            15079919378435648206,
420            8774521769784086994,
421            16794844316583392853,
422            9356562741425567167,
423            13317198313361936216,
424            7187680218428599522,
425            16525662096158660997,
426            540453741156061014,
427            16543585577270698663,
428            3802215918136285729,
429            11389297895303247764,
430            5133769394766075512,
431            1057795099426170863,
432            18037861421172314665,
433            17632255188776359310,
434            17616515088477043142,
435            13307921676744533876,
436            17602277262015191215,
437            15819040654617566738,
438            11961318546000835928,
439            15593174310433874065,
440            9152657050882549004,
441            4801868480369948110,
442            13202076339494141066,
443            726396847460932316,
444        ]);
445
446        let output = MdsMatrixGoldilocks.permute(input);
447
448        let expected: [Goldilocks; 32] = Goldilocks::new_array([
449            1179701925859507209,
450            5543239597787055637,
451            5978278622530964070,
452            3622388166841103287,
453            11383243182536830899,
454            14719109850604985734,
455            17672601866826623850,
456            4879627080283827596,
457            7556887460241466109,
458            9548493506061808122,
459            13980851986825291174,
460            2029844508485082398,
461            10375517623784134775,
462            13067093881736606569,
463            6446569064196467795,
464            15375603814779462714,
465            11307946648742033371,
466            1593906954637160608,
467            5776169226282316678,
468            8167048017892669861,
469            3954052226208277367,
470            9346878497567392707,
471            5570872870988220142,
472            10792661164389799960,
473            17494962593174487938,
474            7080549557843445752,
475            14059834522311268132,
476            17747288366997773235,
477            17158122400620315305,
478            6816598002359267850,
479            12363049840026116993,
480            13313901185845854868,
481        ]);
482
483        assert_eq!(output, expected);
484    }
485
486    #[test]
487    fn goldilocks64() {
488        let input: [Goldilocks; 64] = Goldilocks::new_array([
489            3471075506106776899,
490            4817046918282259009,
491            3480368692354016145,
492            18110937755057600106,
493            3130862083451221140,
494            15376650156021437015,
495            7997596749112997445,
496            7742916918728590149,
497            421644639408377358,
498            2491271421424548020,
499            1940196613872160755,
500            7152053147988203177,
501            13697425352450853423,
502            15877844788345672674,
503            17787098720906653510,
504            6857627524724866519,
505            8541180216786820396,
506            10769715704553877654,
507            9265712399189924160,
508            10220120296438955872,
509            18201417281995610945,
510            6749698931189855822,
511            13700000989116811950,
512            13205437213697578097,
513            10514342943989454609,
514            9926015350795325725,
515            2289808224483690257,
516            12598806357998460973,
517            14393945610969324307,
518            4744625557965362093,
519            2270701163031951561,
520            2927942398784334090,
521            5250916386894733430,
522            4030189910566345872,
523            4953663590324639075,
524            1241519685782896035,
525            8681312160951359069,
526            8236353015475387411,
527            4972690458759871996,
528            1396852754187463352,
529            17512022752774329733,
530            14009268822557836700,
531            1346736409027879377,
532            7609463340861239931,
533            10701512803758419515,
534            5067199073587389986,
535            5030018986055211116,
536            17692625804700013551,
537            9992938630604785132,
538            15350127009762647067,
539            10247405821493235386,
540            15172888833500531069,
541            14657693742399622179,
542            7391511805216089127,
543            2035742693690795598,
544            4047216012963057952,
545            12602085105939403203,
546            16985723692990258059,
547            12141021186082151434,
548            3174646196626212833,
549            16484520987666295947,
550            10579720164460442970,
551            9596917135039689219,
552            13761818390665814258,
553        ]);
554
555        let output = MdsMatrixGoldilocks.permute(input);
556
557        let expected: [Goldilocks; 64] = Goldilocks::new_array([
558            9158798369861934356,
559            9224859686427886689,
560            16948559910286211274,
561            15765762765140902574,
562            16202509467561200764,
563            1911749439284071529,
564            4607026757869726805,
565            8473827004973131317,
566            13716800466551879373,
567            6670177022201597800,
568            17416833238376299449,
569            14953676562252669578,
570            5828107070718286209,
571            17980287408679531241,
572            2220583438808757820,
573            14564318040622847100,
574            3950519594558514416,
575            12164610170526828198,
576            457385640833960098,
577            14068973922383216628,
578            9614382247226943793,
579            3932756878771319222,
580            12728498054939249570,
581            9435109056498897661,
582            7283114805836756402,
583            1720178259138435097,
584            11496602000538177285,
585            7736206812858942065,
586            14289784438950643645,
587            12052665489155550962,
588            12918409840610303255,
589            5224324424989208352,
590            7826309014606327907,
591            11657314889847733528,
592            13899641072303006348,
593            7501780959676548477,
594            1064261716045449147,
595            1487682458939665452,
596            10894217148983862136,
597            12785338167343566981,
598            8043323074629160032,
599            10852328074701301213,
600            15029722608724150267,
601            2611937278660861263,
602            13995790409949796943,
603            7103138700054564899,
604            12756778219044204581,
605            4147399997707606088,
606            11930966590061754579,
607            16708700985380478903,
608            2370160521342035603,
609            14893791582608133454,
610            15313288276425450946,
611            16224601303711716386,
612            4488931442519177087,
613            7443169181907410918,
614            12381442753785370161,
615            16366345507676500076,
616            8097905256807642731,
617            8504207502183388457,
618            11400931328719780407,
619            10879211614969476303,
620            7265889003783205111,
621            7322738272300165489,
622        ]);
623
624        assert_eq!(output, expected);
625    }
626
627    #[test]
628    fn goldilocks68() {
629        let input: [Goldilocks; 68] = Goldilocks::new_array([
630            16450563043143968653,
631            3688080826640678185,
632            133253417037384537,
633            17501558583799613353,
634            14920674569425704293,
635            5030578721963251055,
636            9795600398273758687,
637            402012644192671817,
638            10657312189068414445,
639            9508835336085746575,
640            16081669758721272608,
641            2072823794278273547,
642            16831381326702573736,
643            11381683312293543190,
644            5679539322738625588,
645            9346499485038639332,
646            15554202803455984983,
647            18373955571490331663,
648            11323895584334729789,
649            16834542679468148445,
650            14751528164286075953,
651            3755158780970327991,
652            12622814707645103582,
653            10329238611694882547,
654            7642766530280843057,
655            4876120096290984742,
656            412912224820604426,
657            9118233770240274553,
658            3626520971021993076,
659            10841049054903806738,
660            18205546599950141835,
661            7198482606375262809,
662            17183313930831625294,
663            10181033256431249241,
664            1061211413812819905,
665            3980261141891682525,
666            5674176959446948353,
667            6062696542969845681,
668            3383081006315025715,
669            8812665902421024067,
670            3093645099818246186,
671            16178737149039707082,
672            8204245222345541411,
673            11072582337937050490,
674            17969785901925882398,
675            4670890092981706609,
676            12537558683977529426,
677            12084598516323376868,
678            16293685096019175644,
679            10117612240421467846,
680            17873102395739074620,
681            11220493906741851877,
682            4632957003022201019,
683            12934229307704669322,
684            2152792796882257594,
685            12521131928134126701,
686            17472006670677761650,
687            4560570065837283016,
688            6315543803073912887,
689            4098689719955359793,
690            1784883877365258237,
691            6837590090927294950,
692            2391417016765166652,
693            16389291664603960875,
694            12285946887702044436,
695            7231705445010258971,
696            12976071926225281356,
697            8829402645443096358,
698        ]);
699
700        let output = MdsMatrixGoldilocks.permute(input);
701
702        let expected: [Goldilocks; 68] = Goldilocks::new_array([
703            4984914285749049383,
704            10397959071664799177,
705            3331616814639908945,
706            4252459885611162121,
707            5517786723806029201,
708            1826620401370703815,
709            8257849352373689773,
710            1722805960790112693,
711            17654983138917187833,
712            7542660006721409612,
713            1970182718241277021,
714            12865815507550811641,
715            17507096607056552658,
716            7988714902687660369,
717            150082662759625574,
718            17329095993317360383,
719            965880604543562997,
720            2820931239306841741,
721            1980667983336380501,
722            3781794112174728826,
723            7323192150179872391,
724            12243426826276589932,
725            315076483410634889,
726            3221894784246078707,
727            3515955216509190252,
728            964376148920419876,
729            7679719864273407732,
730            2516714701741920303,
731            4837221266652621366,
732            15301563603415983061,
733            10380321314559647625,
734            3023678426639670063,
735            12020917879204725519,
736            10595808165609787680,
737            14199186729378048831,
738            4520610719509879248,
739            9983949546821718635,
740            5066092593424854949,
741            13843503196305181790,
742            14296362815835302652,
743            6766348697864530153,
744            13804582129741554661,
745            8032169955336281598,
746            5198513488794721460,
747            10613667919514788349,
748            7948289550930596506,
749            14118391408956101449,
750            4356952068887595371,
751            709878153008378134,
752            17168579964784489802,
753            17840495726541494819,
754            2710471020841761312,
755            9950159372116756450,
756            3909574932971200058,
757            2430964021804554670,
758            6035162446515244642,
759            14656543530572478095,
760            1539013407173403800,
761            4150113154618904744,
762            4904646199269229662,
763            17257014030727492672,
764            3791823431764085889,
765            13680668409434600948,
766            12367427987617118934,
767            12462908457168650050,
768            10891613749697412017,
769            6867760775372053830,
770            12474954319307005079,
771        ]);
772
773        assert_eq!(output, expected);
774    }
775}
p3_goldilocks/mds.rs

p3_goldilocks/
mds.rs
