On strong pseudoprimes to several bases
On strong pseudoprimes to several bases
复制标题
DOI：
10.1090/s0025-5718-1993-1192971-8
复制
发表时间：
1993-01
影响因子：
2
通讯作者：
G. Jaeschke
中科院分区：
文献类型：
--
作者：
G. Jaeschke
以Y‘k表示所有前k个素数的最小强伪素数为基，确定了5，q6，q7，q8的精确值，并给出了V/9，/Wt，’1的上界.我们讨论了获得这些结果的方法和基本事实。1.借助于强伪PRIMES计算机代数系统的素性检验，例如公理[2]，使用强伪素数来检验整数的素性。这种测试的好处是它们非常有效。缺点是，当整数不限于一定的区间时，它们只是概率检验。为了使这种测试在规定的区间内对整数具有确定性，我们必须知道所需的所谓“强伪伪性测试”的确切数量。为此，我们引入数字V1i，V/2，.。。我们计算其下界和上界。这一节定义并讨论了这些数字；在？2中，我们推导了一些事实，这些事实是寻找数字V/k的界的基础。在？3中，我们讨论了导致我们结果的方法。根据费马的“小定理”，我们知道，当我们对一个有1 0的整数b有bn-1 i1mod n时，n肯定不是素数，当n是一个复合数时，则称n是“以b为底的强伪素数”
With Y'k denoting the smallest strong pseudoprime to all of the first k primes taken as bases we determine the exact values for 5, q6, q7, q8 and give upper bounds for V/9, / W t,' 1 . We discuss the methods and underlying facts for obtaining these results. 1. PRIMALITY TESTS BY MEANS OF STRONG PSEUDOPRIMES Computer algebra systems, as for instance AXIOM [2], use strong pseudoprimes for testing primality of integers. The advantage of such tests is that they are very efficient. The disadvantage is that they are only probabilistic tests when the integers are not restricted to certain intervals. To make such tests deterministic for integers in prescribed intervals, one has to know the exact number of necessary so-called "strong pseudoprimality tests". For this purpose we introduce the numbers V1i, V/2, . .. for which we compute lower and upper bounds. These numbers are defined and discussed in this section; in ?2 we derive some facts which are the basis for finding bounds for the numbers V/k. In ?3 we discuss the methods which led to our results. In view of Fermat's "Little Theorem" we know that n is certainly not a prime when we have bn-1 i 1 mod n for an integer b with 1 0, and when n is a composite number, then n is called a "strong pseudoprime to base b" if either