curv/arithmetic/
traits.rs

1/*
2    Cryptography utilities
3
4    Copyright 2018 by Kzen Networks
5
6    This file is part of Cryptography utilities library
7    (https://github.com/KZen-networks/cryptography-utils)
8
9    Cryptography utilities is free software: you can redistribute
10    it and/or modify it under the terms of the GNU General Public
11    License as published by the Free Software Foundation, either
12    version 3 of the License, or (at your option) any later version.
13
14    @license GPL-3.0+ <https://github.com/KZen-networks/cryptography-utils/blob/master/LICENSE>
15*/
16
17use super::errors::ParseBigIntError;
18
19/// Reuse common traits from [num_integer] crate
20pub use num_integer::{Integer, Roots};
21/// Reuse common traits from [num_traits] crate
22pub use num_traits::{One, Zero};
23
24#[deprecated(
25    since = "0.6.0",
26    note = "BigInt now implements zeroize::Zeroize trait, you should use it instead"
27)]
28pub trait ZeroizeBN {
29    fn zeroize_bn(&mut self);
30}
31
32/// Converts BigInt to/from various forms of representation.
33pub trait Converter: Sized {
34    /// Returns bytes representation of the number.
35    ///
36    /// ## Examples
37    /// ```
38    /// # use curv::arithmetic::{BigInt, Converter};
39    /// assert_eq!(BigInt::from(31).to_bytes(), &[31]);
40    /// assert_eq!(BigInt::from(1_000_000).to_bytes(), &[15, 66, 64]);
41    /// ```
42    fn to_bytes(&self) -> Vec<u8>;
43    /// Constructs BigInt from its byte representation
44    ///
45    /// ```
46    /// # use curv::arithmetic::{BigInt, Converter};
47    /// assert_eq!(BigInt::from_bytes(&[15, 66, 64]), BigInt::from(1_000_000))
48    /// ```
49    fn from_bytes(bytes: &[u8]) -> Self;
50
51    /// Returns bytes representation of the number in an array with length chosen by the user
52    /// if the array is larger than the bytes it pads it with zeros in the most significant bytes
53    /// If the array is too small for the integer it returns None.
54    ///
55    /// ## Examples
56    /// ```
57    /// # use curv::arithmetic::{BigInt, Converter};
58    /// assert_eq!(BigInt::from(31).to_bytes_array(), Some([31]));
59    /// assert_eq!(BigInt::from(31).to_bytes_array(), Some([0, 31]));
60    /// assert_eq!(BigInt::from(1_000_000).to_bytes_array(), Some([15, 66, 64]));
61    /// assert_eq!(BigInt::from(1_000_000).to_bytes_array::<2>(), None);
62    /// assert_eq!(BigInt::from(1_000_000).to_bytes_array(), Some([0, 15, 66, 64]));
63    /// ```
64    fn to_bytes_array<const N: usize>(&self) -> Option<[u8; N]> {
65        let bytes = self.to_bytes();
66        if bytes.len() > N {
67            return None;
68        }
69        let mut array = [0u8; N];
70        array[N - bytes.len()..].copy_from_slice(&bytes);
71        Some(array)
72    }
73
74    /// Converts BigInt to hex representation.
75    ///
76    /// If the number is negative, it will be serialized by absolute value, and minus character
77    /// will be prepended to resulting string.
78    ///
79    /// ## Examples
80    /// ```
81    /// # use curv::arithmetic::{BigInt, Converter};
82    /// assert_eq!(BigInt::from(31).to_hex(), "1f");
83    /// assert_eq!(BigInt::from(1_000_000).to_hex(), "f4240");
84    /// ```
85    fn to_hex(&self) -> String {
86        self.to_str_radix(16)
87    }
88    /// Parses given hex string.
89    ///
90    /// Follows the same format as was described in [to_hex](Self::to_hex).
91    ///
92    /// ## Examples
93    /// ```
94    /// # use curv::arithmetic::{BigInt, Converter};
95    /// assert_eq!(BigInt::from_hex("1f").unwrap(), BigInt::from(31));
96    /// assert_eq!(BigInt::from_hex("-1f").unwrap(), BigInt::from(-31));
97    /// assert_eq!(BigInt::from_hex("f4240").unwrap(), BigInt::from(1_000_000));
98    /// assert_eq!(BigInt::from_hex("-f4240").unwrap(), BigInt::from(-1_000_000));
99    /// ```
100    fn from_hex(n: &str) -> Result<Self, ParseBigIntError> {
101        Self::from_str_radix(n, 16)
102    }
103
104    /// Converts BigInt to radix representation.
105    ///
106    /// If the number is negative, it will be serialized by absolute value, and minus character
107    /// will be prepended to resulting string.
108    ///
109    /// ## Examples
110    /// ```
111    /// # use curv::arithmetic::{BigInt, Converter};
112    /// assert_eq!(BigInt::from(31).to_str_radix(16), "1f");
113    /// assert_eq!(BigInt::from(1_000_000).to_str_radix(16), "f4240");
114    /// ```
115    fn to_str_radix(&self, radix: u8) -> String;
116    /// Parses given radix string.
117    ///
118    /// Radix must be in `[2; 36]` range. Otherwise, function will **panic**.
119    ///
120    /// ## Examples
121    /// ```
122    /// # use curv::arithmetic::{BigInt, Converter};
123    /// assert_eq!(BigInt::from_str_radix("1f", 16).unwrap(), BigInt::from(31));
124    /// assert_eq!(BigInt::from_str_radix("f4240", 16).unwrap(), BigInt::from(1_000_000));
125    /// ```
126    fn from_str_radix(s: &str, radix: u8) -> Result<Self, ParseBigIntError>;
127}
128
129/// Provides basic arithmetic operators for BigInt
130///
131/// Note that BigInt also implements std::ops::{Add, Mull, ...} traits, so you can
132/// use them instead.
133pub trait BasicOps {
134    fn pow(&self, exponent: u32) -> Self;
135    fn mul(&self, other: &Self) -> Self;
136    fn sub(&self, other: &Self) -> Self;
137    fn add(&self, other: &Self) -> Self;
138    fn abs(&self) -> Self;
139}
140
141/// Modular arithmetic for BigInt
142pub trait Modulo: Sized {
143    /// Calculates base^(exponent) (mod m)
144    ///
145    /// Exponent must not be negative. Function will panic otherwise.
146    fn mod_pow(base: &Self, exponent: &Self, m: &Self) -> Self;
147    /// Calculates a * b (mod m)
148    fn mod_mul(a: &Self, b: &Self, modulus: &Self) -> Self;
149    /// Calculates a - b (mod m)
150    fn mod_sub(a: &Self, b: &Self, modulus: &Self) -> Self;
151    /// Calculates a + b (mod m)
152    fn mod_add(a: &Self, b: &Self, modulus: &Self) -> Self;
153    /// Calculates a^-1 (mod m). Returns None if `a` and `m` are not coprimes.
154    fn mod_inv(a: &Self, m: &Self) -> Option<Self>;
155    /// Calculates a mod m
156    fn modulus(&self, modulus: &Self) -> Self;
157}
158
159/// Generating random BigInt
160pub trait Samplable {
161    /// Generates random number within `[0; upper)` range
162    ///
163    /// ## Panics
164    /// Panics if `upper <= 0`
165    fn sample_below(upper: &Self) -> Self;
166    /// Generates random number within `[lower; upper)` range
167    ///
168    /// ## Panics
169    /// Panics if `upper <= lower`
170    fn sample_range(lower: &Self, upper: &Self) -> Self;
171    /// Generates random number within `(lower; upper)` range
172    ///
173    /// ## Panics
174    /// Panics if `upper <= lower`
175    fn strict_sample_range(lower: &Self, upper: &Self) -> Self;
176    /// Generates number within `[0; 2^bit_size)` range
177    fn sample(bit_size: usize) -> Self;
178    /// Generates number within `[2^(bit_size-1); 2^bit_size)` range
179    fn strict_sample(bit_size: usize) -> Self;
180}
181
182/// Set of predicates allowing to examine BigInt
183pub trait NumberTests {
184    /// Returns `true` if `n` is zero
185    ///
186    /// Alternatively, [BasicOps::sign] method can be used to check sign of the number.
187    fn is_zero(n: &Self) -> bool;
188    /// Returns `true` if `n` is negative
189    ///
190    /// Alternatively, [BasicOps::sign] method can be used to check sign of the number.
191    fn is_negative(n: &Self) -> bool;
192}
193
194/// Extended GCD algorithm
195pub trait EGCD
196where
197    Self: Sized,
198{
199    /// For given a, b calculates gcd(a,b), p, q such as `gcd(a,b) = a*p + b*q`
200    ///
201    /// ## Example
202    /// ```
203    /// # use curv::arithmetic::*;
204    /// let (a, b) = (BigInt::from(10), BigInt::from(15));
205    /// let (s, p, q) = BigInt::egcd(&a, &b);
206    /// assert_eq!(&s, &BigInt::from(5));
207    /// assert_eq!(s, a*p + b*q);
208    /// ```
209    fn egcd(a: &Self, b: &Self) -> (Self, Self, Self);
210}
211
212/// Bits manipulation in BigInt
213pub trait BitManipulation {
214    /// Sets/unsets bit in the number
215    ///
216    /// ## Example
217    /// ```
218    /// # use curv::arithmetic::*;
219    /// let mut n = BigInt::from(0b100);
220    /// n.set_bit(3, true);
221    /// assert_eq!(n, BigInt::from(0b1100));
222    /// n.set_bit(0, true);
223    /// assert_eq!(n, BigInt::from(0b1101));
224    /// n.set_bit(2, false);
225    /// assert_eq!(n, BigInt::from(0b1001));
226    /// ```
227    fn set_bit(&mut self, bit: usize, bit_val: bool);
228    /// Tests if bit is set
229    ///
230    /// ```
231    /// # use curv::arithmetic::*;
232    /// let n = BigInt::from(0b101);
233    /// assert_eq!(n.test_bit(3), false);
234    /// assert_eq!(n.test_bit(2), true);
235    /// assert_eq!(n.test_bit(1), false);
236    /// assert_eq!(n.test_bit(0), true);
237    /// ```
238    fn test_bit(&self, bit: usize) -> bool;
239    /// Length of the number in bits
240    ///
241    /// ```
242    /// # use curv::arithmetic::*;
243    /// assert_eq!(BigInt::from(0b1011).bit_length(), 4);
244    /// ```
245    fn bit_length(&self) -> usize;
246}
247
248#[deprecated(
249    since = "0.6.0",
250    note = "Use corresponding From<T> and TryFrom<T> traits implemented on BigInt"
251)]
252pub trait ConvertFrom<T> {
253    fn _from(_: &T) -> Self;
254}
255
256/// Utilities for searching / testing prime numbers
257pub trait Primes {
258    /// Finds next prime number using probabilistic algorithms
259    fn next_prime(&self) -> Self;
260    /// Probabilistically determine whether number is prime
261    ///
262    /// If number is prime, `is_probable_prime` always returns true. If number is composite,
263    /// `is_probable_prime` probably return false. The probability of returning true for a randomly
264    /// chosen non-prime is at most 4^(-reps).
265    fn is_probable_prime(&self, n: u32) -> bool;
266}
curv/arithmetic/traits.rs

curv/arithmetic/
traits.rs
