能通过2，3，5，7的检验的合数

mathe

看来合数的不好. 对于求解某个底a的一定范围内所有奇伪素数 我们知道,这个伪素数N一定满足$a^{N-1}=1(mod N)$ 所以我们可以用这个作为一个最初的筛选条件. 我们先指定一个范围M(比如M=$10^8$) 对于M以内所有同a互素的素数的幂b,我们计算a关于b的最小指数$r(a,b)$,也就是$a^{r(a,b)}=1(mod b)$,而且这个数值要求最小. 然后我们假设伪素数$N=p_1*p_2*...*p_t*q$ 其中$p_1,p_2,...,p_t$都是M以内的素数的幂,q为大于M的素数幂的乘积,而且它们都互素(q可以同前面某些$p_i$有公因子. 那么我们可以得到表达式$N=1(mod LCM(r(a,p_1),r(a,p_2),...,r(a,p_t)))$, 对于给定的$p_1,p_2,...,p_t$,我们基本可以非常容易判断所有可能的q的值了(除了$p_1*p_2*...*p_t$很小的时候) 所以对于我们来说,最麻烦的对象是那些一个大素数乘上小因子的情况

mathe

对于小因子b乘上大素数Q的情况 假设 N=b*Q是伪素数，我们知道 $a^{Q-1}=1(mod Q)$ $a^{b*Q-1}=1(mod Q)$ 由此得出 $a^{(b*Q-1,Q-1)}=1(mod Q)$ 由此得出 $a^{(b-1,Q-1)}=1(mod Q)$ 得出 $a^{b-1}=1(mod Q)$ 也就是 Q是$a^{b-1}-1$的因子，在a和b都不是太大的时候，特别是a是2,b也不算太大时应该能够确定可能的Q.

mathe

所以如果b*Q是一个关于底2和3的伪素数,而且Q为素数,那么我们可以知道 $Q|(2^{b-1}-1,3^{b-1}-1)$

medie2005

那如果是n=p*q，p,q接近的时候呢？如何处理？

无心人

应该 $p | a^(q - 1) - 1$ $q | a^(p - 1) - 1$ 吧

无心人

安徽芜湖 安徽师范大学 张振祥 这个人是我知道的国内作计算数论的 也许能联系他获得些资料

mathe

76#的结论不大好用,我觉得这个时候用72#的结果比较好

无心人

http://zhangzhx.ik8.com/Cindex.htm 是否有必要拉这个人来看看？ 呵呵

medie2005

呵呵，我觉得没必要。 他有两篇论文： Finding strong pseudoprimes to several bases Finding strong pseudoprimes to several bases II 我有第一篇，大家可以参考一下。

无心人

我是说，拉来好不好 如果好，我就拉来了