欧几里得算法描述 设$$ a = kb + r $$ 得$$ \gcd(a,b) = \gcd(a,r) = \gcd(a, a\pmod b) $$ 证明 设 d = gcd(a,b), 也就是 d|a, d|b有 r = a - kb两边都除 d, r/d = a/d - kb/d = m, 由于m为正整数，所以 d|r得到 d|a, d|b, d|r gcd(a,b) = gcd(a,r)

找到一个正向容易，逆向很难的公式 $$ m^{x} \equiv y\pmod n$$ 设$m$,$n$都是已知的正整数，在知道$x$的情况下计算$y$容易，而只有$y$推算$x$很难 这里得介绍一个公式phi function 记作 φ φ(n) $ 求 1~n 中与 n互素的数的个数 如 φ(8) 在1,2,3,4,5,6,7中，1，3，5，7与8互素，所以 φ(8)= 4 考虑 n为质数，则 φ(n) = n -...