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

无心人 · 发表于 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

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

似乎没问题了吧

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

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

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

先测试下
[2, 3, 5, 7, 11, 13, 17, 19]
然后，对前32个素数做个索引表吧

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

什么意思?没明白

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 来点简单的，素性测试相关小问题