fss_rs/group/
int_prime.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright (C) 2023 Yulong Ming (myl7)
3
4//! Integers as a group which is a `$p$`-group.
5//! `MOD` as the `$p$` is a prime number as the cardinality of the group.
6//! Some prime numbers that are the max ones less than or equal to `u*::MAX` are provided as `PRIME_MAX_LE_U*_MAX`.
7//!
8//! - Associative operation: Integer addition modulo `MOD`, `$(a + b) \mod MOD$`.
9//! - Identity element: 0.
10//! - Inverse element: `-x`.
11
12use std::mem::size_of;
13use std::ops::{Add, AddAssign, Neg};
14
15use super::Group;
16
17macro_rules! decl_int_prime_group {
18    ($t:ty, $t_impl:ident) => {
19        /// See [`self`].
20        #[derive(Debug, Clone, PartialEq, Eq)]
21        pub struct $t_impl<const MOD: $t>(
22            /// Always less than `MOD`.
23            $t,
24        );
25
26        impl<const MOD: $t> $t_impl<MOD> {
27            pub fn new(x: $t) -> Self {
28                $t_impl(x % MOD)
29            }
30        }
31
32        impl<const MOD: $t> Add for $t_impl<MOD> {
33            type Output = Self;
34
35            fn add(self, rhs: Self) -> Self::Output {
36                $t_impl(match self.0.checked_add(rhs.0) {
37                    Some(x) => x % MOD,
38                    None => {
39                        (self.0.wrapping_add(rhs.0) % MOD)
40                            .wrapping_add(<$t>::MAX % MOD)
41                            .wrapping_add(1)
42                            % MOD
43                    }
44                })
45            }
46        }
47
48        impl<const MOD: $t> AddAssign for $t_impl<MOD> {
49            fn add_assign(&mut self, rhs: Self) {
50                self.0 = match self.0.checked_add(rhs.0) {
51                    Some(x) => x % MOD,
52                    None => {
53                        self.0
54                            .wrapping_add(rhs.0)
55                            .wrapping_add(<$t>::MAX % MOD)
56                            .wrapping_add(1)
57                            % MOD
58                    }
59                };
60            }
61        }
62
63        impl<const MOD: $t> Neg for $t_impl<MOD> {
64            type Output = Self;
65
66            fn neg(mut self) -> Self::Output {
67                self.0 = (MOD - self.0) % MOD;
68                self
69            }
70        }
71
72        impl<const BLEN: usize, const MOD: $t> Group<BLEN> for $t_impl<MOD> {
73            fn zero() -> Self {
74                $t_impl(0)
75            }
76        }
77
78        impl<const BLEN: usize, const MOD: $t> From<[u8; BLEN]> for $t_impl<MOD> {
79            fn from(value: [u8; BLEN]) -> Self {
80                if cfg!(not(feature = "int-be")) {
81                    $t_impl(
82                        <$t>::from_le_bytes(
83                            (&value[..size_of::<$t>()]).clone().try_into().unwrap(),
84                        ) % MOD,
85                    )
86                } else {
87                    $t_impl(
88                        <$t>::from_be_bytes(
89                            (&value[..size_of::<$t>()]).clone().try_into().unwrap(),
90                        ) % MOD,
91                    )
92                }
93            }
94        }
95
96        impl<const MOD: $t> From<$t> for $t_impl<MOD> {
97            fn from(value: $t) -> Self {
98                <$t_impl<MOD>>::new(value)
99            }
100        }
101
102        impl<const BLEN: usize, const MOD: $t> From<$t_impl<MOD>> for [u8; BLEN] {
103            fn from(value: $t_impl<MOD>) -> Self {
104                let mut bs = [0; BLEN];
105                if cfg!(not(feature = "int-be")) {
106                    bs[..size_of::<$t>()].copy_from_slice(&value.0.to_le_bytes());
107                } else {
108                    bs[..size_of::<$t>()].copy_from_slice(&value.0.to_be_bytes());
109                }
110                bs
111            }
112        }
113
114        impl<const MOD: $t> From<$t_impl<MOD>> for $t {
115            fn from(value: $t_impl<MOD>) -> Self {
116                value.0
117            }
118        }
119    };
120}
121
122decl_int_prime_group!(u8, U8Group);
123decl_int_prime_group!(u16, U16Group);
124decl_int_prime_group!(u32, U32Group);
125decl_int_prime_group!(u64, U64Group);
126decl_int_prime_group!(u128, U128Group);
127
128/// `$2^8 - 5$`
129pub const PRIME_MAX_LE_U8_MAX: u8 = u8::MAX - 5 + 1;
130/// `$2^16 - 15$`
131pub const PRIME_MAX_LE_U16_MAX: u16 = u16::MAX - 15 + 1;
132/// `$2^32 - 5$`
133pub const PRIME_MAX_LE_U32_MAX: u32 = u32::MAX - 5 + 1;
134/// `$2^64 - 59$`
135pub const PRIME_MAX_LE_U64_MAX: u64 = u64::MAX - 59 + 1;
136/// `$2^128 - 159$`
137pub const PRIME_MAX_LE_U128_MAX: u128 = u128::MAX - 159 + 1;
138
139#[cfg(test)]
140mod tests {
141    use super::*;
142    use crate::test_group_axioms;
143
144    test_group_axioms!(test_u8_group_axioms, U8Group<PRIME_MAX_LE_U8_MAX>, 1);
145    test_group_axioms!(test_u16_group_axioms, U16Group<PRIME_MAX_LE_U16_MAX>, 2);
146    test_group_axioms!(test_u32_group_axioms, U32Group<PRIME_MAX_LE_U32_MAX>, 4);
147    test_group_axioms!(test_u64_group_axioms, U64Group<PRIME_MAX_LE_U64_MAX>, 8);
148    test_group_axioms!(test_u128_group_axioms, U128Group<PRIME_MAX_LE_U128_MAX>, 16);
149}
fss_rs/group/int_prime.rs

fss_rs/group/
int_prime.rs
