素性测试:A Survey

素性测试:A Survey

素数

素数(Prime number),又称质数,指在大于1的自然数中,除了1和该数自身之外,无法被其他自然数整除的数。大于1的自然数,若不是素质,则为合数。前十个素数分别是:2、3、5、7、11、13、17、19、23、29。

RSA加密是现在网络安全系统中非常常用的一种非对称加密方法,这种方法的安全性依赖于大数质因子分解非常困难。

任何一个大于1的自然数都可以表示成素数乘积的形式,并且如果将素数按顺序写出来,这个表示方法是唯一的,这被称为算数基本定理。比如,60=223*5。将自然数表示成素数乘积的过程叫做质因子分解,可以用来判断一个数是不是素数。另外,还有一些方法可以在不进行质因子分解就能知道一个数字是不是素数,这些方法可以分为两类,分别是随机的和确定的。随机方法不一定能保证通过测试的一定是素数,只能保证通过检验的数很大可能上是一个素数。而确定的则可以完全保证通过测试的数字是一个素数。

下面我们具体研究各种判断素数的方法。

阅读更多
牛客练习赛-53B
2019-ICPC-南京网络赛
BZOJ-2956-模积和
拉格朗日乘数法

拉格朗日乘数法

简单来说,拉格朗日乘子法可以解决$f(\hat x)$在一些限制条件$g_k(\hat x) = c_k$下的极值。

阅读更多
Codeforces-622-F