modular_arithmetic/
arithmetic.rs

1use std::u64;
2use std::i64;
3
4
5pub fn mod_add(a:u64, b:u64, q:u64) -> u64 {
6	let a0 = a % q;
7	let b0 = b % q;
8	let sum = a0.checked_add(b0);
9	match sum {
10		Some(x) => x % q,
11		None => slow_add(a0,b0,q)
12	}
13}
14
15pub fn mod_abs(a: i64, q: u64) -> u64 {
16	let mut abs_a = a;
17	while abs_a < 0 {
18		abs_a += q as i64;
19	}
20	abs_a as u64
21}
22
23pub fn mod_sub(a: i64, b: i64, modulus: u64) -> u64 {
24	mod_add(mod_abs(a,modulus), mod_abs(b, modulus), modulus)
25}
26
27
28//assumes a,b < q
29fn slow_add(a:u64, b:u64, q:u64) -> u64 {
30	if a > b {
31		let neg_b = q -b;
32		a - neg_b
33	} else {
34		let neg_a = q - a;
35		b - neg_a
36	}
37}
38
39
40pub fn mod_mul(a:u64, b:u64, q:u64) -> u64 {
41	let a0 = a % q;
42	let b0 = b % q;
43	let prod = a0.checked_mul(b0);
44	match prod {
45		Some(x) => x % q,
46		None => slow_mul(a0, b0, q)
47	}
48}
49
50fn slow_mul(a:u64, b:u64, q:u64) -> u64 {
51	let mut total = 0;
52	for _ii in 0..b {
53		total = mod_add(total, a, q);
54	}
55	total 
56}
57
58pub fn mod_exp(base :u64, exponent :u64, q:u64) -> u64 {
59	if exponent == 0{
60		return 1
61	}
62
63	let reduced_base = base % q;
64	let mut current_state = reduced_base;
65
66	for _i in 0..exponent-1 {
67		current_state = mod_mul(current_state, reduced_base, q);
68	}
69	current_state
70}
modular_arithmetic/arithmetic.rs

modular_arithmetic/
arithmetic.rs
