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

SAY · 发表于 2024-4-8 18:51:46

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

kutnfeuwunaxo · 发表于 2024-4-8 18:52:00

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

urinowiq · 发表于 2024-4-8 18:52:51

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

isotaztiqotew · 发表于 2024-4-8 18:52:59

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

uahexuk · 发表于 2024-4-8 18:53:49

哦
失误失误

已经修改了

ipeuric · 发表于 2024-4-8 18:54:31

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

epezzaqegazeu · 发表于 2024-4-8 18:54:51

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

似乎没问题了吧

obibohazek · 发表于 2024-4-8 18:55:06

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

anoqejiji · 发表于 2024-4-8 18:55:35

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

oasuoxi · 发表于 2024-4-8 18:56:07

什么意思?没明白

		自动登录	找回密码
密码			立即注册