数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[讨论] 郭有没有兴趣做出一个确定性的素性检测函数

[复制链接]
 楼主| 发表于 2010-7-8 16:05:59 | 显示全部楼层
肯定是10k - 1形式的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 16:08:42 | 显示全部楼层
你说的是30 k - 1
下面依次可以考虑7, 11, 13, 17, 19素数的模
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 16:09:09 | 显示全部楼层
我的方法可以改善到30k-1
另外,我们还可以要求模7为{2,4,5,6}之一
同样还可以对模11进行处理,显然余数10是可以的,但是对于其他非0余数,我们还需要判断一下,有多少个8次以内不会到达0(只有两个),所以模11比模7更加高效
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 16:09:24 | 显示全部楼层
8链起始素数很可能大于10^8的
我搜索不完全
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 16:16:42 | 显示全部楼层
只需要搜索1/30,如果在使用模7和模11,大概可以接近到1/200,这个数据量应该是可以忍受的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 16:19:17 | 显示全部楼层
暴力搜索到2329469的,是没有8序列的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 16:28:45 | 显示全部楼层
7 = {2, 4, 5, 6}
11 = {1, 3, 10}
13 = {1, 2, 3, 7, 12}
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 16:29:55 | 显示全部楼层
Haskell测试代码
let m2 n i p = take i (iterate (\x ->mod (x * 2 + 1) p) n)
*Primes List> map (\x -> m2 x 8 11) [1..10]
[[1,3,7,4,9,8,6,2],[2,5,0,1,3,7,4,9],[3,7,4,9,8,6,2,5],[4,9,8,6,2,5,0,1],[5,0,1,
3,7,4,9,8],[6,2,5,0,1,3,7,4],[7,4,9,8,6,2,5,0],[8,6,2,5,0,1,3,7],[9,8,6,2,5,0,1,
3],[10,10,10,10,10,10,10,10]]
*Primes List> map (\x -> m2 x 8 13) [1..12]
[[1,3,7,2,5,11,10,8],[2,5,11,10,8,4,9,6],[3,7,2,5,11,10,8,4],[4,9,6,0,1,3,7,2],[
5,11,10,8,4,9,6,0],[6,0,1,3,7,2,5,11],[7,2,5,11,10,8,4,9],[8,4,9,6,0,1,3,7],[9,6
,0,1,3,7,2,5],[10,8,4,9,6,0,1,3],[11,10,8,4,9,6,0,1],[12,12,12,12,12,12,12,12]]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 16:33:27 | 显示全部楼层
*Primes List> map (\x -> m2 x 8 17) [1..16]
[[1,3,7,15,14,12,8,0],[2,5,11,6,13,10,4,9],[3,7,15,14,12,8,0,1],[4,9,2,5,11,6,13
,10],[5,11,6,13,10,4,9,2],[6,13,10,4,9,2,5,11],[7,15,14,12,8,0,1,3],[8,0,1,3,7,1
5,14,12],[9,2,5,11,6,13,10,4],[10,4,9,2,5,11,6,13],[11,6,13,10,4,9,2,5],[12,8,0,
1,3,7,15,14],[13,10,4,9,2,5,11,6],[14,12,8,0,1,3,7,15],[15,14,12,8,0,1,3,7],[16,
16,16,16,16,16,16,16]]
19的
[[1,3,7,15,12,6,13,8],[2,5,11,4,9,0,1,3],[3,7,15,12,6,13,8,17],[4,9,0,1,3,7,15,1
2],[5,11,4,9,0,1,3,7],[6,13,8,17,16,14,10,2],[7,15,12,6,13,8,17,16],[8,17,16,14,
10,2,5,11],[9,0,1,3,7,15,12,6],[10,2,5,11,4,9,0,1],[11,4,9,0,1,3,7,15],[12,6,13,
8,17,16,14,10],[13,8,17,16,14,10,2,5],[14,10,2,5,11,4,9,0],[15,12,6,13,8,17,16,1
4],[16,14,10,2,5,11,4,9],[17,16,14,10,2,5,11,4],[18,18,18,18,18,18,18,18]]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 16:35:37 | 显示全部楼层
17 = {2, 4, 5, 6, 9, 10, 11, 13, 16}
19 = {1, 3, 6, 7, 8, 12, 13, 15, 16, 17, 18}!!!!!!!!!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-10-27 12:11 , Processed in 0.054303 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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