astra_num/
lib.rs

1//! # Astra-Num
2//!
3//! `astra-num` is a Rust library providing an easy-to-use wrapper around
4//! [`num-bigint`](https://crates.io/crates/num-bigint), [`num-integer`](https://crates.io/crates/num-integer),
5//! and [`num-traits`](https://crates.io/crates/num-traits). It offers additional utilities
6//! for handling incredibly large (astronomical) values, cryptography, and more.
7
8use num_bigint::{BigInt, Sign, ToBigInt, ParseBigIntError};
9use num_traits::{FromPrimitive, ToPrimitive, Zero, One, Num, Signed};
10use num_integer::Integer;
11use std::ops::{
12    Add, Sub, Mul, Div, Rem, Neg,
13    BitAnd, BitOr, BitXor, Not,
14    AddAssign, SubAssign, MulAssign, DivAssign, RemAssign
15};
16use std::str::FromStr;
17use std::fmt;
18use serde::{Deserialize, Deserializer, Serialize};
19
20#[cfg(feature = "crypto_utils")]
21use rand::prelude::*;
22
23/// Represents errors that can occur when working with [`BigNum`].
24#[derive(Debug)]
25pub enum BigNumError {
26    /// Wrapper for parse errors from `num_bigint`.
27    ParseBigIntError(ParseBigIntError),
28    /// Generic conversion error with an accompanying message.
29    ConversionError(String),
30}
31
32impl From<ParseBigIntError> for BigNumError {
33    fn from(err: ParseBigIntError) -> Self {
34        BigNumError::ParseBigIntError(err)
35    }
36}
37
38/// Represents errors specifically related to parsing [`BigInt`]-formatted values.
39#[derive(Debug)]
40pub enum BigIntError {
41    /// Returned when the string format is invalid.
42    InvalidFormat,
43    // Additional variants can be added as needed.
44}
45
46impl fmt::Display for BigIntError {
47    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
48        match self {
49            BigIntError::InvalidFormat => write!(f, "Invalid BigInt format"),
50        }
51    }
52}
53
54impl std::error::Error for BigIntError {}
55
56/// A wrapper struct around `BigInt` providing additional utilities
57/// such as modular exponentiation, easy conversions, and more.
58/// 
59/// # Example
60/// 
61/// ```
62/// use astra_num::BigNum;
63/// 
64/// let a = BigNum::from(123u32);
65/// let b = BigNum::from(456u32);
66/// let c = a + b;
67/// println!("{}", c); // 579
68/// ```
69#[derive(Debug, Clone, PartialEq, Eq, Default)]
70pub struct BigNum(pub BigInt);
71
72impl BigNum {
73    /// Constructs a new [`BigNum`] directly from a [`BigInt`].
74    pub fn is(value: BigInt) -> Self {
75        BigNum(value)
76    }
77
78    /// Creates a [`BigNum`] from a decimal string.
79    ///
80    /// # Errors
81    ///
82    /// Returns [`BigIntError::InvalidFormat`] if parsing fails.
83    pub fn from_str(s: &str) -> Result<Self, BigIntError> {
84        match BigInt::from_str(s) {
85            Ok(bigint) => Ok(BigNum(bigint)),
86            Err(_) => Err(BigIntError::InvalidFormat),
87        }
88    }
89
90    /// Converts this [`BigNum`] to a decimal string.
91    pub fn to_string(&self) -> String {
92        self.0.to_string()
93    }
94
95    /// Creates a [`BigNum`] from a little-endian byte slice.
96    pub fn from_bytes_le(bytes: &[u8]) -> Self {
97        BigNum(BigInt::from_bytes_le(Sign::Plus, bytes))
98    }
99
100    /// Converts this [`BigNum`] into a tuple of (Sign, `Vec<u8>`) in little-endian byte order.
101    pub fn to_bytes_le(&self) -> (Sign, Vec<u8>) {
102        self.0.to_bytes_le()
103    }
104
105    /// Creates a [`BigNum`] by parsing a byte slice with the given `radix` in **big-endian** order.
106    ///
107    /// # Errors
108    ///
109    /// Returns [`BigNumError::ConversionError`] if parsing fails for the given `radix`.
110    pub fn from_radix_be(bytes: &[u8], radix: u32) -> Result<BigNum, BigNumError> {
111        match BigInt::parse_bytes(bytes, radix) {
112            Some(bigint) => Ok(BigNum(bigint)),
113            None => Err(BigNumError::ConversionError(
114                "Invalid digit found for the given radix".into(),
115            )),
116        }
117    }
118
119    /// Converts this [`BigNum`] to an `f64`, returning `None` if it doesn't fit.
120    pub fn to_f64(&self) -> Option<f64> {
121        self.0.to_f64()
122    }
123
124    /// Creates a [`BigNum`] from an `f64`. May lose precision or return an error for NaN/infinity.
125    ///
126    /// # Errors
127    ///
128    /// Returns [`BigNumError::ConversionError`] if the value is not representable as an integer.
129    pub fn from_f64(value: f64) -> Result<BigNum, BigNumError> {
130        value.to_bigint()
131            .map(BigNum)
132            .ok_or(BigNumError::ConversionError(
133                "Failed to convert f64 to BigInt".into(),
134            ))
135    }
136
137    /// Adds two [`BigNum`]s by reference and returns the result.
138    pub fn add(&self, other: &BigNum) -> BigNum {
139        BigNum(&self.0 + &other.0)
140    }
141
142    /// Subtracts two [`BigNum`]s by reference and returns the result.
143    pub fn sub(&self, other: &BigNum) -> BigNum {
144        BigNum(&self.0 - &other.0)
145    }
146
147    /// Multiplies two [`BigNum`]s by reference and returns the result.
148    pub fn mul(&self, other: &BigNum) -> BigNum {
149        BigNum(&self.0 * &other.0)
150    }
151
152    /// Performs integer division (floor) between two [`BigNum`]s by reference and returns the result.
153    /// 
154    /// # Panics
155    ///
156    /// May panic if `other` is zero.
157    pub fn div(&self, other: &Self) -> Self {
158        BigNum(&self.0 / &other.0)
159    }
160
161    /// Returns the remainder of dividing this [`BigNum`] by another.
162    ///
163    /// # Panics
164    ///
165    /// May panic if `other` is zero.
166    pub fn rem(&self, other: &Self) -> Self {
167        BigNum(&self.0 % &other.0)
168    }
169
170    /// Returns the integer square root (floor) of this [`BigNum`].
171    pub fn sqrt(&self) -> BigNum {
172        BigNum(self.0.sqrt())
173    }
174
175    /// Computes a more precise integer square root using Newton's method.
176    ///
177    /// # Errors
178    ///
179    /// Returns an error string if the number is negative (since real sqrt is not defined for negative values).
180    pub fn sqrt_precise(&self) -> Result<BigNum, String> {
181        if self.0.sign() == Sign::Minus {
182            return Err("Square root of negative numbers is not supported.".into());
183        }
184
185        if self.0 < BigInt::from(2) {
186            return Ok(self.clone());
187        }
188
189        let two: BigInt = BigInt::from(2);
190        let mut x0 = self.0.clone();
191        let mut x1 = (&self.0 / &two) + 1u32;
192
193        while x1 < x0 {
194            x0 = x1.clone();
195            x1 = ((&self.0 / &x1) + &x1) / &two;
196        }
197        Ok(BigNum(x0))
198    }
199
200    /// Returns the number of bits needed to represent this [`BigNum`].
201    pub fn bits(&self) -> u64 {
202        self.0.bits()
203    }
204
205    /// Raises this [`BigNum`] to the power of `exp` using exponentiation by squaring.
206    pub fn pow(&self, exp: u32) -> Self {
207        BigNum(self.0.pow(exp))
208    }
209
210    /// Computes `(self^exponent) mod modulus` using modular exponentiation.
211    pub fn mod_pow(&self, exponent: &Self, modulus: &Self) -> BigNum {
212        BigNum(self.0.modpow(&exponent.0, &modulus.0))
213    }
214
215    /// Computes the bitwise AND of `self` & `other`.
216    pub fn bitand(&self, other: &Self) -> Self {
217        BigNum(&self.0 & &other.0)
218    }
219
220    /// Computes the bitwise OR of `self` | `other`.
221    pub fn bitor(&self, other: &Self) -> Self {
222        BigNum(&self.0 | &other.0)
223    }
224
225    /// Computes the bitwise XOR of `self` ^ `other`.
226    pub fn bitxor(&self, other: &Self) -> Self {
227        BigNum(&self.0 ^ &other.0)
228    }
229
230    /// Computes the bitwise NOT of `self`.
231    pub fn not(&self) -> Self {
232        BigNum(!&self.0)
233    }
234
235    /// Checks if this [`BigNum`] is zero.
236    pub fn is_zero(&self) -> bool {
237        self.0.is_zero()
238    }
239
240    /// Returns an immutable reference to the underlying `BigInt`.
241    pub fn inner(&self) -> &BigInt {
242        &self.0
243    }
244
245    // ================================================================
246    // Cryptographic Utilities (enabled with `crypto_utils` feature)
247    // ================================================================
248    #[cfg(feature = "crypto_utils")]
249    /// Performs the Miller-Rabin primality test for a given number of `rounds`.
250    /// 
251    /// The more rounds used, the higher the confidence that the number is prime.
252    pub fn probable_prime(&self, rounds: usize) -> bool {
253        let n = &self.0;
254
255        if *n == BigInt::one() || *n == BigInt::from(2) {
256            return true;
257        }
258        if n.is_even() {
259            return false;
260        }
261
262        let mut rng = rand::thread_rng();
263        let (d, r) = n.sub(1).unwrap().decompose();
264
265        'outer: for _ in 0..rounds {
266            let a = rng.gen_bigint_range(&BigInt::from(2), &(n - 1));
267            let mut x = a.modpow(&d, n);
268
269            if x == BigInt::one() || x == n - 1 {
270                continue;
271            }
272
273            for _ in 0..r {
274                x = x.modpow(&BigInt::from(2), n);
275
276                if x == n - 1 {
277                    continue 'outer;
278                }
279            }
280            return false;
281        }
282        true
283    }
284
285    #[cfg(feature = "crypto_utils")]
286    /// Generates a random prime [`BigNum`] of the given bit size.
287    ///
288    /// Uses 20 Miller-Rabin rounds for primality checks by default.
289    pub fn generate_prime(bits: usize) -> BigNum {
290        let mut rng = rand::thread_rng();
291        loop {
292            let candidate = rng.gen_bigint(bits);
293            if candidate.probable_prime(20) {
294                return BigNum(candidate);
295            }
296        }
297    }
298}
299
300// ================================================================
301// Trait Implementations
302// ================================================================
303
304impl fmt::Display for BigNum {
305    /// Allows printing a [`BigNum`] with `format!` or `println!`.
306    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
307        write!(f, "{}", self.0)
308    }
309}
310
311impl From<&BigInt> for BigNum {
312    fn from(value: &BigInt) -> Self {
313        BigNum(value.clone())
314    }
315}
316
317impl From<&BigNum> for BigNum {
318    fn from(value: &BigNum) -> Self {
319        value.clone()
320    }
321}
322
323impl From<i32> for BigNum {
324    fn from(num: i32) -> Self {
325        BigNum(BigInt::from(num))
326    }
327}
328
329impl From<u32> for BigNum {
330    fn from(num: u32) -> Self {
331        BigNum(BigInt::from(num))
332    }
333}
334
335impl From<u64> for BigNum {
336    fn from(num: u64) -> Self {
337        BigNum(BigInt::from(num))
338    }
339}
340
341// Operator Overloads
342impl Add for BigNum {
343    type Output = BigNum;
344    fn add(self, other: Self) -> Self::Output {
345        BigNum(self.0 + other.0)
346    }
347}
348
349impl Sub for BigNum {
350    type Output = BigNum;
351    fn sub(self, other: Self) -> Self::Output {
352        BigNum(self.0 - other.0)
353    }
354}
355
356impl Mul for BigNum {
357    type Output = BigNum;
358    fn mul(self, other: Self) -> Self::Output {
359        BigNum(self.0 * other.0)
360    }
361}
362
363impl Mul for &BigNum {
364    type Output = BigNum;
365    fn mul(self, other: &BigNum) -> BigNum {
366        BigNum(&self.0 * &other.0)
367    }
368}
369
370impl Mul<BigNum> for &BigNum {
371    type Output = BigNum;
372    fn mul(self, mut other: BigNum) -> BigNum {
373        other.0 *= &self.0;
374        other
375    }
376}
377
378impl Mul<&BigNum> for BigNum {
379    type Output = BigNum;
380    fn mul(mut self, other: &BigNum) -> BigNum {
381        self.0 *= &other.0;
382        self
383    }
384}
385
386impl Div for BigNum {
387    type Output = BigNum;
388    fn div(self, other: Self) -> Self::Output {
389        BigNum(self.0 / other.0)
390    }
391}
392
393impl Rem for BigNum {
394    type Output = BigNum;
395    fn rem(self, other: Self) -> Self::Output {
396        BigNum(self.0 % other.0)
397    }
398}
399
400impl Neg for BigNum {
401    type Output = BigNum;
402    fn neg(self) -> Self::Output {
403        BigNum(-self.0)
404    }
405}
406
407impl AddAssign for BigNum {
408    fn add_assign(&mut self, other: Self) {
409        self.0 += other.0;
410    }
411}
412
413impl SubAssign for BigNum {
414    fn sub_assign(&mut self, other: Self) {
415        self.0 -= other.0;
416    }
417}
418
419impl MulAssign for BigNum {
420    fn mul_assign(&mut self, other: Self) {
421        self.0 *= other.0;
422    }
423}
424
425impl DivAssign for BigNum {
426    fn div_assign(&mut self, other: Self) {
427        self.0 /= other.0;
428    }
429}
430
431impl RemAssign for BigNum {
432    fn rem_assign(&mut self, other: Self) {
433        self.0 %= other.0;
434    }
435}
436
437impl PartialOrd for BigNum {
438    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
439        Some(self.cmp(other))
440    }
441}
442
443impl Ord for BigNum {
444    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
445        self.0.cmp(&other.0)
446    }
447}
448
449impl BitAnd for BigNum {
450    type Output = Self;
451    fn bitand(self, rhs: Self) -> Self::Output {
452        BigNum(self.0 & rhs.0)
453    }
454}
455
456impl BitOr for BigNum {
457    type Output = Self;
458    fn bitor(self, rhs: Self) -> Self::Output {
459        BigNum(self.0 | rhs.0)
460    }
461}
462
463impl BitXor for BigNum {
464    type Output = Self;
465    fn bitxor(self, rhs: Self) -> Self::Output {
466        BigNum(self.0 ^ rhs.0)
467    }
468}
469
470impl Not for BigNum {
471    type Output = Self;
472    fn not(self) -> Self::Output {
473        BigNum(!self.0)
474    }
475}
476
477// Serde Serialization & Deserialization
478impl Serialize for BigNum {
479    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
480    where
481        S: serde::Serializer,
482    {
483        serializer.serialize_str(&self.to_string())
484    }
485}
486
487impl<'de> Deserialize<'de> for BigNum {
488    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
489    where
490        D: Deserializer<'de>,
491    {
492        let s = String::deserialize(deserializer)?;
493        BigNum::from_str(&s).map_err(serde::de::Error::custom)
494    }
495}
496
497// Zero and One
498impl Zero for BigNum {
499    fn zero() -> Self {
500        BigNum(BigInt::zero())
501    }
502    fn is_zero(&self) -> bool {
503        self.0.is_zero()
504    }
505}
506
507impl One for BigNum {
508    fn one() -> Self {
509        BigNum(BigInt::one())
510    }
511}
512
513// Integer trait implementation
514impl Integer for BigNum {
515    fn div_floor(&self, other: &Self) -> Self {
516        BigNum(&self.0 / &other.0)
517    }
518
519    fn mod_floor(&self, other: &Self) -> Self {
520        BigNum(self.0.mod_floor(&other.0))
521    }
522
523    fn gcd(&self, other: &Self) -> Self {
524        BigNum(self.0.gcd(&other.0))
525    }
526
527    fn lcm(&self, other: &Self) -> Self {
528        BigNum(self.0.lcm(&other.0))
529    }
530
531    fn divides(&self, other: &Self) -> bool {
532        if other.is_zero() {
533            return self.is_zero();
534        }
535        let r = &other.0 % &self.0;
536        r.is_zero()
537    }
538
539    fn is_multiple_of(&self, other: &Self) -> bool {
540        if self.is_zero() {
541            return other.is_zero();
542        }
543        let r = &self.0 % &other.0;
544        r.is_zero()
545    }
546
547    fn is_even(&self) -> bool {
548        let two = BigInt::from(2);
549        (&self.0 % two).is_zero()
550    }
551
552    fn is_odd(&self) -> bool {
553        !self.is_even()
554    }
555
556    fn div_rem(&self, other: &Self) -> (Self, Self) {
557        let (div, rem) = self.0.div_rem(&other.0);
558        (BigNum(div), BigNum(rem))
559    }
560}
561
562// Num trait implementation
563impl Num for BigNum {
564    type FromStrRadixErr = ParseBigIntError;
565
566    fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
567        BigInt::from_str_radix(str, radix).map(BigNum)
568    }
569}
570
571// Signed trait implementation
572impl Signed for BigNum {
573    fn abs(&self) -> Self {
574        BigNum(self.0.abs())
575    }
576
577    fn abs_sub(&self, other: &Self) -> Self {
578        if *self <= *other {
579            BigNum::zero()
580        } else {
581            self.sub(other)
582        }
583    }
584
585    fn signum(&self) -> Self {
586        BigNum(self.0.signum())
587    }
588
589    fn is_positive(&self) -> bool {
590        self.0.is_positive()
591    }
592
593    fn is_negative(&self) -> bool {
594        self.0.is_negative()
595    }
596}
597
598// FromPrimitive trait for convenience
599impl FromPrimitive for BigNum {
600    fn from_i64(n: i64) -> Option<Self> {
601        Some(BigNum(BigInt::from(n)))
602    }
603
604    fn from_u64(n: u64) -> Option<Self> {
605        Some(BigNum(BigInt::from(n)))
606    }
607}
608
609
610
611// ================================================================
612// Tests
613// ================================================================
614
615#[cfg(test)]
616mod tests {
617    use super::*;
618
619    #[test]
620    fn test_from_str_and_to_string() {
621        let bn = BigNum::from_str("12345").expect("Failed to parse BigNum from str");
622        assert_eq!(bn.to_string(), "12345");
623    }
624
625    #[test]
626    fn test_addition() {
627        let a = BigNum::from(2i32);
628        let b = BigNum::from(3i32);
629        let sum = a + b;
630        assert_eq!(sum.to_string(), "5");
631    }
632
633    #[test]
634    fn test_subtraction() {
635        let a = BigNum::from(10u32);
636        let b = BigNum::from(3u32);
637        let difference = a - b;
638        assert_eq!(difference.to_string(), "7");
639    }
640
641    #[test]
642    fn test_multiplication() {
643        let a = BigNum::from(6u32);
644        let b = BigNum::from(7u32);
645        let product = a * b;
646        assert_eq!(product.to_string(), "42");
647    }
648
649    #[test]
650    fn test_division() {
651        let a = BigNum::from(24u32);
652        let b = BigNum::from(4u32);
653        let quotient = a / b;
654        assert_eq!(quotient.to_string(), "6");
655    }
656
657    #[test]
658    fn test_remainder() {
659        let a = BigNum::from(29u32);
660        let b = BigNum::from(4u32);
661        let remainder = a % b;
662        assert_eq!(remainder.to_string(), "1");
663    }
664
665    #[test]
666    fn test_is_zero() {
667        let zero_num = BigNum::zero();
668        assert!(zero_num.is_zero());
669
670        let non_zero = BigNum::from(5u32);
671        assert!(!non_zero.is_zero());
672    }
673
674    #[test]
675    fn test_sqrt() {
676        // sqrt(49) = 7
677        let a = BigNum::from(49u32);
678        let r = a.sqrt();
679        assert_eq!(r.to_string(), "7");
680    }
681
682    #[test]
683    fn test_sqrt_precise() {
684        // sqrt_precise(100) = 10
685        let a = BigNum::from(100u32);
686        let r = a.sqrt_precise().expect("Failed to compute sqrt_precise");
687        assert_eq!(r.to_string(), "10");
688    }
689
690    #[test]
691    fn test_pow() {
692        // 2^10 = 1024
693        let base = BigNum::from(2u32);
694        let result = base.pow(10);
695        assert_eq!(result.to_string(), "1024");
696    }
697
698    #[test]
699    fn test_bits() {
700        // 15 in binary is 1111 => 4 bits
701        let a = BigNum::from(15u32);
702        assert_eq!(a.bits(), 4);
703    }
704}
astra_num/lib.rs

astra_num/
lib.rs
