curv/arithmetic/
big_gmp.rs

1/*
2    Curv
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/curv/blob/master/LICENSE>
15*/
16
17use std::convert::{TryFrom, TryInto};
18use std::sync::atomic;
19use std::{fmt, ops, ptr};
20
21use gmp::mpz::Mpz;
22use gmp::sign::Sign;
23use num_traits::{One, Zero};
24use zeroize::Zeroize;
25
26use super::errors::*;
27use super::traits::*;
28
29type BN = Mpz;
30
31/// Big integer
32///
33/// Wraps underlying BigInt implementation (either GMP bindings or num-bigint), exposes only
34/// very limited API that allows easily switching between implementations.
35///
36/// Set of traits implemented on BigInt remains the same regardless of underlying implementation.
37#[derive(PartialOrd, PartialEq, Ord, Eq, Clone)]
38pub struct BigInt {
39    gmp: Mpz,
40}
41
42impl BigInt {
43    fn inner_ref(&self) -> &Mpz {
44        &self.gmp
45    }
46    fn inner_mut(&mut self) -> &mut Mpz {
47        &mut self.gmp
48    }
49    fn into_inner(self) -> Mpz {
50        self.gmp
51    }
52}
53
54#[allow(deprecated)]
55impl ZeroizeBN for BigInt {
56    fn zeroize_bn(&mut self) {
57        unsafe { ptr::write_volatile(&mut self.gmp, Mpz::zero()) };
58        atomic::fence(atomic::Ordering::SeqCst);
59        atomic::compiler_fence(atomic::Ordering::SeqCst);
60    }
61}
62
63impl Zeroize for BigInt {
64    fn zeroize(&mut self) {
65        unsafe { ptr::write_volatile(&mut self.gmp, Mpz::zero()) };
66        atomic::fence(atomic::Ordering::SeqCst);
67        atomic::compiler_fence(atomic::Ordering::SeqCst);
68    }
69}
70
71impl Converter for BigInt {
72    fn to_bytes(&self) -> Vec<u8> {
73        (&self.gmp).into()
74    }
75
76    fn from_bytes(bytes: &[u8]) -> Self {
77        Mpz::from(bytes).wrap()
78    }
79
80    fn to_hex(&self) -> String {
81        self.gmp.to_str_radix(16)
82    }
83
84    fn from_hex(value: &str) -> Result<BigInt, ParseBigIntError> {
85        Mpz::from_str_radix(value, 16)
86            .map(Wrap::wrap)
87            .map_err(|e| ParseBigIntError {
88                reason: ParseErrorReason::Gmp(e),
89                radix: 16,
90            })
91    }
92
93    fn to_str_radix(&self, radix: u8) -> String {
94        self.gmp.to_str_radix(radix)
95    }
96
97    fn from_str_radix(str: &str, radix: u8) -> Result<Self, ParseBigIntError> {
98        Mpz::from_str_radix(str, radix)
99            .map(Wrap::wrap)
100            .map_err(|e| ParseBigIntError {
101                reason: ParseErrorReason::Gmp(e),
102                radix: radix.into(),
103            })
104    }
105}
106
107impl num_traits::Num for BigInt {
108    type FromStrRadixErr = ParseBigIntError;
109    fn from_str_radix(str: &str, radix: u32) -> Result<Self, ParseBigIntError> {
110        <Self as Converter>::from_str_radix(str, radix.try_into().unwrap())
111    }
112}
113
114impl BasicOps for BigInt {
115    fn pow(&self, exponent: u32) -> Self {
116        self.gmp.pow(exponent).wrap()
117    }
118
119    fn mul(&self, other: &Self) -> Self {
120        self * other
121    }
122
123    fn sub(&self, other: &Self) -> Self {
124        self - other
125    }
126
127    fn add(&self, other: &Self) -> Self {
128        self + other
129    }
130
131    fn abs(&self) -> Self {
132        self.gmp.abs().wrap()
133    }
134}
135
136impl Primes for BigInt {
137    fn next_prime(&self) -> Self {
138        self.gmp.nextprime().wrap()
139    }
140
141    fn is_probable_prime(&self, n: u32) -> bool {
142        use gmp::mpz::ProbabPrimeResult::*;
143        match self.gmp.probab_prime(n as i32) {
144            Prime | ProbablyPrime => true,
145            NotPrime => false,
146        }
147    }
148}
149
150impl Modulo for BigInt {
151    fn mod_pow(base: &Self, exponent: &Self, modulus: &Self) -> Self {
152        assert!(exponent >= &BigInt::zero(), "exponent must be non-negative");
153        base.gmp.powm(&exponent.gmp, &modulus.gmp).wrap()
154    }
155
156    fn mod_mul(a: &Self, b: &Self, modulus: &Self) -> Self {
157        (a.gmp.mod_floor(&modulus.gmp) * b.gmp.mod_floor(&modulus.gmp))
158            .mod_floor(&modulus.gmp)
159            .wrap()
160    }
161
162    fn mod_sub(a: &Self, b: &Self, modulus: &Self) -> Self {
163        let a_m = a.gmp.mod_floor(&modulus.gmp);
164        let b_m = b.gmp.mod_floor(&modulus.gmp);
165
166        let sub_op = a_m - b_m + &modulus.gmp;
167        sub_op.mod_floor(&modulus.gmp).wrap()
168    }
169
170    fn mod_add(a: &Self, b: &Self, modulus: &Self) -> Self {
171        (a.gmp.mod_floor(&modulus.gmp) + b.gmp.mod_floor(&modulus.gmp))
172            .mod_floor(&modulus.gmp)
173            .wrap()
174    }
175
176    fn mod_inv(a: &Self, modulus: &Self) -> Option<Self> {
177        Some(a.gmp.invert(&modulus.gmp)?.wrap())
178    }
179
180    fn modulus(&self, modulus: &Self) -> Self {
181        self.gmp.modulus(&modulus.gmp).wrap()
182    }
183}
184
185impl NumberTests for BigInt {
186    fn is_zero(me: &Self) -> bool {
187        me.gmp.is_zero()
188    }
189    fn is_negative(me: &Self) -> bool {
190        matches!(me.gmp.sign(), Sign::Negative)
191    }
192}
193
194impl EGCD for BigInt {
195    #[allow(clippy::many_single_char_names)]
196    fn egcd(a: &Self, b: &Self) -> (Self, Self, Self) {
197        let (s, p, q) = a.gmp.gcdext(&b.gmp);
198        (s.wrap(), p.wrap(), q.wrap())
199    }
200}
201
202impl BitManipulation for BigInt {
203    fn set_bit(&mut self, bit: usize, bit_val: bool) {
204        if bit_val {
205            self.gmp.setbit(bit);
206        } else {
207            self.gmp.clrbit(bit);
208        }
209    }
210
211    fn test_bit(&self, bit: usize) -> bool {
212        self.gmp.tstbit(bit)
213    }
214
215    fn bit_length(&self) -> usize {
216        self.gmp.bit_length()
217    }
218}
219
220impl Integer for BigInt {
221    fn div_floor(&self, other: &Self) -> Self {
222        self.gmp.div_floor(&other.gmp).wrap()
223    }
224
225    fn mod_floor(&self, other: &Self) -> Self {
226        self.gmp.mod_floor(&other.gmp).wrap()
227    }
228
229    fn gcd(&self, other: &Self) -> Self {
230        self.gmp.gcd(&other.gmp).wrap()
231    }
232
233    fn lcm(&self, other: &Self) -> Self {
234        self.gmp.lcm(&other.gmp).wrap()
235    }
236
237    fn divides(&self, other: &Self) -> bool {
238        self.gmp.divides(&other.gmp)
239    }
240
241    fn is_multiple_of(&self, other: &Self) -> bool {
242        self.gmp.is_multiple_of(&other.gmp)
243    }
244
245    fn is_even(&self) -> bool {
246        self.gmp.is_multiple_of(&Mpz::from(2))
247    }
248
249    fn is_odd(&self) -> bool {
250        !self.gmp.is_multiple_of(&Mpz::from(2))
251    }
252
253    fn div_rem(&self, other: &Self) -> (Self, Self) {
254        let n = self / other;
255        let m = self % other;
256        (n, m)
257    }
258}
259
260impl Roots for BigInt {
261    fn nth_root(&self, n: u32) -> Self {
262        self.gmp.root(n).wrap()
263    }
264
265    fn sqrt(&self) -> Self {
266        self.gmp.sqrt().wrap()
267    }
268}
269
270impl fmt::Display for BigInt {
271    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
272        self.gmp.fmt(f)
273    }
274}
275
276impl fmt::Debug for BigInt {
277    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
278        self.gmp.fmt(f)
279    }
280}
281
282macro_rules! impl_try_from {
283    ($($primitive:ty),*$(,)?) => {
284        $(
285        impl TryFrom<&BigInt> for $primitive {
286            type Error = TryFromBigIntError;
287
288            fn try_from(value: &BigInt) -> Result<Self, Self::Error> {
289                Option::<$primitive>::from(&value.gmp)
290                    .ok_or(TryFromBigIntError { type_name: stringify!($primitive) })
291            }
292        }
293        )*
294    };
295}
296
297impl_try_from! { u64, i64 }
298
299#[allow(deprecated)]
300impl ConvertFrom<BigInt> for u64 {
301    fn _from(x: &BigInt) -> u64 {
302        let opt_x: Option<u64> = (&x.gmp).into();
303        opt_x.unwrap()
304    }
305}
306
307crate::__bigint_impl_ops! {
308    Add add,
309    Sub sub,
310    Mul mul,
311    Div div,
312    Rem rem,
313    BitAnd bitand,
314    BitXor bitxor,
315    Shl shl usize,
316    Shr shr usize,
317
318    Add add u64 [swap],
319    Sub sub u64 [swap],
320    Mul mul u64 [swap],
321    Div div u64,
322    Rem rem u64,
323}
324
325crate::__bigint_impl_assigns! {
326    AddAssign add_assign,
327    AddAssign add_assign u64,
328    BitAndAssign bitand_assign,
329    BitOrAssign bitor_assign,
330    BitXorAssign bitxor_assign,
331    DivAssign div_assign,
332    DivAssign div_assign u64,
333    MulAssign mul_assign,
334    MulAssign mul_assign u64,
335    RemAssign rem_assign,
336    RemAssign rem_assign u64,
337    ShlAssign shl_assign usize,
338    ShrAssign shr_assign usize,
339    SubAssign sub_assign,
340    SubAssign sub_assign u64,
341}
342
343impl ops::Neg for BigInt {
344    type Output = BigInt;
345    fn neg(self) -> Self::Output {
346        self.gmp.neg().wrap()
347    }
348}
349impl ops::Neg for &BigInt {
350    type Output = BigInt;
351    fn neg(self) -> Self::Output {
352        (&self.gmp).neg().wrap()
353    }
354}
355
356impl Zero for BigInt {
357    fn zero() -> Self {
358        Mpz::zero().wrap()
359    }
360
361    fn is_zero(&self) -> bool {
362        self.gmp.is_zero()
363    }
364}
365
366impl One for BigInt {
367    fn one() -> Self {
368        Mpz::one().wrap()
369    }
370    fn is_one(&self) -> bool {
371        self.gmp.is_one()
372    }
373}
374
375crate::__bigint_impl_from! { u32, i32, u64 }
376
377impl From<u16> for BigInt {
378    fn from(n: u16) -> Self {
379        BigInt::from(u64::from(n))
380    }
381}
382
383/// Internal helper trait. Creates short-hand for wrapping Mpz into BigInt.
384trait Wrap {
385    fn wrap(self) -> BigInt;
386}
387impl Wrap for Mpz {
388    fn wrap(self) -> BigInt {
389        BigInt { gmp: self }
390    }
391}
curv/arithmetic/big_gmp.rs

curv/arithmetic/
big_gmp.rs
