由 Miller_Rabin 素性测试想到的问题

sunwukong

1、求某个数（比如 10^32 ）之内的卡米切尔数（Carmichael）。 2、求以 n 个素数 P[1]、P[2]、P[3]、……、P[n] 为底的最小的 m 个强伪素数。 3、我们知道：以 2, 3, 7, 61 和 24251 作为底数，那么 10^16 内唯一的强伪素数为 46 856 248 255 981。 那么，给定一个大数 N 以及一个整数 k（k >= 0 ），求一组素数 P[1]、P[2]、P[3]、……、P[n] ，使素数的个数 n 最小，而且以这些素数为底的强伪素数中，在 1 到 N 范围内的强伪素数的个数 <= k。 这些问题有没有复杂度比强搜小的算法？？

mathe

怎样的复杂度算强搜索的呢？ 在链接 http://bbs.emath.ac.cn/viewthrea ... &fromuid=20#pid2063 中给出的求卡米切尔数的算法应该算比强搜复杂度小吧？不过要算大$10^32$以内可能性还是不大。 你说的以P为底的强伪素数是什么？最好先定义一下

无心人

1、论坛有mathe的一个程序，但范围没这么大，应该很费时间 网路上也没这么大范围的数据，10^16内还有的 2、我想应该可做到，但n不能太大的 3、很难吧，我觉得目前只能靠暴力搜索

无心人

另外，以模乘方测试的方法在 广义 菲拨那妾 －－ 录卡死 序列 书里有很详细的叙述 我95年图书馆看到过 现在大概80元能得到复印本

sunwukong

P为底的强伪素数：通过以P为底的 Miller_Rabin 素性测试的合数称作 以 P 为底的强伪素数。 即 p^(n-1) = 1(mod n) 的合数 n 不同的资料有不同的称呼，有的把这个称为伪素数，少了个强字。

无心人

强一般用做通过了比较多的素数为底的测试的伪素数 而且相对这个题目 这种东西不得是素数

medie2005

P为底的强伪素数：通过以P为底的 Miller_Rabin 素性测试的合数称作 以 P 为底的强伪素数。 即 p^(n-1) = 1(mod n) 的合数 n =================================== “通过以P为底的 Miller_Rabin 素性测试的合数称作 以 P 为底的强伪素数”，与“p^(n-1) = 1(mod n) 的合数 n”是不等价的。 通过以P为底的 Miller_Rabin 素性测试的合数称作 以 P 为底的强伪素数，应当对应于： 若n-1=(2^k)*q，则满足：p^(q<<0) mod n，p^(q<<1) mod n，...，p^(q<

无心人

多谢 确实是我说错了