| 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 |
|
| 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] |
| 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] |
| 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] |
| 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 |
|
| 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] |
| 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] |
| 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] |
| 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 |
} |