最少分组方案算法

无心人

这里有个概率问题
假设要测试的数字
被某个小素数整除

要知道大数字做除数
除法时间是大于小数字的

你如何考虑这个问题？

我想是能获得提速
但具体是多少？
有试验结果么？

无心人

我倾向于顺序组合
乱序组合根本达不到目的

因为素数因子的概率是和素数的倒数成正比的
组合大素数和小素数的乘积
将达不到减少运算的效果

gxqcn

以前用的是顺序组合，前172个素数需要分成54组，现在仅需47组。

无心人

我的意思
你组合
3和65537
不如组合3和5的效果好
因为
两者在是素因子的概率上差的太大

gxqcn

我现在明白你表达的意思了。

你说的可能主要大整数进行素性检测时，如何尽快将“伪素数”暴露而剔除出去？
还有一个过程则是在搜索邻近素数时建立一个小型筛相关，如何快速计算大整数除以系列小素数的对应余数？
其实 26# 中描述的算法更多的是在为后者服务。

无心人

我明白了
你想搜索临近素数而不是随机素数
但
恕我直言
RSA的候选素数必须是独立产生的随机数字
且每位二进制都是随机的
才是安全的吧

如果搜索某个数字的下一个素数
我想并不适合RSA素数吧

gxqcn

那你有的碰运气了。

一般的作法是：产生一个随机大数，然后搜索其最邻近（包含其本身）的大素数，
由于“种子”的随机性，得到的大素数也就随机了。

shshsh_0510

原帖由 无心人 于 2008-8-25 17:52 发表
呵呵
你的代码等于在现有理论基础上
得到了本问题的一个上界
而根据理论计算有一个下界
优化的方案的结果应该在之间出现
我想，每次取最小的
能得到别的结果吧？
谁尝试下？
不过可能不如GxQ的结论好

每次取最小效果差很多，我当天试的好像是50组吧，一看和gxq的结果差这么多，就没再试取最大的情况

无心人

知道了

To GxQ
我想，不很严格的RSA加密可以你那么做
但军用强度的可能要实现我的方法了

实际上，我的说法也不正确
应该是预先生成两个N/2 Bit的素数p, q
然后去尝试2 * p * q + 1的素性

gxqcn

那你的 p、q 如何获得？无穷递归下去？
这样使目标区域变小，“随机性”更难保证。

我知道，无心人的目的使想得到“安全素数”：
p、q 为素数；且 p-1,q-1有大素数因子；(p-1,q-1)很小。