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

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

什么意思?没明白

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

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