zmodn-rs

commit c07b47ee1a7aa3469753fa2ec49f3b499defac55
parent 51bb82df499e35cdc13d33dd24eca85d7abd0aaf
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Mon, 23 Jun 2025 11:21:11 +0200

Finalized

Diffstat:
A
README.md
 | 
3
+++
M
src/lib.rs
 | 
83
+++++++++++++++++++++++++++++++++++++++----------------------------------------

2 files changed, 44 insertions(+), 42 deletions(-)
diff --git a/README.md b/README.md
@@ -0,0 +1,3 @@
+A small library for integers modulo n, similar to
+[zmodn](https://git.tronto.net/zmodn/file/README.md.html)
+but in Rust.
diff --git a/src/lib.rs b/src/lib.rs
@@ -1,20 +1,19 @@
-// TODO: make Zmod argument type generic
-// TODO: re-implement ECM?
-
 use std::fmt;
 use std::ops;
 
+pub type BaseInt = i64;
+
 // We assume canonical representative, can compare value for PartialEq
 #[derive(Copy, Clone, Debug, PartialEq)]
-pub struct Zmod<const N: i64> {
-    value: i64
+pub struct Zmod<const N: BaseInt> {
+    value: BaseInt
 }
 
-fn canonical_rep<const N: i64>(x: i64) -> i64 {
+fn canonical_rep<const N: BaseInt>(x: BaseInt) -> BaseInt {
     return (x % N + N) % N;
 }
 
-fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
+fn extended_gcd(a: BaseInt, b: BaseInt) -> (BaseInt, BaseInt, BaseInt) {
     if b == 0 {
         return (a, 1, 0);
     }
@@ -22,15 +21,15 @@ fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
     (g, y, x - y*(a/b))
 }
 
-impl<const N: i64> Zmod<N> {
-    pub fn from(x: i64) -> Zmod<N> {
+impl<const N: BaseInt> Zmod<N> {
+    pub fn from(x: BaseInt) -> Zmod<N> {
         #[cfg(debug_assertions)]
         assert!(N > 1, "modulus must be greater than 1");
 
         Zmod::<N> { value: canonical_rep::<N>(x) }
     }
 
-    fn inverse(self) -> Result<Zmod<N>, i64> {
+    fn inverse(self) -> Result<Zmod<N>, BaseInt> {
         let (g, a, _) = extended_gcd(self.value, N);
         if g == 1 {
             Ok(Zmod::<N>::from(a))
@@ -40,13 +39,13 @@ impl<const N: i64> Zmod<N> {
     }
 }
 
-impl<const N: i64> fmt::Display for Zmod<N> {
+impl<const N: BaseInt> fmt::Display for Zmod<N> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "({} mod {})", self.value, N)
     }
 }
 
-impl<const N: i64> ops::Add for Zmod<N> {
+impl<const N: BaseInt> ops::Add for Zmod<N> {
     type Output = Zmod<N>;
 
     fn add(self, z: Zmod<N>) -> Zmod<N> {
@@ -54,15 +53,15 @@ impl<const N: i64> ops::Add for Zmod<N> {
     }
 }
 
-impl<const N: i64> ops::Add<i64> for Zmod<N> {
+impl<const N: BaseInt> ops::Add<BaseInt> for Zmod<N> {
     type Output = Zmod<N>;
 
-    fn add(self, z: i64) -> Zmod<N> {
+    fn add(self, z: BaseInt) -> Zmod<N> {
         Zmod::<N>::from(self.value + z)
     }
 }
 
-impl<const N: i64> ops::Add<Zmod<N>> for i64 {
+impl<const N: BaseInt> ops::Add<Zmod<N>> for BaseInt {
     type Output = Zmod::<N>;
 
     fn add(self, z: Zmod::<N>) -> Zmod<N> {
@@ -70,19 +69,19 @@ impl<const N: i64> ops::Add<Zmod<N>> for i64 {
     }
 }
 
-impl<const N: i64> ops::AddAssign for Zmod<N> {
+impl<const N: BaseInt> ops::AddAssign for Zmod<N> {
     fn add_assign(&mut self, z: Zmod<N>) {
         self.value = canonical_rep::<N>(self.value + z.value);
     }
 }
 
-impl<const N: i64> ops::AddAssign<i64> for Zmod<N> {
-    fn add_assign(&mut self, z: i64) {
+impl<const N: BaseInt> ops::AddAssign<BaseInt> for Zmod<N> {
+    fn add_assign(&mut self, z: BaseInt) {
         self.value = canonical_rep::<N>(self.value + z);
     }
 }
 
-impl<const N: i64> ops::Sub for Zmod<N> {
+impl<const N: BaseInt> ops::Sub for Zmod<N> {
     type Output = Zmod<N>;
 
     fn sub(self, z: Zmod<N>) -> Zmod<N> {
@@ -90,15 +89,15 @@ impl<const N: i64> ops::Sub for Zmod<N> {
     }
 }
 
-impl<const N: i64> ops::Sub<i64> for Zmod<N> {
+impl<const N: BaseInt> ops::Sub<BaseInt> for Zmod<N> {
     type Output = Zmod<N>;
 
-    fn sub(self, z: i64) -> Zmod<N> {
+    fn sub(self, z: BaseInt) -> Zmod<N> {
         Zmod::<N>::from(self.value - z)
     }
 }
 
-impl<const N: i64> ops::Sub<Zmod<N>> for i64 {
+impl<const N: BaseInt> ops::Sub<Zmod<N>> for BaseInt {
     type Output = Zmod<N>;
 
     fn sub(self, z: Zmod<N>) -> Zmod<N> {
@@ -106,19 +105,19 @@ impl<const N: i64> ops::Sub<Zmod<N>> for i64 {
     }
 }
 
-impl<const N: i64> ops::SubAssign for Zmod<N> {
+impl<const N: BaseInt> ops::SubAssign for Zmod<N> {
     fn sub_assign(&mut self, z: Zmod<N>) {
         self.value = canonical_rep::<N>(self.value - z.value);
     }
 }
 
-impl<const N: i64> ops::SubAssign<i64> for Zmod<N> {
-    fn sub_assign(&mut self, z: i64) {
+impl<const N: BaseInt> ops::SubAssign<BaseInt> for Zmod<N> {
+    fn sub_assign(&mut self, z: BaseInt) {
         self.value = canonical_rep::<N>(self.value - z);
     }
 }
 
-impl<const N: i64> ops::Neg for Zmod<N> {
+impl<const N: BaseInt> ops::Neg for Zmod<N> {
     type Output = Zmod<N>;
 
     fn neg(self) -> Zmod<N> {
@@ -126,7 +125,7 @@ impl<const N: i64> ops::Neg for Zmod<N> {
     }
 }
 
-impl<const N: i64> ops::Mul for Zmod<N> {
+impl<const N: BaseInt> ops::Mul for Zmod<N> {
     type Output = Zmod<N>;
 
     fn mul(self, z: Zmod<N>) -> Zmod<N> {
@@ -134,15 +133,15 @@ impl<const N: i64> ops::Mul for Zmod<N> {
     }
 }
 
-impl<const N: i64> ops::Mul<i64> for Zmod<N> {
+impl<const N: BaseInt> ops::Mul<BaseInt> for Zmod<N> {
     type Output = Zmod<N>;
 
-    fn mul(self, z: i64) -> Zmod<N> {
+    fn mul(self, z: BaseInt) -> Zmod<N> {
         Zmod::<N>::from(self.value * z)
     }
 }
 
-impl<const N: i64> ops::Mul<Zmod<N>> for i64 {
+impl<const N: BaseInt> ops::Mul<Zmod<N>> for BaseInt {
     type Output = Zmod<N>;
 
     fn mul(self, z: Zmod<N>) -> Zmod<N> {
@@ -150,38 +149,38 @@ impl<const N: i64> ops::Mul<Zmod<N>> for i64 {
     }
 }
 
-impl<const N: i64> ops::MulAssign for Zmod<N> {
+impl<const N: BaseInt> ops::MulAssign for Zmod<N> {
     fn mul_assign(&mut self, z: Zmod<N>) {
         self.value = canonical_rep::<N>(self.value * z.value);
     }
 }
 
-impl<const N: i64> ops::MulAssign<i64> for Zmod<N> {
-    fn mul_assign(&mut self, z: i64) {
+impl<const N: BaseInt> ops::MulAssign<BaseInt> for Zmod<N> {
+    fn mul_assign(&mut self, z: BaseInt) {
         self.value = canonical_rep::<N>(self.value * z);
     }
 }
 
-impl<const N: i64> ops::Div for Zmod<N> {
-    type Output = Result<Zmod<N>, i64>;
+impl<const N: BaseInt> ops::Div for Zmod<N> {
+    type Output = Result<Zmod<N>, BaseInt>;
 
-    fn div(self, z: Zmod<N>) -> Result<Zmod<N>, i64> {
+    fn div(self, z: Zmod<N>) -> Result<Zmod<N>, BaseInt> {
         Ok(self * z.inverse()?)
     }
 }
 
-impl<const N: i64> ops::Div<i64> for Zmod<N> {
-    type Output = Result<Zmod<N>, i64>;
+impl<const N: BaseInt> ops::Div<BaseInt> for Zmod<N> {
+    type Output = Result<Zmod<N>, BaseInt>;
 
-    fn div(self, z: i64) -> Result<Zmod<N>, i64> {
+    fn div(self, z: BaseInt) -> Result<Zmod<N>, BaseInt> {
         self / Zmod::<N>::from(z)
     }
 }
 
-impl<const N: i64> ops::Div<Zmod<N>> for i64 {
-    type Output = Result<Zmod<N>, i64>;
+impl<const N: BaseInt> ops::Div<Zmod<N>> for BaseInt {
+    type Output = Result<Zmod<N>, BaseInt>;
 
-    fn div(self, z: Zmod<N>) -> Result<Zmod<N>, i64> {
+    fn div(self, z: Zmod<N>) -> Result<Zmod<N>, BaseInt> {
         Zmod::<N>::from(self) / z
     }
 }