【笔记】Modular Inverse

2019-04-13 16:49发布

站内文章 / 模拟电子
15907 0 1181
扩展欧几里得方法可以求解ax + by = gcd(a, b)，当gcd(a, b) = 1时，ax + by = 1。 ax = 1 (mod b),  x即a的模逆。 by = 1 (mod a)，y即b的模逆。 最简单的模逆运算就是调用扩展欧几里得方法，扩展欧几里得方法见另一篇笔记。 /// /// ^ -1 (mod ) if gcd(, ) = 1。others return -1 /// public static int ModInverse(int value, int modulo) { if (modulo <= 0) throw new ArgumentOutOfRangeException("modulo should be positive"); if (modulo == 1) return 0; var mod = Mod(value, modulo); if (mod == 1) return 1; var result = ExtendedEuclid(mod, modulo); return result[2] == 1 ? Mod(result[0], modulo) : -1; } /// /// (mod ) /// public static int Mod(int value, int modulo) { if (modulo <= 0) throw new ArgumentOutOfRangeException("modulo should be positive"); var remainder = value % modulo; return remainder < 0 ? remainder + modulo : remainder; }

特殊模的模逆

当模为素数时，可以简化扩展欧几里得方法。 /// /// ^ -1 (mod ) /// if is prime。 /// public static int ModInversePrime(int value, int modulo) { if (modulo <= 0) throw new ArgumentOutOfRangeException("modulo should be positive"); var mod = Mod(value, modulo); if (mod == 1) return 1; int u = mod, v = modulo, r = 1, s = 0; while (u != 0) { while (IsEven(u)) { u >>= 1; if (IsEven(r)) r >>= 1; else r = Mid(r, modulo); } while (IsEven(v)) { v >>= 1; if (IsEven(s)) s >>= 1; else s = Mid(s, modulo); } if (u >= v) { u -= v; r -= s; } else { v -= u; s -= r; } } return Mod(s, modulo); } public static int Mid(int left, int right) => ((left ^ right) >> 1) + (left & right);//Dietz's method 当模为2^k时 /// /// ^ -1 (mod ) /// if is odd and is power of 2。 /// public static int ModInversePowerOf2(int value, int modulo) { if (modulo <= 0) throw new ArgumentOutOfRangeException("modulo should be positive"); if (!IsPowerOf2((uint)modulo)) throw new ArgumentOutOfRangeException("modulo should be power of 2"); if (IsEven(value)) throw new ArgumentOutOfRangeException("value should be odd"); var mod = Mod(value, modulo); if (mod == 1) return 1; var k = modulo.NumberOfTrailingZeros(); var bits = new int[k]; var tmp = 1; for(var i = 0; i < k; ++i) { bits[i] = tmp & 1; tmp = (tmp - bits[i] * mod) >> 1; } var str = new string(bits.Select(num => num == 1 ? '1' : '0').Reverse().ToArray()); return Convert.ToInt32(str, 2); } /// /// 二进制尾数0的个数 /// public static int NumberOfTrailingZeros(this int n) { if (n == 0) return 32; var c = 31; var t = n << 16; if (t != 0) { c -= 16; n = t; } t = n << 8; if (t != 0) { c -= 8; n = t; } t = n << 4; if (t != 0) { c -= 4; n = t; } t = n << 2; if (t != 0) { c -= 2; n = t; } t = n << 1; if (t != 0) { c -= 1; } return c; } /// /// return true if n is power of 2 /// public static bool IsPowerOf2(uint n) => n < 1u ? false : (n & (n - 1)) == 0u; public static bool IsEven(int n) => (n & 1) == 0;    

热门文章