由 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<<k)  mod n的结果序列只能是如下的形式：
x...x(n-1)1...1 (x表示非1和n-1的数)

p^(n-1) = 1(mod n)是费马测试，通过这个测试的数比通过Miller-Rabin测试的数要多很多。

无心人

多谢
确实是我说错了