qfall_math/integer_mod_q/z_q/arithmetic/
mul.rs

1// Copyright © 2023 Phil Milewski
2//
3// This file is part of qFALL-math.
4//
5// qFALL-math is free software: you can redistribute it and/or modify it under
6// the terms of the Mozilla Public License Version 2.0 as published by the
7// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
8
9//! Implementation of the [`Mul`] trait for [`Zq`] values.
10
11use super::super::Zq;
12use crate::{
13    error::MathError,
14    integer::Z,
15    macros::arithmetics::{
16        arithmetic_assign_between_types, arithmetic_assign_trait_borrowed_to_owned,
17        arithmetic_between_types_zq, arithmetic_trait_borrowed_to_owned,
18        arithmetic_trait_mixed_borrowed_owned,
19    },
20    traits::CompareBase,
21};
22use flint_sys::{
23    fmpz::fmpz,
24    fmpz_mod::{fmpz_mod_mul, fmpz_mod_mul_fmpz, fmpz_mod_mul_si, fmpz_mod_mul_ui},
25};
26use std::ops::{Mul, MulAssign};
27
28impl MulAssign<&Zq> for Zq {
29    /// Computes the multiplication of `self` and `other` reusing
30    /// the memory of `self`.
31    /// [`MulAssign`] can be used on [`Zq`] in combination with
32    /// [`Zq`], [`Z`], [`i64`], [`i32`], [`i16`], [`i8`], [`u64`], [`u32`], [`u16`] and [`u8`].
33    ///
34    /// Parameters:
35    /// - `other`: specifies the value to multiply to `self`
36    ///
37    /// Returns the product of both numbers modulo `q` as a [`Zq`].
38    ///
39    /// # Examples
40    /// ```
41    /// use qfall_math::{integer_mod_q::Zq, integer::Z};
42    ///
43    /// let mut a: Zq = Zq::from((23, 42));
44    /// let b: Zq = Zq::from((1, 42));
45    /// let c: Z = Z::from(5);
46    ///
47    /// a *= &b;
48    /// a *= b;
49    /// a *= 5;
50    /// a *= c;
51    /// ```
52    ///
53    /// # Panics ...
54    /// - if the moduli of both [`Zq`] mismatch.
55    fn mul_assign(&mut self, other: &Self) {
56        if !self.compare_base(other) {
57            panic!("{}", self.call_compare_base_error(other).unwrap());
58        }
59
60        unsafe {
61            fmpz_mod_mul(
62                &mut self.value.value,
63                &self.value.value,
64                &other.value.value,
65                self.modulus.get_fmpz_mod_ctx_struct(),
66            )
67        };
68    }
69}
70impl MulAssign<i64> for Zq {
71    /// Documentation at [`Zq::mul_assign`].
72    fn mul_assign(&mut self, other: i64) {
73        unsafe {
74            fmpz_mod_mul_si(
75                &mut self.value.value,
76                &self.value.value,
77                other,
78                self.modulus.get_fmpz_mod_ctx_struct(),
79            )
80        };
81    }
82}
83impl MulAssign<u64> for Zq {
84    /// Documentation at [`Zq::mul_assign`].
85    fn mul_assign(&mut self, other: u64) {
86        unsafe {
87            fmpz_mod_mul_ui(
88                &mut self.value.value,
89                &self.value.value,
90                other,
91                self.modulus.get_fmpz_mod_ctx_struct(),
92            )
93        };
94    }
95}
96impl MulAssign<&Z> for Zq {
97    /// Documentation at [`Zq::mul_assign`].
98    fn mul_assign(&mut self, other: &Z) {
99        unsafe {
100            fmpz_mod_mul_fmpz(
101                &mut self.value.value,
102                &self.value.value,
103                &other.value,
104                self.modulus.get_fmpz_mod_ctx_struct(),
105            )
106        };
107    }
108}
109
110arithmetic_assign_trait_borrowed_to_owned!(MulAssign, mul_assign, Zq, Zq);
111arithmetic_assign_trait_borrowed_to_owned!(MulAssign, mul_assign, Zq, Z);
112arithmetic_assign_between_types!(MulAssign, mul_assign, Zq, i64, i32 i16 i8);
113arithmetic_assign_between_types!(MulAssign, mul_assign, Zq, u64, u32 u16 u8);
114
115impl Mul for &Zq {
116    type Output = Zq;
117    /// Implements the [`Mul`] trait for two [`Zq`] values.
118    /// [`Mul`] is implemented for any combination of [`Zq`] and borrowed [`Zq`].
119    ///
120    /// Parameters:
121    /// - `other`: specifies the value to multiply with `self`
122    ///
123    /// Returns the product of both numbers as a [`Zq`].
124    ///
125    /// # Examples
126    /// ```
127    /// use qfall_math::integer_mod_q::Zq;
128    ///
129    /// let a: Zq = Zq::from((23, 42));
130    /// let b: Zq = Zq::from((1, 42));
131    ///
132    /// let c: Zq = &a * &b;
133    /// let d: Zq = a * b;
134    /// let e: Zq = &c * d;
135    /// let f: Zq = c * &e;
136    /// ```
137    ///
138    /// # Panics ...
139    /// - if the moduli of both [`Zq`] mismatch.
140    fn mul(self, other: Self) -> Self::Output {
141        self.mul_safe(other).unwrap()
142    }
143}
144
145impl Zq {
146    /// Implements multiplication for two [`Zq`] values.
147    ///
148    ///
149    /// Parameters:
150    /// - `other`: specifies the value to multiply with `self`
151    ///
152    /// Returns the product of both numbers as a [`Zq`] or an error if the moduli
153    /// mismatch.
154    ///
155    /// # Examples
156    /// ```
157    /// use qfall_math::integer_mod_q::Zq;
158    ///
159    /// let a: Zq = Zq::from((23, 42));
160    /// let b: Zq = Zq::from((1, 42));
161    ///
162    /// let c: Zq = a.mul_safe(&b).unwrap();
163    /// ```
164    /// # Errors
165    /// - Returns a [`MathError`] of type [`MathError::MismatchingModulus`] if the moduli of
166    ///   both [`Zq`] mismatch.
167    pub fn mul_safe(&self, other: &Self) -> Result<Zq, MathError> {
168        if !self.compare_base(other) {
169            return Err(self.call_compare_base_error(other).unwrap());
170        }
171        let mut out_z = Z::ZERO;
172        unsafe {
173            fmpz_mod_mul(
174                &mut out_z.value,
175                &self.value.value,
176                &other.value.value,
177                self.modulus.get_fmpz_mod_ctx_struct(),
178            )
179        };
180
181        Ok(Self {
182            value: out_z,
183            modulus: self.modulus.clone(),
184        })
185    }
186}
187
188arithmetic_trait_borrowed_to_owned!(Mul, mul, Zq, Zq, Zq);
189arithmetic_trait_mixed_borrowed_owned!(Mul, mul, Zq, Zq, Zq);
190
191impl Mul<&Z> for &Zq {
192    type Output = Zq;
193
194    /// Implements the [`Mul`] trait for [`Zq`] and [`Z`] values.
195    /// [`Mul`] is implemented for any combination of owned and borrowed values.
196    ///
197    /// Parameters:
198    ///  - `other`: specifies the value to multiply with `self`
199    ///
200    /// Returns the product of both numbers as a [`Zq`].
201    ///
202    /// # Examples
203    /// ```
204    /// use qfall_math::integer_mod_q::Zq;
205    /// use qfall_math::integer::Z;
206    /// use std::str::FromStr;
207    ///
208    /// let a: Zq = Zq::from((42, 19));
209    /// let b: Z = Z::from(42);
210    ///
211    /// let c: Zq = &a * &b;
212    /// let d: Zq = a * b;
213    /// let e: Zq = &c * Z::from(42);
214    /// let f: Zq = c * &Z::from(42);
215    /// ```
216    fn mul(self, other: &Z) -> Self::Output {
217        let mut out = fmpz(0);
218        unsafe {
219            fmpz_mod_mul_fmpz(
220                &mut out,
221                &self.value.value,
222                &other.value,
223                self.modulus.get_fmpz_mod_ctx_struct(),
224            );
225        }
226        Zq {
227            modulus: self.modulus.clone(),
228            value: Z { value: out },
229        }
230    }
231}
232
233arithmetic_trait_borrowed_to_owned!(Mul, mul, Zq, Z, Zq);
234arithmetic_trait_mixed_borrowed_owned!(Mul, mul, Zq, Z, Zq);
235arithmetic_between_types_zq!(Mul, mul, Zq, i64 i32 i16 i8 u64 u32 u16 u8);
236
237#[cfg(test)]
238mod test_mul_assign {
239    use crate::{integer::Z, integer_mod_q::Zq};
240
241    /// Ensure that `mul_assign` works for small numbers.
242    #[test]
243    fn correct_small() {
244        let mut a: Zq = Zq::from((-1, 7));
245        let b = Zq::from((-1, 7));
246        let c = Zq::from((0, 7));
247
248        a *= &b;
249        assert_eq!(Zq::from((1, 7)), a);
250        a *= &b;
251        assert_eq!(Zq::from((6, 7)), a);
252        a *= &c;
253        assert_eq!(Zq::from((0, 7)), a);
254    }
255
256    /// Ensure that `mul_assign` works for large numbers.
257    #[test]
258    fn correct_large() {
259        let mut a = Zq::from((i64::MAX, u64::MAX));
260        let b = Zq::from((-1, u64::MAX));
261
262        a *= &b;
263        assert_eq!(Zq::from((9223372036854775808u64, u64::MAX)), a);
264        a *= b;
265        assert_eq!(Zq::from((i64::MAX, u64::MAX)), a);
266    }
267
268    /// Ensure that `mul_assign` is available for all types.
269    #[test]
270    fn availability() {
271        let mut a = Zq::from((3, 7));
272        let b = Zq::from((1, 7));
273        let c = Z::from(1);
274
275        a *= &b;
276        a *= b;
277        a *= &c;
278        a *= c;
279        a *= 1_u8;
280        a *= 1_u16;
281        a *= 1_u32;
282        a *= 1_u64;
283        a *= 1_i8;
284        a *= 1_i16;
285        a *= 1_i32;
286        a *= 1_i64;
287    }
288
289    /// Ensures that mismatching moduli result in a panic.
290    #[test]
291    #[should_panic]
292    fn mismatching_moduli() {
293        let mut a = Zq::from((3, 7));
294        let b = Zq::from((1, 8));
295
296        a *= b;
297    }
298}
299
300#[cfg(test)]
301mod test_mul {
302    use super::Zq;
303
304    /// Testing multiplication for two [`Zq`]
305    #[test]
306    fn mul() {
307        let a: Zq = Zq::from((11, 17));
308        let b: Zq = Zq::from((12, 17));
309        let c: Zq = a * b;
310        assert_eq!(c, Zq::from((13, 17)));
311    }
312
313    /// Testing multiplication for two borrowed [`Zq`]
314    #[test]
315    fn mul_borrow() {
316        let a: Zq = Zq::from((10, 11));
317        let b: Zq = Zq::from((1, 11));
318        let c: Zq = &a * &b;
319        assert_eq!(c, Zq::from((10, 11)));
320    }
321
322    /// Testing multiplication for borrowed [`Zq`] and [`Zq`]
323    #[test]
324    fn mul_first_borrowed() {
325        let a: Zq = Zq::from((2, 11));
326        let b: Zq = Zq::from((5, 11));
327        let c: Zq = &a * b;
328        assert_eq!(c, Zq::from((10, 11)));
329    }
330
331    /// Testing multiplication for [`Zq`] and borrowed [`Zq`]
332    #[test]
333    fn mul_second_borrowed() {
334        let a: Zq = Zq::from((12, 11));
335        let b: Zq = Zq::from((10, 11));
336        let c: Zq = a * &b;
337        assert_eq!(c, Zq::from((-1, 11)));
338    }
339
340    /// Testing multiplication for large [`Zq`]
341    #[test]
342    fn mul_large_numbers() {
343        let a: Zq = Zq::from((u32::MAX, u32::MAX - 58));
344        let b: Zq = Zq::from((i32::MAX, u32::MAX - 58));
345        let c: Zq = a * b;
346        assert_eq!(
347            c,
348            Zq::from((u64::from((u32::MAX - 1) / 2) * 58, u32::MAX - 58))
349        );
350    }
351
352    /// Testing multiplication for [`Zq`] with different moduli does not work
353    #[test]
354    #[should_panic]
355    fn mul_mismatching_modulus() {
356        let a: Zq = Zq::from((4, 11));
357        let b: Zq = Zq::from((1, 3));
358        let _c: Zq = a * b;
359    }
360
361    /// Testing whether mul_safe throws an error for mismatching moduli
362    #[test]
363    fn mul_safe_is_err() {
364        let a: Zq = Zq::from((4, 11));
365        let b: Zq = Zq::from((1, 3));
366        assert!(&a.mul_safe(&b).is_err());
367    }
368}
369
370#[cfg(test)]
371mod test_mul_between_zq_and_z {
372    use super::Z;
373    use crate::integer_mod_q::Zq;
374
375    /// Testing multiplication for [`Zq`] and [`Z`]
376    #[test]
377    fn mul() {
378        let a: Zq = Zq::from((4, 11));
379        let b: Z = Z::from(9);
380        let c: Zq = a * b;
381        assert_eq!(c, Zq::from((3, 11)));
382    }
383
384    /// Testing multiplication for both borrowed [`Zq`] and [`Z`]
385    #[test]
386    fn mul_borrow() {
387        let a: Zq = Zq::from((4, 11));
388        let b: Z = Z::from(9);
389        let c: Zq = &a * &b;
390        assert_eq!(c, Zq::from((3, 11)));
391    }
392
393    /// Testing multiplication for borrowed [`Zq`] and [`Z`]
394    #[test]
395    fn mul_first_borrowed() {
396        let a: Zq = Zq::from((4, 11));
397        let b: Z = Z::from(9);
398        let c: Zq = &a * b;
399        assert_eq!(c, Zq::from((3, 11)));
400    }
401
402    /// Testing multiplication for [`Zq`] and borrowed [`Z`]
403    #[test]
404    fn mul_second_borrowed() {
405        let a: Zq = Zq::from((4, 11));
406        let b: Z = Z::from(9);
407        let c: Zq = a * &b;
408        assert_eq!(c, Zq::from((3, 11)));
409    }
410
411    /// Testing multiplication for large numbers
412    #[test]
413    fn mul_large_numbers() {
414        let a: Zq = Zq::from((i64::MAX, u64::MAX - 58));
415        let b: Zq = Zq::from((i64::MAX - 1, i64::MAX));
416        let c: Z = Z::from(u64::MAX);
417
418        let d: Zq = a * &c;
419        let e: Zq = b * c;
420
421        assert_eq!(
422            d,
423            Zq::from(((u64::MAX - 1) / 2, u64::MAX - 58)) * Zq::from((u64::MAX, u64::MAX - 58))
424        );
425        assert_eq!(e, Zq::from((-1, i64::MAX)) * Zq::from((u64::MAX, i64::MAX)));
426    }
427}
428
429#[cfg(test)]
430mod test_mul_between_types {
431    use crate::integer_mod_q::Zq;
432
433    /// Testing multiplication between different types
434    #[test]
435    #[allow(clippy::op_ref)]
436    fn mul() {
437        let a: Zq = Zq::from((4, 11));
438        let b: u64 = 1;
439        let c: u32 = 1;
440        let d: u16 = 1;
441        let e: u8 = 1;
442        let f: i64 = 1;
443        let g: i32 = 1;
444        let h: i16 = 1;
445        let i: i8 = 1;
446
447        let _: Zq = &a * &b;
448        let _: Zq = &a * &c;
449        let _: Zq = &a * &d;
450        let _: Zq = &a * &e;
451        let _: Zq = &a * &f;
452        let _: Zq = &a * &g;
453        let _: Zq = &a * &h;
454        let _: Zq = &a * &i;
455
456        let _: Zq = &b * &a;
457        let _: Zq = &c * &a;
458        let _: Zq = &d * &a;
459        let _: Zq = &e * &a;
460        let _: Zq = &f * &a;
461        let _: Zq = &g * &a;
462        let _: Zq = &h * &a;
463        let _: Zq = &i * &a;
464
465        let _: Zq = &a * b;
466        let _: Zq = &a * c;
467        let _: Zq = &a * d;
468        let _: Zq = &a * e;
469        let _: Zq = &a * f;
470        let _: Zq = &a * g;
471        let _: Zq = &a * h;
472        let _: Zq = &a * i;
473
474        let _: Zq = &b * Zq::from((4, 11));
475        let _: Zq = &c * Zq::from((4, 11));
476        let _: Zq = &d * Zq::from((4, 11));
477        let _: Zq = &e * Zq::from((4, 11));
478        let _: Zq = &f * Zq::from((4, 11));
479        let _: Zq = &g * Zq::from((4, 11));
480        let _: Zq = &h * Zq::from((4, 11));
481        let _: Zq = &i * Zq::from((4, 11));
482
483        let _: Zq = Zq::from((4, 11)) * &b;
484        let _: Zq = Zq::from((4, 11)) * &c;
485        let _: Zq = Zq::from((4, 11)) * &d;
486        let _: Zq = Zq::from((4, 11)) * &e;
487        let _: Zq = Zq::from((4, 11)) * &f;
488        let _: Zq = Zq::from((4, 11)) * &g;
489        let _: Zq = Zq::from((4, 11)) * &h;
490        let _: Zq = Zq::from((4, 11)) * &i;
491
492        let _: Zq = b * &a;
493        let _: Zq = c * &a;
494        let _: Zq = d * &a;
495        let _: Zq = e * &a;
496        let _: Zq = f * &a;
497        let _: Zq = g * &a;
498        let _: Zq = h * &a;
499        let _: Zq = i * &a;
500
501        let _: Zq = Zq::from((4, 11)) * b;
502        let _: Zq = Zq::from((4, 11)) * c;
503        let _: Zq = Zq::from((4, 11)) * d;
504        let _: Zq = Zq::from((4, 11)) * e;
505        let _: Zq = Zq::from((4, 11)) * f;
506        let _: Zq = Zq::from((4, 11)) * g;
507        let _: Zq = Zq::from((4, 11)) * h;
508        let _: Zq = Zq::from((4, 11)) * i;
509
510        let _: Zq = b * Zq::from((4, 11));
511        let _: Zq = c * Zq::from((4, 11));
512        let _: Zq = d * Zq::from((4, 11));
513        let _: Zq = e * Zq::from((4, 11));
514        let _: Zq = f * Zq::from((4, 11));
515        let _: Zq = g * Zq::from((4, 11));
516        let _: Zq = h * Zq::from((4, 11));
517        let _: Zq = i * Zq::from((4, 11));
518    }
519}
qfall_math/integer_mod_q/z_q/arithmetic/mul.rs

qfall_math/integer_mod_q/z_q/arithmetic/
mul.rs
