oxinum_int/native/
core_traits.rs

1//! Core trait implementations from `oxinum_core` for the native
2//! [`BigUint`] and [`BigInt`] types.
3//!
4//! This module wires up:
5//! - `OxiNum`, `OxiUnsigned`, `OxiSigned`
6//! - `FromRadix`, `ToRadix`
7//! - `Roots`, `Pow<u32>`
8//! - `ModularArithmetic`
9//! - `Primality`
10
11use super::int::BigInt;
12use super::uint::BigUint;
13use super::{mod_arith, primality};
14use oxinum_core::{
15    FromRadix, ModularArithmetic, OxiNum, OxiNumResult, OxiSigned, OxiUnsigned, Pow, Primality,
16    Roots, Sign, ToRadix,
17};
18
19// ============================================================================
20// BigUint: OxiNum
21// ============================================================================
22
23impl OxiNum for BigUint {
24    #[inline]
25    fn is_zero(&self) -> bool {
26        BigUint::is_zero(self)
27    }
28
29    #[inline]
30    fn is_one(&self) -> bool {
31        BigUint::is_one(self)
32    }
33}
34
35// ============================================================================
36// BigUint: OxiUnsigned (marker)
37// ============================================================================
38
39impl OxiUnsigned for BigUint {}
40
41// ============================================================================
42// BigUint: FromRadix / ToRadix
43// ============================================================================
44
45impl FromRadix for BigUint {
46    fn from_radix(src: &str, radix: u32) -> OxiNumResult<Self> {
47        BigUint::from_str_radix(src, radix)
48    }
49}
50
51impl ToRadix for BigUint {
52    fn to_radix(&self, radix: u32) -> OxiNumResult<String> {
53        BigUint::to_radix(self, radix)
54    }
55}
56
57// ============================================================================
58// BigUint: Roots
59// ============================================================================
60
61impl Roots for BigUint {
62    #[inline]
63    fn sqrt(&self) -> Self {
64        BigUint::sqrt(self)
65    }
66
67    #[inline]
68    fn cbrt(&self) -> Self {
69        // n=3 never fails in nth_root
70        BigUint::nth_root(self, 3).expect("cbrt: n=3 is always valid")
71    }
72
73    #[inline]
74    fn nth_root(&self, n: u32) -> Self {
75        BigUint::nth_root(self, n).expect("nth_root: n must be >= 1")
76    }
77}
78
79// ============================================================================
80// BigUint: Pow<u32>
81// ============================================================================
82
83impl Pow<u32> for BigUint {
84    type Output = BigUint;
85
86    #[inline]
87    fn pow(&self, exp: u32) -> BigUint {
88        BigUint::pow(self, exp)
89    }
90}
91
92// ============================================================================
93// BigUint: ModularArithmetic
94// ============================================================================
95
96impl ModularArithmetic for BigUint {
97    fn mod_add(&self, rhs: &Self, modulus: &Self) -> Self {
98        assert!(!modulus.is_zero(), "mod_add: modulus must be non-zero");
99        let sum = self + rhs;
100        &sum % modulus
101    }
102
103    fn mod_sub(&self, rhs: &Self, modulus: &Self) -> Self {
104        assert!(!modulus.is_zero(), "mod_sub: modulus must be non-zero");
105        if self >= rhs {
106            let diff = self - rhs;
107            diff % modulus
108        } else {
109            let diff = rhs - self;
110            let r = diff % modulus;
111            if r.is_zero() {
112                BigUint::ZERO
113            } else {
114                modulus - &r
115            }
116        }
117    }
118
119    fn mod_mul(&self, rhs: &Self, modulus: &Self) -> Self {
120        mod_arith::mod_mul(self, rhs, modulus).expect("mod_mul: modulus must be non-zero")
121    }
122
123    fn mod_pow(&self, exp: &Self, modulus: &Self) -> Self {
124        mod_arith::mod_pow(self, exp, modulus).expect("mod_pow: modulus must be non-zero")
125    }
126}
127
128// ============================================================================
129// BigUint: Primality
130// ============================================================================
131
132impl Primality for BigUint {
133    fn is_probably_prime(&self, _witnesses: u32) -> bool {
134        // `_witnesses` is ignored — our implementation always uses BPSW/
135        // deterministic Miller-Rabin with proven witness sets; it subsumes
136        // any user-specified witness count.
137        primality::is_probably_prime(self)
138    }
139
140    fn next_prime(&self) -> Self {
141        // Special case: input <= 1 → first prime is 2.
142        if self.is_zero() || self.is_one() {
143            return BigUint::from_u64(2);
144        }
145        // Start the search from self + 1 and iterate until we hit a prime.
146        let one = BigUint::from_u64(1);
147        let two = BigUint::from_u64(2);
148        let mut candidate = self + &one;
149        // Ensure we start from an odd number (all even numbers > 2 are composite).
150        if !candidate.test_bit(0) {
151            candidate += &one;
152        }
153        loop {
154            if primality::is_probably_prime(&candidate) {
155                return candidate;
156            }
157            // Advance by 2 to stay on odd numbers.
158            candidate += &two;
159        }
160    }
161}
162
163// ============================================================================
164// BigInt: OxiNum
165// ============================================================================
166
167impl OxiNum for BigInt {
168    #[inline]
169    fn is_zero(&self) -> bool {
170        BigInt::is_zero(self)
171    }
172
173    #[inline]
174    fn is_one(&self) -> bool {
175        BigInt::is_one(self)
176    }
177}
178
179// ============================================================================
180// BigInt: OxiSigned
181// ============================================================================
182
183impl OxiSigned for BigInt {
184    #[inline]
185    fn signum(&self) -> Sign {
186        BigInt::signum(self)
187    }
188
189    #[inline]
190    fn abs(&self) -> Self {
191        BigInt::abs(self)
192    }
193}
194
195// ============================================================================
196// BigInt: FromRadix / ToRadix
197// ============================================================================
198
199impl FromRadix for BigInt {
200    fn from_radix(src: &str, radix: u32) -> OxiNumResult<Self> {
201        // Strip optional leading '-', parse magnitude, then negate if needed.
202        let (negative, digits) = match src.strip_prefix('-') {
203            Some(rest) => (true, rest),
204            None => (false, src),
205        };
206        let mag = BigUint::from_str_radix(digits, radix)?;
207        let sign = if negative && !mag.is_zero() {
208            Sign::Negative
209        } else {
210            Sign::Positive
211        };
212        Ok(BigInt::from_parts(sign, mag))
213    }
214}
215
216impl ToRadix for BigInt {
217    fn to_radix(&self, radix: u32) -> OxiNumResult<String> {
218        let mag_str = self.magnitude().to_radix(radix)?;
219        if self.is_negative() {
220            Ok(format!("-{mag_str}"))
221        } else {
222            Ok(mag_str)
223        }
224    }
225}
226
227// ============================================================================
228// BigInt: Pow<u32>
229// ============================================================================
230
231impl Pow<u32> for BigInt {
232    type Output = BigInt;
233
234    fn pow(&self, exp: u32) -> BigInt {
235        let mag = BigUint::pow(self.magnitude(), exp);
236        // A negative base raised to an odd exponent is negative; otherwise positive.
237        let sign = if self.is_negative() && exp % 2 == 1 {
238            Sign::Negative
239        } else {
240            Sign::Positive
241        };
242        BigInt::from_parts(sign, mag)
243    }
244}
oxinum_int/native/core_traits.rs

oxinum_int/native/
core_traits.rs
