mathematica 发表于 2012-7-13 14:18:37

大整数的素性判定很简单!

1\大整数的加减乘除
2\整数的模幂的快速算法,针对miller-rabin算法
3\矩阵的模幂的快速算法,针对lucas的算法

如果用mathematica来编程,那么只需要2和3
参见:
(*Miller-Rabin素性判定的mathematica子函数*)
http://bbs.emath.ac.cn/viewthread.php?tid=4433&page=1&fromuid=865#pid44082
(*我自己写的矩阵模幂的myPowerMod的mathematica子函数*)
http://bbs.emath.ac.cn/viewthread.php?tid=4448&page=1&fromuid=865#pid44192

mathematica 发表于 2012-7-13 14:21:32

呵呵,HugeCalc算法似乎在于解决了大整数的加减乘除,
如果我能解决上面的问题,我觉得我自己就能写出大整数的
素性判定了!
当然,我从来没研究过大整数的加减乘除!!!!!!!!
就目前来说,还没有那个需求!
我觉得mathematica软件能够完全满足我的需求!!!!!!!!!

mathematica 发表于 2012-7-13 14:25:34

http://bbs.emath.ac.cn/viewthread.php?tid=4054&page=1&fromuid=865#pid41742
针对lucas的素性判定!!!!!!!!!!!!!!!!!!!!!!!

mathematica 发表于 2012-7-13 14:26:54

没啥了不起!!!!!!!!!!!!!!!!!!!!!

mathematica 发表于 2012-7-13 14:27:14

真的没啥了不起!连我都会!!!!!!!!!!

mathematica 发表于 2012-7-13 14:27:35

哈哈哈

无心人 发表于 2012-11-5 19:32:58

关键是，达到一定位数的大整数，在经过你说的步骤后，只能是无限接近于概率1的近似素数，而不是确定性素数！！

所以，大整数确定性素性测试很难。。。

云梦 发表于 2012-11-6 11:03:18

大整数究竟可以达到多大的数量级？按整数位算是多少位？

只是呼吸 发表于 2013-3-16 12:54:53

大整数究竟可以达到多大的数量级？按整数位算是多少位？
云梦 发表于 2012-11-6 11:03 http://bbs.emath.ac.cn/images/common/back.gif


十进制150位以上。特殊用途的还要多得多，例如在RSA中用到了463位十进制大整数。肯定还有更大的数被应用着。

无心人 发表于 2013-3-16 21:54:34

十进制千位级别的，确定性检验还是可以做到的，不过时间可能很长
页: [1]
查看完整版本: 大整数的素性判定很简单!