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

https://bbs.emath.ac.cn/static/image/smiley/1/smile.gif

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

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

https://bbs.emath.ac.cn/static/image/smiley/1/sweat.gif

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

似乎没问题了吧

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

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

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

先测试下

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

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

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