| // Calculate the modular inverse of `num`, using Extended GCD. | |
| // | |
| // Reference: | |
| // Brent & Zimmermann, Modern Computer Arithmetic, v0.5.9, Algorithm 1.20 | |
| pub fn inv_mod_u32(num: u32) -> u32 { | |
| // num needs to be relatively prime to 2**32 -- i.e. it must be odd. | |
| assert!(num % 2 != 0); | |
| let mut a: i64 = num as i64; | |
| let mut b: i64 = (u32::MAX as i64) + 1; | |
| // ExtendedGcd | |
| // Input: positive integers a and b | |
| // Output: integers (g, u, v) such that g = gcd(a, b) = ua + vb | |
| // As we don't need v for modular inverse, we don't calculate it. | |
| // 1: (u, w) <- (1, 0) | |
| let mut u = 1; | |
| let mut w = 0; | |
| // 3: while b != 0 | |
| while b != 0 { | |
| // 4: (q, r) <- DivRem(a, b) | |
| let q = a / b; | |
| let r = a % b; | |
| // 5: (a, b) <- (b, r) | |
| a = b; | |
| b = r; | |
| // 6: (u, w) <- (w, u - qw) | |
| let m = u - w * q; | |
| u = w; | |
| w = m; | |
| } | |
| assert!(a == 1); | |
| // Downcasting acts like a mod 2^32 too. | |
| u as u32 | |
| } |