这篇文章将会从欧几里得算法开始讲起,之后过渡到扩展欧几里得算法解线性方程,最后介绍中国生于定理.
前几天在看 lucas 定理的时候发现要求 的逆元,然后就看到了一个 的做法发现太神了,虽然想起来是挺简单的
如果给出一个正奇数 n,要判断它是不是素数,有一个最简单暴力的方法,就是从 2 开始一直试到 ,这样的话能保证结果绝对正确,但是,时间复杂度也就是 ,当 n 的规模到达 甚至更高的级别的时候,就不能在可以忍受的时间内看到结果了.尤其是构造 RSA 密码体制时所需要用到的,找一个极大的素数.