sn_curv 0.10.1

/*
    Cryptography utilities

    Copyright 2018 by Kzen Networks

    This file is part of Cryptography utilities library
    (https://github.com/KZen-networks/cryptography-utils)

    Cryptography utilities is free software: you can redistribute
    it and/or modify it under the terms of the GNU General Public
    License as published by the Free Software Foundation, either
    version 3 of the License, or (at your option) any later version.

    @license GPL-3.0+ <https://github.com/KZen-networks/cryptography-utils/blob/master/LICENSE>
*/

use super::errors::ParseBigIntError;

/// Reuse common traits from [num_integer] crate
pub use num_integer::{Integer, Roots};
/// Reuse common traits from [num_traits] crate
pub use num_traits::{One, Zero};

#[deprecated(
    since = "0.6.0",
    note = "BigInt now implements zeroize::Zeroize trait, you should use it instead"
)]
pub trait ZeroizeBN {
    fn zeroize_bn(&mut self);
}

/// Converts BigInt to/from various forms of representation.
pub trait Converter: Sized {
    /// Returns bytes representation of the number.
    ///
    /// ## Examples
    /// ```
    /// # use curv::arithmetic::{BigInt, Converter};
    /// assert_eq!(BigInt::from(31).to_bytes(), &[31]);
    /// assert_eq!(BigInt::from(1_000_000).to_bytes(), &[15, 66, 64]);
    /// ```
    fn to_bytes(&self) -> Vec<u8>;
    /// Constructs BigInt from its byte representation
    ///
    /// ```
    /// # use curv::arithmetic::{BigInt, Converter};
    /// assert_eq!(BigInt::from_bytes(&[15, 66, 64]), BigInt::from(1_000_000))
    /// ```
    fn from_bytes(bytes: &[u8]) -> Self;

    /// Returns bytes representation of the number in an array with length chosen by the user
    /// if the array is larger than the bytes it pads it with zeros in the most significant bytes
    /// If the array is too small for the integer it returns None.
    ///
    /// ## Examples
    /// ```
    /// # use curv::arithmetic::{BigInt, Converter};
    /// assert_eq!(BigInt::from(31).to_bytes_array(), Some([31]));
    /// assert_eq!(BigInt::from(31).to_bytes_array(), Some([0, 31]));
    /// assert_eq!(BigInt::from(1_000_000).to_bytes_array(), Some([15, 66, 64]));
    /// assert_eq!(BigInt::from(1_000_000).to_bytes_array::<2>(), None);
    /// assert_eq!(BigInt::from(1_000_000).to_bytes_array(), Some([0, 15, 66, 64]));
    /// ```
    fn to_bytes_array<const N: usize>(&self) -> Option<[u8; N]> {
        let bytes = self.to_bytes();
        if bytes.len() > N {
            return None;
        }
        let mut array = [0u8; N];
        array[N - bytes.len()..].copy_from_slice(&bytes);
        Some(array)
    }

    /// Converts BigInt to hex representation.
    ///
    /// If the number is negative, it will be serialized by absolute value, and minus character
    /// will be prepended to resulting string.
    ///
    /// ## Examples
    /// ```
    /// # use curv::arithmetic::{BigInt, Converter};
    /// assert_eq!(BigInt::from(31).to_hex(), "1f");
    /// assert_eq!(BigInt::from(1_000_000).to_hex(), "f4240");
    /// ```
    fn to_hex(&self) -> String {
        self.to_str_radix(16)
    }
    /// Parses given hex string.
    ///
    /// Follows the same format as was described in [to_hex](Self::to_hex).
    ///
    /// ## Examples
    /// ```
    /// # use curv::arithmetic::{BigInt, Converter};
    /// assert_eq!(BigInt::from_hex("1f").unwrap(), BigInt::from(31));
    /// assert_eq!(BigInt::from_hex("-1f").unwrap(), BigInt::from(-31));
    /// assert_eq!(BigInt::from_hex("f4240").unwrap(), BigInt::from(1_000_000));
    /// assert_eq!(BigInt::from_hex("-f4240").unwrap(), BigInt::from(-1_000_000));
    /// ```
    fn from_hex(n: &str) -> Result<Self, ParseBigIntError> {
        Self::from_str_radix(n, 16)
    }

    /// Converts BigInt to radix representation.
    ///
    /// If the number is negative, it will be serialized by absolute value, and minus character
    /// will be prepended to resulting string.
    ///
    /// ## Examples
    /// ```
    /// # use curv::arithmetic::{BigInt, Converter};
    /// assert_eq!(BigInt::from(31).to_str_radix(16), "1f");
    /// assert_eq!(BigInt::from(1_000_000).to_str_radix(16), "f4240");
    /// ```
    fn to_str_radix(&self, radix: u8) -> String;
    /// Parses given radix string.
    ///
    /// Radix must be in `[2; 36]` range. Otherwise, function will **panic**.
    ///
    /// ## Examples
    /// ```
    /// # use curv::arithmetic::{BigInt, Converter};
    /// assert_eq!(BigInt::from_str_radix("1f", 16).unwrap(), BigInt::from(31));
    /// assert_eq!(BigInt::from_str_radix("f4240", 16).unwrap(), BigInt::from(1_000_000));
    /// ```
    fn from_str_radix(s: &str, radix: u8) -> Result<Self, ParseBigIntError>;
}

/// Provides basic arithmetic operators for BigInt
///
/// Note that BigInt also implements std::ops::{Add, Mull, ...} traits, so you can
/// use them instead.
pub trait BasicOps {
    fn pow(&self, exponent: u32) -> Self;
    fn mul(&self, other: &Self) -> Self;
    fn sub(&self, other: &Self) -> Self;
    fn add(&self, other: &Self) -> Self;
    fn abs(&self) -> Self;
}

/// Modular arithmetic for BigInt
pub trait Modulo: Sized {
    /// Calculates base^(exponent) (mod m)
    ///
    /// Exponent must not be negative. Function will panic otherwise.
    fn mod_pow(base: &Self, exponent: &Self, m: &Self) -> Self;
    /// Calculates a * b (mod m)
    fn mod_mul(a: &Self, b: &Self, modulus: &Self) -> Self;
    /// Calculates a - b (mod m)
    fn mod_sub(a: &Self, b: &Self, modulus: &Self) -> Self;
    /// Calculates a + b (mod m)
    fn mod_add(a: &Self, b: &Self, modulus: &Self) -> Self;
    /// Calculates a^-1 (mod m). Returns None if `a` and `m` are not coprimes.
    fn mod_inv(a: &Self, m: &Self) -> Option<Self>;
    /// Calculates a mod m
    fn modulus(&self, modulus: &Self) -> Self;
}

/// Generating random BigInt
pub trait Samplable {
    /// Generates random number within `[0; upper)` range
    ///
    /// ## Panics
    /// Panics if `upper <= 0`
    fn sample_below(upper: &Self) -> Self;
    /// Generates random number within `[lower; upper)` range
    ///
    /// ## Panics
    /// Panics if `upper <= lower`
    fn sample_range(lower: &Self, upper: &Self) -> Self;
    /// Generates random number within `(lower; upper)` range
    ///
    /// ## Panics
    /// Panics if `upper <= lower`
    fn strict_sample_range(lower: &Self, upper: &Self) -> Self;
    /// Generates number within `[0; 2^bit_size)` range
    fn sample(bit_size: usize) -> Self;
    /// Generates number within `[2^(bit_size-1); 2^bit_size)` range
    fn strict_sample(bit_size: usize) -> Self;
}

/// Set of predicates allowing to examine BigInt
pub trait NumberTests {
    /// Returns `true` if `n` is zero
    ///
    /// Alternatively, [BasicOps::sign] method can be used to check sign of the number.
    fn is_zero(n: &Self) -> bool;
    /// Returns `true` if `n` is negative
    ///
    /// Alternatively, [BasicOps::sign] method can be used to check sign of the number.
    fn is_negative(n: &Self) -> bool;
}

/// Extended GCD algorithm
pub trait EGCD
where
    Self: Sized,
{
    /// For given a, b calculates gcd(a,b), p, q such as `gcd(a,b) = a*p + b*q`
    ///
    /// ## Example
    /// ```
    /// # use curv::arithmetic::*;
    /// let (a, b) = (BigInt::from(10), BigInt::from(15));
    /// let (s, p, q) = BigInt::egcd(&a, &b);
    /// assert_eq!(&s, &BigInt::from(5));
    /// assert_eq!(s, a*p + b*q);
    /// ```
    fn egcd(a: &Self, b: &Self) -> (Self, Self, Self);
}

/// Bits manipulation in BigInt
pub trait BitManipulation {
    /// Sets/unsets bit in the number
    ///
    /// ## Example
    /// ```
    /// # use curv::arithmetic::*;
    /// let mut n = BigInt::from(0b100);
    /// n.set_bit(3, true);
    /// assert_eq!(n, BigInt::from(0b1100));
    /// n.set_bit(0, true);
    /// assert_eq!(n, BigInt::from(0b1101));
    /// n.set_bit(2, false);
    /// assert_eq!(n, BigInt::from(0b1001));
    /// ```
    fn set_bit(&mut self, bit: usize, bit_val: bool);
    /// Tests if bit is set
    ///
    /// ```
    /// # use curv::arithmetic::*;
    /// let n = BigInt::from(0b101);
    /// assert_eq!(n.test_bit(3), false);
    /// assert_eq!(n.test_bit(2), true);
    /// assert_eq!(n.test_bit(1), false);
    /// assert_eq!(n.test_bit(0), true);
    /// ```
    fn test_bit(&self, bit: usize) -> bool;
    /// Length of the number in bits
    ///
    /// ```
    /// # use curv::arithmetic::*;
    /// assert_eq!(BigInt::from(0b1011).bit_length(), 4);
    /// ```
    fn bit_length(&self) -> usize;
}

#[deprecated(
    since = "0.6.0",
    note = "Use corresponding From<T> and TryFrom<T> traits implemented on BigInt"
)]
pub trait ConvertFrom<T> {
    fn _from(_: &T) -> Self;
}

/// Utilities for searching / testing prime numbers
pub trait Primes {
    /// Finds next prime number using probabilistic algorithms
    fn next_prime(&self) -> Self;
    /// Probabilistically determine whether number is prime
    ///
    /// If number is prime, `is_probable_prime` always returns true. If number is composite,
    /// `is_probable_prime` probably return false. The probability of returning true for a randomly
    /// chosen non-prime is at most 4^(-reps).
    fn is_probable_prime(&self, n: u32) -> bool;
}