1 static BIG_B: &str = "\
2                       efac3c0a_0de55551_fee0bfe4_67fa017a_1a898fa1_6ca57cb1\
3                       ca9e3248_cacc09a9_b99d6abc_38418d0f_82ae4238_d9a68832\
4                       aadec7c1_ac5fed48_7a56a71b_67ac59d5_afb28022_20d9592d\
5                       247c4efc_abbd9b75_586088ee_1dc00dc4_232a8e15_6e8191dd\
6                       675b6ae0_c80f5164_752940bc_284b7cee_885c1e10_e495345b\
7                       8fbe9cfd_e5233fe1_19459d0b_d64be53c_27de5a02_a829976b\
8                       33096862_82dad291_bd38b6a9_be396646_ddaf8039_a2573c39\
9                       1b14e8bc_2cb53e48_298c047e_d9879e9c_5a521076_f0e27df3\
10                       990e1659_d3d8205b_6443ebc0_9918ebee_6764f668_9f2b2be3\
11                       b59cbc76_d76d0dfc_d737c3ec_0ccf9c00_ad0554bf_17e776ad\
12                       b4edf9cc_6ce540be_76229093_5c53893b";
13 
14 static BIG_E: &str = "\
15                       be0e6ea6_08746133_e0fbc1bf_82dba91e_e2b56231_a81888d2\
16                       a833a1fc_f7ff002a_3c486a13_4f420bf3_a5435be9_1a5c8391\
17                       774d6e6c_085d8357_b0c97d4d_2bb33f7c_34c68059_f78d2541\
18                       eacc8832_426f1816_d3be001e_b69f9242_51c7708e_e10efe98\
19                       449c9a4a_b55a0f23_9d797410_515da00d_3ea07970_4478a2ca\
20                       c3d5043c_bd9be1b4_6dce479d_4302d344_84a939e6_0ab5ada7\
21                       12ae34b2_30cc473c_9f8ee69d_2cac5970_29f5bf18_bc8203e4\
22                       f3e895a2_13c94f1e_24c73d77_e517e801_53661fdd_a2ce9e47\
23                       a73dd7f8_2f2adb1e_3f136bf7_8ae5f3b8_08730de1_a4eff678\
24                       e77a06d0_19a522eb_cbefba2a_9caf7736_b157c5c6_2d192591\
25                       17946850_2ddb1822_117b68a0_32f7db88";
26 
27 // This modulus is the prime from the 2048-bit MODP DH group:
28 // https://tools.ietf.org/html/rfc3526#section-3
29 static BIG_M: &str = "\
30                       FFFFFFFF_FFFFFFFF_C90FDAA2_2168C234_C4C6628B_80DC1CD1\
31                       29024E08_8A67CC74_020BBEA6_3B139B22_514A0879_8E3404DD\
32                       EF9519B3_CD3A431B_302B0A6D_F25F1437_4FE1356D_6D51C245\
33                       E485B576_625E7EC6_F44C42E9_A637ED6B_0BFF5CB6_F406B7ED\
34                       EE386BFB_5A899FA5_AE9F2411_7C4B1FE6_49286651_ECE45B3D\
35                       C2007CB8_A163BF05_98DA4836_1C55D39A_69163FA8_FD24CF5F\
36                       83655D23_DCA3AD96_1C62F356_208552BB_9ED52907_7096966D\
37                       670C354E_4ABC9804_F1746C08_CA18217C_32905E46_2E36CE3B\
38                       E39E772C_180E8603_9B2783A2_EC07A28F_B5C55DF0_6F4C52C9\
39                       DE2BCBF6_95581718_3995497C_EA956AE5_15D22618_98FA0510\
40                       15728E5A_8AACAA68_FFFFFFFF_FFFFFFFF";
41 
42 static BIG_R: &str = "\
43                       a1468311_6e56edc9_7a98228b_5e924776_0dd7836e_caabac13\
44                       eda5373b_4752aa65_a1454850_40dc770e_30aa8675_6be7d3a8\
45                       9d3085e4_da5155cf_b451ef62_54d0da61_cf2b2c87_f495e096\
46                       055309f7_77802bbb_37271ba8_1313f1b5_075c75d1_024b6c77\
47                       fdb56f17_b05bce61_e527ebfd_2ee86860_e9907066_edd526e7\
48                       93d289bf_6726b293_41b0de24_eff82424_8dfd374b_4ec59542\
49                       35ced2b2_6b195c90_10042ffb_8f58ce21_bc10ec42_64fda779\
50                       d352d234_3d4eaea6_a86111ad_a37e9555_43ca78ce_2885bed7\
51                       5a30d182_f1cf6834_dc5b6e27_1a41ac34_a2e91e11_33363ff0\
52                       f88a7b04_900227c9_f6e6d06b_7856b4bb_4e354d61_060db6c8\
53                       109c4735_6e7db425_7b5d74c7_0b709508";
54 
55 mod biguint {
56     use num_bigint::BigUint;
57     use num_integer::Integer;
58     use num_traits::Num;
59 
check_modpow<T: Into<BigUint>>(b: T, e: T, m: T, r: T)60     fn check_modpow<T: Into<BigUint>>(b: T, e: T, m: T, r: T) {
61         let b: BigUint = b.into();
62         let e: BigUint = e.into();
63         let m: BigUint = m.into();
64         let r: BigUint = r.into();
65 
66         assert_eq!(b.modpow(&e, &m), r);
67 
68         let even_m = &m << 1;
69         let even_modpow = b.modpow(&e, &even_m);
70         assert!(even_modpow < even_m);
71         assert_eq!(even_modpow.mod_floor(&m), r);
72     }
73 
74     #[test]
test_modpow_single()75     fn test_modpow_single() {
76         check_modpow::<u32>(1, 0, 11, 1);
77         check_modpow::<u32>(0, 15, 11, 0);
78         check_modpow::<u32>(3, 7, 11, 9);
79         check_modpow::<u32>(5, 117, 19, 1);
80         check_modpow::<u32>(20, 1, 2, 0);
81         check_modpow::<u32>(20, 1, 3, 2);
82     }
83 
84     #[test]
test_modpow_small()85     fn test_modpow_small() {
86         for b in 0u64..11 {
87             for e in 0u64..11 {
88                 for m in 1..11 {
89                     check_modpow::<u64>(b, e, m, b.pow(e as u32) % m);
90                 }
91             }
92         }
93     }
94 
95     #[test]
test_modpow_big()96     fn test_modpow_big() {
97         let b = BigUint::from_str_radix(super::BIG_B, 16).unwrap();
98         let e = BigUint::from_str_radix(super::BIG_E, 16).unwrap();
99         let m = BigUint::from_str_radix(super::BIG_M, 16).unwrap();
100         let r = BigUint::from_str_radix(super::BIG_R, 16).unwrap();
101 
102         assert_eq!(b.modpow(&e, &m), r);
103 
104         let even_m = &m << 1;
105         let even_modpow = b.modpow(&e, &even_m);
106         assert!(even_modpow < even_m);
107         assert_eq!(even_modpow % m, r);
108     }
109 }
110 
111 mod bigint {
112     use num_bigint::BigInt;
113     use num_integer::Integer;
114     use num_traits::{Num, One, Signed};
115 
check_modpow<T: Into<BigInt>>(b: T, e: T, m: T, r: T)116     fn check_modpow<T: Into<BigInt>>(b: T, e: T, m: T, r: T) {
117         fn check(b: &BigInt, e: &BigInt, m: &BigInt, r: &BigInt) {
118             assert_eq!(&b.modpow(e, m), r, "{} ** {} (mod {}) != {}", b, e, m, r);
119 
120             let even_m = m << 1u8;
121             let even_modpow = b.modpow(e, m);
122             assert!(even_modpow.abs() < even_m.abs());
123             assert_eq!(&even_modpow.mod_floor(&m), r);
124 
125             // the sign of the result follows the modulus like `mod_floor`, not `rem`
126             assert_eq!(b.modpow(&BigInt::one(), m), b.mod_floor(m));
127         }
128 
129         let b: BigInt = b.into();
130         let e: BigInt = e.into();
131         let m: BigInt = m.into();
132         let r: BigInt = r.into();
133 
134         let neg_b_r = if e.is_odd() {
135             (-&r).mod_floor(&m)
136         } else {
137             r.clone()
138         };
139         let neg_m_r = r.mod_floor(&-&m);
140         let neg_bm_r = neg_b_r.mod_floor(&-&m);
141 
142         check(&b, &e, &m, &r);
143         check(&-&b, &e, &m, &neg_b_r);
144         check(&b, &e, &-&m, &neg_m_r);
145         check(&-b, &e, &-&m, &neg_bm_r);
146     }
147 
148     #[test]
test_modpow()149     fn test_modpow() {
150         check_modpow(1, 0, 11, 1);
151         check_modpow(0, 15, 11, 0);
152         check_modpow(3, 7, 11, 9);
153         check_modpow(5, 117, 19, 1);
154         check_modpow(-20, 1, 2, 0);
155         check_modpow(-20, 1, 3, 1);
156     }
157 
158     #[test]
test_modpow_small()159     fn test_modpow_small() {
160         for b in -10i64..11 {
161             for e in 0i64..11 {
162                 for m in -10..11 {
163                     if m == 0 {
164                         continue;
165                     }
166                     check_modpow(b, e, m, b.pow(e as u32).mod_floor(&m));
167                 }
168             }
169         }
170     }
171 
172     #[test]
test_modpow_big()173     fn test_modpow_big() {
174         let b = BigInt::from_str_radix(super::BIG_B, 16).unwrap();
175         let e = BigInt::from_str_radix(super::BIG_E, 16).unwrap();
176         let m = BigInt::from_str_radix(super::BIG_M, 16).unwrap();
177         let r = BigInt::from_str_radix(super::BIG_R, 16).unwrap();
178 
179         check_modpow(b, e, m, r);
180     }
181 }
182