p3_goldilocks/
mds.rs

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

p3_goldilocks/
mds.rs
