qfall-math 0.1.1

Mathematical foundations for rapid prototyping of lattice-based cryptography
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

// Copyright © 2023 Niklas Siemer
//
// This file is part of qFALL-math.
//
// qFALL-math is free software: you can redistribute it and/or modify it under
// the terms of the Mozilla Public License Version 2.0 as published by the
// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.

//! This module provides an implementation of the [`Pow`] trait for [`Zq`].

use crate::{error::MathError, integer::Z, integer_mod_q::Zq, traits::Pow};
use flint_sys::fmpz_mod::fmpz_mod_pow_fmpz;

impl<Integer: Into<Z>> Pow<Integer> for Zq {
    type Output = Zq;

    /// Raises the value of `self` to the power of an integer `exp`.
    ///
    /// Parameters:
    /// - `exp`: specifies the exponent to which the value is raised
    ///
    /// Returns the value of `self` powered by `exp` as a new `Output` instance
    /// or an error if the exponent is negative and the base value of `self` is not invertible.
    ///
    /// # Examples
    /// ```
    /// use qfall_math::integer::Z;
    /// use qfall_math::integer_mod_q::Zq;
    /// use qfall_math::traits::*;
    ///
    /// let base = Zq::from((2, 9));
    ///
    /// let powered_value = base.pow(4).unwrap();
    ///
    /// let cmp = Zq::from((7, 9));
    /// assert_eq!(cmp, powered_value);
    /// ```
    ///
    /// # Errors and Failures
    /// - Returns a [`MathError`] of type [`InvalidExponent`](MathError::InvalidExponent)
    ///   if the provided exponent is negative and the base value of `self` is not invertible.
    fn pow(&self, exp: Integer) -> Result<Self::Output, MathError> {
        let exp = exp.into();
        let mut out = self.clone();
        if 0 == unsafe {
            fmpz_mod_pow_fmpz(
                &mut out.value.value,
                &self.value.value,
                &exp.value,
                self.modulus.get_fmpz_mod_ctx_struct(),
            )
        } {
            return Err(MathError::InvalidExponent(format!(
                "The negative exponent {exp} was used for a non-invertible base {self}"
            )));
        }
        Ok(out)
    }
}

#[cfg(test)]
mod test_pow {
    use super::*;

    /// Ensure that `pow` works for [`Zq`] properly for small values
    #[test]
    fn small() {
        let base = Zq::from((2, 9));
        let exp_0 = Z::from(4);
        let exp_1 = Z::ZERO;
        let exp_2 = Z::from(-2);

        let res_0 = base.pow(&exp_0).unwrap();
        let res_1 = base.pow(&exp_1).unwrap();
        let res_2 = base.pow(&exp_2).unwrap();

        assert_eq!(Zq::from((7, 9)), res_0);
        assert_eq!(Zq::from((1, 9)), res_1);
        assert_eq!(Zq::from((7, 9)), res_2);
    }

    /// Ensure that `pow` works for [`Zq`] properly for large values
    #[test]
    fn large() {
        let base = Zq::from((i64::MAX, u64::MAX));
        let exp_0 = Z::from(4);
        let exp_1 = Z::ZERO;
        let exp_2 = Z::from(-1);
        let cmp_0 = Zq::from((1152921504606846976_i64, u64::MAX));
        let cmp_1 = Zq::from((1, u64::MAX));
        let cmp_2 = Zq::from((18446744073709551613_u64, u64::MAX));

        let res_0 = base.pow(&exp_0).unwrap();
        let res_1 = base.pow(&exp_1).unwrap();
        let res_2 = base.pow(&exp_2).unwrap();

        assert_eq!(cmp_0, res_0);
        assert_eq!(cmp_1, res_1);
        assert_eq!(cmp_2, res_2);
    }

    /// Ensures that the `pow` trait is available for other types
    #[test]
    fn availability() {
        let base = Zq::from((i64::MAX, u64::MAX));
        let exp = Z::from(4);

        let _ = base.pow(exp);
        let _ = base.pow(2_i8);
        let _ = base.pow(2_i16);
        let _ = base.pow(2_i32);
        let _ = base.pow(2_i64);
        let _ = base.pow(2_u8);
        let _ = base.pow(2_u16);
        let _ = base.pow(2_u32);
        let _ = base.pow(2_u64);
    }

    /// Ensures that `pow` returns an error if a non-invertible basis is
    /// powered by a negative exponent
    #[test]
    fn non_invertible_detection() {
        let base = Zq::from((2, 4));

        assert!(base.pow(-1).is_err());
    }
}