无心人 发表于 2008-12-10 14:03:00

来点简单的，素性测试相关小问题

有素数集合$P$
求素数集合$Q$
使得任何
$q in Q$
$q-1$的素因子均在$P$中，
且$q-1$无平方因子
即有$p_i | q-1, p_i in P$

medie2005 发表于 2008-12-10 14:22:10

没看明白什么意思。
我猜是想考利用p-1的因子分解的素性检验算法。

无心人 发表于 2008-12-10 15:10:52

:)

差不多
不过这个集合真有用途的

medie2005 发表于 2008-12-10 15:20:52

q-1的素因子均在Q中，
且q无平方因子.
=====================
如何理解？
q本身就是素数，自然不含平方因子。
q-1的素因子怎么能在Q中呢？在P中还差不多。

无心人 发表于 2008-12-10 15:50:52

哦
失误失误

已经修改了

medie2005 发表于 2008-12-10 16:07:56

还是不对啊，q-1的素因子怎么能在Q中呢？在P中还差不多。
q-1的素因子全在Q中的话，2在Q中，这样，就要求P中的任何素数p_i|1,这怎么可能？

无心人 发表于 2008-12-10 21:46:40

:L

不好意思了
这两天忙昏头了
好多烂事

似乎没问题了吧

mathe 发表于 2008-12-11 08:48:47

呵呵P的规模有多大呀，这个问题复杂度为$2^P$

无心人 发表于 2008-12-11 11:52:15

先测试下

然后，对前32个素数做个索引表吧

郭先抢 发表于 2012-12-7 20:09:21

什么意思?没明白
页: [1] 2
查看完整版本: 来点简单的，素性测试相关小问题