有几个素性测试的问题向高手请教

海里游

我看有些高手用下面的方法已经实现了测试，所以特来请教。 1、费马素性判定　设n是一个整数。选择一个随机的a满足1＜a＜n－1。如果a^(n－1)≡/ 1 (mod n)，那么n是一个合数。如果a^(n－1)≡1 (mod n)，那么n可能是一个素数。 我想问的是：这个判断怎么实现的。是直接用a^(n－1)和n进行模运算，还是利用的乘法计算再反复取模。 我想：如果直接用a^(n－1)和n进行模运算的话，当n相当大时，设n为百万位，就算a=2，能用2^(n－1)与n进行模运算吗？ 如果用乘法计算再反复取模的话，那要运行多少次呀！一直弄不明白，请高人不要笑话我问的这低级问题。 2 Miller-Rabin素性判定　 若一个数n，分解n－1＝2^k*m，当k的值较小，设k=1，那么奇数m的数字位数也相当于n的位数，选择一个随机数a满足1＜a＜n－1，取a=2,那么用2^m去除以n(n是百万位), 2^m也相当大呀，然后再把余数反复平方，再取模，如果n要相当大,运行的次数也不少哇，这又怎么实现的呢？

mathematica

第二个问题： Modular exponentiation http://en.wikipedia.org/wiki/Modular_exponentiation 其实这个问题你最好问hugecalc的作者，他是最清楚不过的！

海里游

谢谢mathematica 的关注和指点，我也希望郭老师给我点提示，不过你的能力 也不一般那，是不是谦虚不想说。

mathematica

谢谢mathematica 的关注和指点，我也希望郭老师给我点提示，不过你的能力 也不一般那，是不是谦虚不想说。 海里游 发表于 2011-12-3 16:16

素性判定和因数分解是很迷人的两个话题，但是前者基本上解决了，但是后者很难！ 前者用BPSW素性判定加上随机整数的miller-rabin判定就可以了， 后者是非常难的，不要专研了，这个是连郭都不敢专研的！

海里游

mathematica说的对。 但你说素性判定已基本上解决了，我只想知道费马素性检测， 是用2^(n-1)-1和n直接取模计算，还是用乘法完成的， 看有些资料介绍，似乎很容易，不知容易在什么地方，很是好奇。

gxqcn

模幂算法也是比较有学问的算法， 一般是将指数转化成二进制序列，然后从左至右或从右至左扫描（前者更好）， 为了提速，还可结合滑动窗口法，即先进行些预算，拿空间换时间。

海里游

谢谢郭老师的指点，高人就是高人，方法多，不保守，值得尊敬。

medie2005

一般是根据二进制来算，也有根据幂的因子分解来算的。 如果想深入研究，请搜索加法链。

海里游

谢谢高人medie2005 的指点，昨天看了郭老师的方法后，在网上搜了一下， 我搜到一个论文，正好包括了你们这两位高人的算法，使我大概知道了大数 运算的原理，再次对二位高人表示感谢！

sielw

蒙哥马利 模幂运算