数学研发论坛

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

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

[复制链接]
 楼主| 发表于 2010-7-8 16:38:48 | 显示全部楼层
继续优化函数
*Primes List> let m1 p = map (\x -> m2 x 8 p) [1..p-1]
*Primes List> let m2 p = filter (\x -> not (any (==0) x)) (m1  p)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 16:45:00 | 显示全部楼层
结论
7 = {2, 4, 5, 6}
11 = {1, 3, 10}
13 = {1, 2, 3, 7, 12}
即可,再大的素数候选就太多了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 16:46:52 | 显示全部楼层
下面是100内素数p满足条件的模的可能个数
[(3,1),(5,1),(7,4),(11,3),(13,5),(17,9),(19,11),(23,15),(29,21),(31,26),(37,29),
(41,33),(43,35),(47,39),(53,45),(59,51),(61,53),(67,59),(71,63),(73,65),(79,71),
(83,75),(89,81),(97,89)]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 16:55:47 | 显示全部楼层
对于搜索连续长度为10以上的素数,我们只需要搜索形式如2*3*5*11*k-1的素数。
而如果搜索长度为12以上的,只需要搜索形式如2*3*5*11*13*k-1的素数
mathe 发表于 2010-7-8 15:29


根据 36# mathe 的推导,27# 还可进一步加强为:
对于搜索连续长度为10以上的素数,我们只需要搜索形式如2^10*3*5*11*k-1的素数。
而如果搜索长度为12以上的,只需要搜索形式如2^12*3*5*11*13*k-1的素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 16:58:58 | 显示全部楼层
*Primes List> let is7 n = any (==(mod n 7)) [2,4,5,6]
*Primes List> let is11 n = any (==(mod n 11)) [1, 3, 10]
*Primes List> let is13 n = any (==(mod n 13)) [1, 2, 3, 7, 12]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 17:00:48 | 显示全部楼层
根据  36# mathe  的推导,27# 还可进一步加强为:

gxqcn 发表于 2010-7-8 16:55

这个结论不成立
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 17:05:11 | 显示全部楼层
我是这样想的:
对于连续长度为10以上的素数,这个数必须为 2^10*t-1 型,又同时得为 2*3*5*11*k-1 型,此时必须 2^9|k,
所以才有上述加强的说法,不知哪里不对?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 17:10:38 | 显示全部楼层
是不成立
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-7-8 17:13:42 | 显示全部楼层
$(2^10t-1)(Mod P)$未必是$2^10t-1$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2010-7-8 17:22:04 | 显示全部楼层
放弃计算了,只能用C/C++了
haskell计算候选素数,就N慢了
不过,筛选的就已经很少了
大概2000左右才有一个
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

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

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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