数学研发论坛

 找回密码
 欢迎注册
查看: 1602|回复: 9

[分享] 大整数的素性判定很简单!

[复制链接]
发表于 2012-7-13 14:18:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

如果用mathematica来编程,那么只需要2和3
参见:
(*Miller-Rabin素性判定的mathematica子函数*)
/viewthrea ... romuid=865#pid44082
(*我自己写的矩阵模幂的myPowerMod的mathematica子函数*)
/viewthrea ... romuid=865#pid44192
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-13 14:21:32 | 显示全部楼层
呵呵,HugeCalc算法似乎在于解决了大整数的加减乘除,
如果我能解决上面的问题,我觉得我自己就能写出大整数的
素性判定了!
当然,我从来没研究过大整数的加减乘除!!!!!!!!
就目前来说,还没有那个需求!
我觉得mathematica软件能够完全满足我的需求!!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-13 14:25:34 | 显示全部楼层
/viewthrea ... romuid=865#pid41742
针对lucas的素性判定!!!!!!!!!!!!!!!!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-13 14:26:54 | 显示全部楼层
没啥了不起!!!!!!!!!!!!!!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-7-13 14:27:14 | 显示全部楼层
真的没啥了不起!连我都会!!!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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



十进制150位以上。特殊用途的还要多得多,例如在RSA中用到了463位十进制大整数。肯定还有更大的数被应用着。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-3-16 21:54:34 | 显示全部楼层
十进制千位级别的,确定性检验还是可以做到的,不过时间可能很长
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-11-13 12:16 , Processed in 0.056903 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表