for Lucas pseudoprimes ]]> The Rabin-Monier theorem for Lucas pseudoprimes F. Arnault arnault@unilim.fr Arnault_F with $0\le P,Q<n$ such that a composite number $n$ is a strong Lucas pseudoprime with respect to the parameters $(P,Q)$.

]]> We give bounds on the number of pairs with such that a composite number is a strong Lucas pseudoprime with respect to the parameters . 1 F. Arnault, Rabin-Miller primality test: Composite numbers which pass it , Math. Comp. 64 (1995), 355--361. 95c:11152 2 , Constructing Carmichael numbers which are strong pseudoprimes to several bases , J. Symbolic Comput. 20 (1995), 151--161. 96:08 3 F. Arnault and G. Robin, Sur une fonction associee aux entiers quadratiques , Preprint. 4 R. Baillie and S. Wagstaff, Jr., Lucas pseudoprimes , Math. Comp. 35 (1980), 1391--1417. 81j:10005 5 G. Jaeschke, On strong pseudoprimes to several bases , Math. Comp. 61 (1993), 915--926. 94d:11004 6 Z. Mo and J. P. Jones, A new probabilistic primality test using Lucas sequences , Preprint. 7 L. Monier, Evaluation and comparison of two efficient primality testing algorithms , Theoret. Comput. Sci. 11 (1980), 97--108. 82a:68078 8 C. Pomerance, J. L. Selfridge, and S. S. Wagstraff, The pseudoprimes to 2510 9 , Math. Comp. 35 (1980), 1003--1026. 82g:10030 9 M. O. Rabin, Probabilistic algorithms for testing primality , J. Number Theory 12 (1980), 128--138. 81f:10003 10 H. C. Williams, On numbers analogous to the Carmichael numbers , Canad. Math. Bull. 20 (1977), 133--143. 56:5414

1.
F. Arnault, Rabin-Miller primality test: Composite numbers which pass it, Math. Comp. 64 (1995), 355-361. MR 95c:11152

2.
-, Constructing Carmichael numbers which are strong pseudoprimes to several bases, J. Symbolic Comput. 20 (1995), 151-161. CMP 96:08

3.
F. Arnault and G. Robin, Sur une fonction associée aux entiers quadratiques, Preprint.

4.
R. Baillie and S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), 1391-1417. MR 81j:10005

5.
G. Jaeschke, On strong pseudoprimes to several bases, Math. Comp. 61 (1993), 915-926. MR 94d:11004

6.
Z. Mo and J. P. Jones, A new probabilistic primality test using Lucas sequences, Preprint.

7.
L. Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoret. Comput. Sci. 11 (1980), 97-108. MR 82a:68078

8.
C. Pomerance, J. L. Selfridge, and S. S. Wagstraff, The pseudoprimes to $25\cdot 10^9$, Math. Comp. 35 (1980), 1003-1026. MR 82g:10030

9.
M. O. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128-138. MR 81f:10003

10.
H. C. Williams, On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), 133-143. MR 56:5414
]]> 1997 American Mathematical Society Mathematics of Computation of the American Mathematical Society Math. Comp. mcom 66 218 19970401 August 30, 1994 February 28, 1995 and November 6, 1995 Primality testing Lucas pseudoprimes. 869 869-881 13 S0025-5718-97-00836-3 10.1090/S0025-5718-97-00836-3 0025-5718 1088-6842 English 11Y11 11A51 11R11 1991 http://www.ams.org/jourcgi/jour-getitem?pii=S0025-5718-97-00836-3 Introduction Pseudoprimes, strong pseudoprimes It is well known that if n is a prime number, then it satisfies one of the following relations, where n-1 2 kq with q odd. equation 1 split b q1 modulo n or there exists an integer i such that 0i k and b 2 iq -1 modulo n . split equation This property is often used as a primality test'', called the Rabin-Miller test, which consists in checking if the property 1 holds, for several bases b . If 1 does not hold for some b , then n is certainly composite. If 1 is found to be true when trying several bases (usually 10 or 20), then n is likely to be prime. Composite numbers which satisfy the condition 1 are called strong pseudoprimes with respect to the base b . For short spsp (b) . By recent results, it is possible to build composite numbers which satisfy 1 for several chosen bases b (see 1, 2, 5). So, when one knows the bases used by a given implementation of the Rabin-Miller test, one can find composite numbers which this test finds to be prime. However, it is possible to give upper bounds for the probability that this test will give an incorrect answer. The main result in this direction is the Rabin-Monier theorem. thm Rabin-Monier thm:1.1 Let n be a composite integer distinct from 9 . The number of bases b such that 0 b n , which are relatively prime to n and for which n is a (b) is bounded by (n) 4 , where is the Euler function. thm Lucas pseudoprimes Let P and Q be integers and D P 2-4Q . For n integer, we denote by (n) the Jacobi symbol (D n) . The Lucas sequences associated with the parameters P,Q are defined by cases U 0 0, U 1 1, V 0 2, V 1 P, cases and, for k0, cases U k 2 PU k 1 -QU k, V k 2 PV k 1 -QV k. cases We have the following result, which can be compared with the criterion 1: thm Let p be a prime number not dividing 2QD . Put p-(p) 2 kq with q odd. One of the following conditions is satisfied: equation split p U q or there exists i such that 0i k and p V 2 iq . split equation thm A composite number n relatively prime to 2QD and satisfying equation 2 split n U q or there exists i such that 0i k and p V 2 iq , split equation where we have put n-(n) 2 kq with q odd, is called a strong Lucas pseudoprime with respect to the parameters P and Q . For short we write n is an (P,Q) . As above, we can derive a test'' from this property: the strong Lucas pseudoprime test 4. In this test, we check whether property 2 holds, for several pairs (P,Q) . The main result The main purpose of this paper is to prove the following theorem, which is the analog of Theorem thm:1.1 but for strong Lucas pseudoprimes. thm thm:1.3 Let D be an integer and n a composite number relatively prime to 2D and distinct from 9 . For all integer D , the size equation (D,n) (P,Q) matrix 0P,Q n, P 2-4QD modulo n, (Q,n) 1, n is (P,Q) matrix . equation is less than or equal to 4 15 n except if n is the product n (2 k 1 q 1-1)(2 k 1 q 1 1) of twin primes with q 1 odd and such that the Legendre symbols satisfy (D 2 k 1 q 1-1) -1 , (D 2 k 1 q 1 1) 1 . Also, the following inequality is always true: (D,n)n 2. thm The Monier formula and its analog A result close to Theorem thm:1.1 was first shown by Rabin 9. But Monier 7 gave the following formula and used it to prove Theorem thm:1.1 . thm Monier thm:1.4 Let p 1 r 1 p s r s be the prime decomposition of an odd integer n 0 . Put equation cases n-1 2 kq, p i-1 2 k i q i for 0is, cases with q,q i odd , equation ordering the p i 's such that k 1k s . The number of bases b such that n is an (b) is expressed by the following formula B(n) (1 j 0 k 1-1 2 js ) i 1 s(q,q i). thm Similarly, we will first prove, in Section sec:4 , an analogous formula for the Lucas test. thm thm:1.5 Let D be an integer and let p 1 r 1 p s r s be the prime decomposition of an integer n 2 relatively prime to 2D . Put equation cases n-(n) 2 kq, p i-(p i) 2 k i q i for 1is, cases with q,q i odd , equation ordering the p i 's such that k 1k s . The number of pairs (P,Q) with 0P,Q n , (Q,n) 1 , P 2-4QD modulo n and such that n is an (P,Q) is expressed by the following formula (D,n) i 1 s((q,q i)-1) j 0 k 1-1 2 js i 1 s(q,q i). thm Some lemmas We start with three lemmas. The first two will be used to prove Theorem thm:1.5 , and the last to prove Theorem thm:1.3 . Roots in a cyclic group lem lem:2.1 Let G be a cyclic group and q an integer. (a) There are exactly (q, G ) q th-roots of 1 in G . (b) An element y of G is a q th-power if and only if y G (q, G ) 1. In this case, y has exactly (q, G ) q th-roots in G . lem proof Put d (q, G ) . The proof of (a) is easy if we see, using Bezout relations, that for xG , x q 1x d 1. Also, the q th-powers in G are the d th-powers. But, y is a d th-power if and only if y G d 1 . To count the q th-roots of y whenever such a root exists, we remark that we can obtain the others from it by multiplying it by a q th-root of 1. proof Congruences in some rings lem lem:2.2 Let O be a ring extension of Z and ,O . Let also p be a prime ideal in O , r1 be an integer, and kpZ . One has the implication modulo p k r-1 k r-1 modulo p r. lem proof If -p , then equation split k- k (-)( k-1 k-2 k-1 ) (-)( k-1 k-1 k-1 ) modulo p (-)k k-1 p 2. split equation This shows the assertion when r 2 . An easy induction concludes the proof. proof The D function Let D be an integer and let (n) denote the Jacobi symbol (D n) . For convenience, we introduce the following number-theoretic function, studied in 3 and defined only on integers relatively prime to 2D : cases D(p r) p r-1 (p-(p)) for any prime p2D, and rN , D(n 1n 2) D(n 1) D(n 2) for n 1 and n 2 relatively prime . cases lem lem:2.3 Let D be an integer. For n 0 relatively prime to 2D , we have D(n)(43) sn where s is the number of distinct prime factors of n . Also, we have the particular cases: equation split s 2 D(n)85n, s 3 D(n) 64 35 n, s4 D(n) 768 385 ( 14 13 ) s-4 n. split equation lem proof For the first part of the result, it is sufficient to handle the case where n p r is an odd prime power such that pD . Then we have D(p r) p r p r-1 (p-(p)) p r 1-(p) p1 1 p4 3 and the result follows. The proof of the second part is similar, using the knowledge that p i5 for all but perhaps one subscript i,p i7 for all but perhaps two subscripts i,p i11 for all but perhaps three subscripts, and p i13 for all but perhaps four subscripts. proof Connection with quadratic integers Let P,Q be integers such that D P 2-4Q 0 and consider the Lucas sequences (U n) and (V n) associated with P,Q . It is easy to see that we have the relations equation 4 U k k- k - ,V k k k, for all kN, equation where , are the two roots of the polynomial X 2-PX Q . Also, if n is an integer relatively prime to 2QD , we can put -1 modulo nO . Then we have the following equivalences, for kN , equation split n U k k1 modulo n, n V k k-1 modulo n. split equation Hence, if n is composite and relatively prime to 2QD , it is an (P,Q) if and only if equation split q1 modulo n or there exists i such that 0i k and 2 iq -1 modulo n , split equation where n-(n) 2 kq with q odd. Norm 1 elements Let O be the ring of integers of a quadratic field Q() . The norm in Q() is the map N defined by N(u v) u 2-Dv 2Q (u,vQ) . For z in O , the norm N(z) is in Z . For a rational integer n , the ring O n is a free (Z nZ) -algebra of rank 2. We consider, in this algebra, the multiplicative group of norm 1 elements, which we denote by (O n) . In other words, (O n) is the image of the set xO N(x)1 modulo n by the canonical map OO n . The proof of Theorem thm:1.5 will be similar to Monier's proof, but will use the following result on the structure of the group (O n) , which is proved in 3. thm thm:3.1 Let p2D be a prime number and r1 an integer. The group (O p r) is cyclic of order p r-1 (p-(D p)) . thm The link between the parameters P,Q and the norm 1 elements is described by the following result: prp prp:3.2 Let D be an integer, but not a perfect square and O be the ring of integers in Q() . Let n be an integer relatively prime to 2D . Then, for all integers P , there exists an integer Q , uniquely determined modulo n , such that P 2-4QD modulo n . Moreover, the set of integers P such that cases 0P n, (P 2-D,n) 1 ( i.e. (Q,n) 1), cases is in a one-to-one correspondence with the elements in (O n) such that -1 is a unit in O n . This correspondence is expressed by the following formulas equation 5 cases (P )(P-) -1 P( 1)(-1) -1 cases modulo nO. equation prp proof The first claim is easy, as n is odd. Then, we observe that -1 and are conjugate in O n . So putting u ( 1)(-1) -1 , we have equation split u-v ( 1)(-1) -1 -( -1 1)( -1 -1) -1 modulo n -(1 )(1-) -1 ( 1)(-1) -1 u v. split equation As n is odd, we obtain v0 modulo n . So the second equation in 5 is satisfied by a rational integer. Then we leave to the reader the task of showing that the two relations 5 are equivalent to each other. proof Remark on the square discriminant case If D is a non-zero perfect square it is well known that the strong Lucas test reduces to the Rabin-Miller test. It is interesting to clarify this fact. If n is an integer relatively prime to 2D , we can put T -1 modulo n (this time, , are rational integers). From 4 we have the following equivalences, for kN : n U kT k1 modulo n,n V kT k-1 modulo n. So n is an (P,Q) if and only if it is an (T) . Moreover, the proof of Proposition prp:3.2 could very easily be adapted to show that there exists a one-to-one correspondence between the sets P array l0P n (P 2-D,n) 1 array . and T array l0T n (T,n) (T-1,n) 1 array . . Hence, the proof of Theorem thm:1.4 given by Monier could easily be adapted to prove Theorem thm:1.5 in this special case where D is a perfect square. Proof of Theorem thm:1.5 sec:4 The difference between consecutive perfect squares d 2 and (d 1) 2 tends to as d tends to . So the integers D kn with kZ cannot all be perfect squares. Because (D,n) is equal to (D kn,n) for all integer k , we can assume in the proof that D is not a perfect square. We denote by O the ring of integers of the field Q() . Proposition prp:3.2 shows that we have to count the number of elements in the sets gather X(n) (O n) 1-(O n) , q 1 , Y j(n) (O n) 1-(O n) , 2 jq -1 , for 0jk-1, gather because their sum is (D,n) . Using the Chinese Remainder Theorem, we reduce the problem to counting the sets X(p i r i ) and Y j(p i r i ) . Count of X(p i r i ) We first count X(p i r i ) . By Theorem thm:3.1 , the number of q th-roots of 1 in the group (O p i r i ) is equation split d (q,p i r i-1 (p i-(p i))) (q,p i-(p i)) since q is relatively prime to n , (q,q i) -(p i) since q is odd . split equation From these roots, we must throw away those such that 1- is not invertible modulo p i . We show that the only such is the trivial root 1. Indeed, note that cases n-(n) 1 p i r i-1 (p i-(p i)) 1 cases d1 p i-(p i) 1 modulo p i r i O. Let p be a prime ideal of O containing p iO . For k1 integer, we have equation split 1 modulo p k p i 1 modulo p k 1 by Lemma lem:2.2 , 1 p i-(p i) -(p i) modulo p k 1 1 modulo p k 1 . split equation So, by induction, 1- is not a unit modulo p r i . If p i splits in O , this implies 1 modulo p r i (as -1 ) . In both cases (inertial or split), we obtain 1 modulo p i r i . Hence, the number of elements in X(p i r i ) is d-1 (q,q i)-1. Hence, X(n) i 1 s((q,q i)-1). Count of Y j(p i r i ) We now count Y j(p i r i ) . Here, the invertibility condition for 1- modulo p i does not throw away any solution. Indeed, as p i is odd we cannot have, for p a prime ideal containing p iO , 1 1 2 jq 2 jq -1 modulo p. By Lemma lem:2.1 , we have Y j(p i r i ) cases 0 if jk i, (2 jq, D(p i r i )) 2 j(q,q i) if j k i. cases Lastly, the equality (D,n) X(n) j 0 k-1 Y j(n) completes the proof because, as n(n) modulo 2 k 1 (as p i(p i) modulo 2 k 1 for all i) , we have k 1k . First consequences Following the usual proof 7 of the Rabin-Monier theorem, we would easily obtain cor If n is an odd composite integer, then (D,n) D(n) 4. cor But, as the function D(n) is not bounded by n (see 3 for more details), this result is not of the same interest as Theorem thm:1.3 . In fact, using Proposition prp:3.2 , one can show, if p 1 r 1 p s r s is the prime decomposition of n , that the size (P,Q) matrix 0P,Q n,P 2-4QD modulo n, (Q,n) 1 matrix . is i 1 s p i r i-1 (p i-(p i)-1). This size is less than n and is equal to it infinitely many times. So it seems quite natural to try to bound (D,n) by kn for some constant k . lem lem:5.2 Let p 1 r 1 p s r s be the prime decomposition of an integer n relatively prime to 2D . With the notations k,q,k i,q i of Theorem thm:1.5 , we have the inequalities (D,n) D(n) cases 1 2 s-1 i 1 s (q,q i) q i , 1 2 s-1 i 1 s1 p i r i-1 , 1 2 s-1 2 s where i k i-k 1. cases lem proof We follow the proof of the very similar statement by Monier 7. We have D(n) 2 k 1 k s i 1 s q i i 1 s p i r i-1 so, by Theorem thm:1.5 , equation 6 (D,n) D(n) 1 j 0 k 1-1 2 js 2 k 1 k s i 1 s (q,q i) q i i 1 s 1 p i r i-1 . equation But the left-hand factor of 6 is bounded by equation split 1 j 0 k 1-1 2 js 2 sk 1 1 (2 sk 1 -1) (2 s-1) 2 sk 1 (1 2 sk 1 2 s-1 -1 2 s-1 ) 2 sk 1 (1-1 2 s-1 ) 2 sk 1 1 2 s-1 . split equation The last formula shows that this is a decreasing function of k 1 . So we can bound it by its value at k 1 1 : equation 7 1 j 0 k 1-1 2 js 2 sk 1 1 2 s-1 . equation The first two inequalities follow from this. The last also follows from 7, using the equality 1 j 0 k 1-1 2 js 2 k 1 k s 1 j 0 k 1-1 2 js 2 sk 1 1 2 2 s . proof Proof of Theorem thm:1.3 As in Theorem thm:1.5 , we use the following notation: Let p 1 r 1 p s r s be the prime decomposition of n and put equation cases n-(n) 2 kq, with q,q i odd . p i-(p i) 2 k i q i for 1is, cases equation The case s 1 First, consider the case s 1 . The second inequality of Lemma lem:5.2 shows that (D,n)1 p 1 r 1-1 D(n). If p 15 we obtain, as r 12 , (D,n) D(n) 5. In this case, Lemma lem:2.3 implies (D,n)(4 3)n 5 (4 15)n . If p 1 3 , a similar argument holds, because we assume n 9 . The case s 2 Now, the case s 2 . By the second part of Lemma lem:2.3 , it is sufficient to show that we have equation 8 (D,n)16 D(n). equation But, Lemma lem:5.2 gives (D,n) D(n) cases 1 6 if r i2 for at least some i, 1 8 if 2 k 2-k 12, cases which is sufficient to prove the assertion in both cases. So we can assume that r 1 r 2 1 (n p 1p 2) and 2 k 2-k 1 0 or 1. First, we consider the subcase where q 1 q 2 . Then the first inequality of Lemma lem:5.2 shows that (D,n) D(n) 12 (q,q 1) q 1 (q,q 2) q 2 . Here, we point out that at least one of the ratios (q,q i) q i is bounded by 1 3. Otherwise, they would both be 1 and then both q 1 and q 2 would divide q . Also equation split 2 kq p 1p 2-(p 1p 2) (2 k 1 q 1 (p 1))(2 k 1 2 q 2 (p 2))-(p 1p 2) 2 2k 1 2 q 1q 22 k 1 (q 12 2 q 2). split equation We would then have q 1 q 2 and q 2 q 1 , contradicting the hypothesis q 1 q 2 . Hence, if q 1 q 2 , then (D,n) D(n) 1 6 and equation 8 is satisfied. So we can suppose that r 1 r 2 1 (n p 1p 2) , 2 k 2-k 1 equals 0 or 1, and that q 1 q 2 . If 2 1 , the integer n is equation split n (2 k 1 q 11)(2 k 1 1 q 11) with q 1 odd (2 k 1 q 1-1)(2 k 1 1 q 1-1) 2(2 k 1 q 1) 2-3(2 k 1 q 1) 1. split equation Hence, 8(2 k 1 q 1) 2-12(2 k 1 q 1) 44n . We have also 2 kq n-(n) 2(2 k 1 q 1) 2 (2(p 1) (p 2))(2 k 1 q 1) and so, q 1 divides q . Here, Theorem thm:1.5 gives equation 9 split (D,n) (q 1-1) 2 (1 4 4 k 1-1 )q 1 2 (q 1-1) 2 4 k 1 -1 3q 1 2 4 k 1 2 3q 1 2. split equation Hence, 15(D,n)5(2 k 1 q 1) 2 10q 1 2 . We distinguish the subcase k 1 1 from the one where k 12 . If k 12 we have 10q 1 2 (2 2q 1) 2(2 k 1 q 1) 2 . Hence, equation split 4n-15(D,n) 3(2 k 1 q 1) 2-10q 1 2-12(2 k 1 q 1) 4 2(2 k 1 q 1) 2-12(2 k 1 q 1) 4 2((2 k 1 q 1) 2-6(2 k 1 q 1) 2). split equation The roots of this polynomial are less than 6. So it is positive as soon as 2 k 1 q 16 . As k 12 , the only possibility in this case is 2 k 1 q 1 4 , which implies k 1 2 and q 1 1 so that p 1 3 or 5, and p 2 2 k 1 1 q 11 7 or 9, so that n 21 or 35, and (D,n) 5 . In the other subcase (k 1 1) , 2 1 and hence k 2 2 and therefore equation cases n(2q 1-1)(4q 1-1) with q 1 odd , (D,n) 2q 1 2-2q 1 1 from 9 . cases equation Hence, equation split 4n-15(D,n) 2q 1 2 6q 1-11 0 if q 1 1. split equation The remaining case is q 1 1 . Since k 1 1 and 2 1 so that k 2 2 , this implies n 15 and (D,n) 1 . At this point, the result has been proved when 2 1 . Lastly, we consider the exceptional case n p 1p 2 , 2 0 so that k 1 k 2 , and q 1 q 2 . Then we have n (2 k 1 q 1-1)(2 k 1 q 1 1) 4 k 1 q 1 2-1 with (n) -1, (D,n) (q 1-1) 2 4 k 1 -1 3q 1 2 as in 9. Hence, equation split 3(n-2(D,n)) 4 k 1 q 1 2-4q 1 2 12q 1-9 12q 1-9 0. split equation Therefore, (D,n) n 2 . The case s 3 Now, the case s 3 . By the second part of Lemma lem:2.3 , it is sufficient to show that the inequality equation 10 (D,n)7 48 D(n) equation holds. Lemma lem:5.2 implies the result under the following conditions: equation (D,n) D(n) cases 1 12 if r i2 for at least one i, 1 8 if the k i 's are not all equal , 1 12 if one of the q i 's does not divide q, cases equation because the inequality 10 is then satisfied. In the remaining case, we have n (2 k 1 q 1 1)(2 k 1 q 2 2)(2 k 1 q 3 3) with q 1,q 2 and q 3 odd and dividing n-(n) 2 k 1 q . The formula of Theorem thm:1.5 can be written equation split (D,n) (q 1-1)(q 2-1)(q 3-1) (1 8 8 k 1-1 )q 1q 2q 3 (q 1-1)(q 2-1)(q 3-1) 8 k 1 -1 7q 1q 2q 3. split equation But, D(n) 8 k 1 q 1q 2q 3 so, the inequality 10 can be written (q 1-1)(q 2-1)(q 3-1) 8 k 1 -1 7q 1q 2q 37 48 8 k 1 q 1q 2q 3 or more simply, (q 1-1)(q 2-1)(q 3-1)( 8 k 1 336 17)q 1q 2q 3. This is satisfied as soon as ( 8 k 1 336 17)1 and in particular as soon as k 13 . So we can assume that k 1 equals 1 or 2. We handle first the case k 1 2 , that is n (4q 1 1)(4q 2 2)(4q 3 3) with q 1,q 2,q 3 odd and dividing n-(n) 4q . Suppose that q 1 q 2 1 , so that 1 - 2 and p 1,p 2 3,5 . Then (n) - 3 and 4q n-(n) 15(4q 3 3) 3 60q 3 16 3. As q 3 q , this implies q 3 16 , so q 3 1 , which is impossible because the prime p 1,p 2,p 3 are distinct. Hence, we can assume that q 23 and q 33 since the ordering of the primes is arbitrary here. Then since equation split n (4q 1-1)(4q 2-1)(4q 3-1) 64q 1q 2q 3-16(q 1q 2 q 1q 3 q 2q 3) 4(q 1 q 2 q 3)-1 split equation and since (D,n) 10q 1q 2q 3-(q 1q 2 q 1q 3 q 2q 3) (q 1 q 2 q 3)-1 we can see that equation split 4n-15(D,n) 106q 1q 2q 3-49(q 1q 2 q 1q 3 q 2q 3) (q 1 q 2 q 3) 11 106(q 1-1)(q 2-3)(q 3-3) 269(q 1-1)(q 2-3) 269(q 1-1)(q 3-3) 57(q 2-3)(q 3-3) 661(q 1-1) 123(q 2-3) 123(q 3-3) 237 0. split equation Now, we consider the case where k 1 1 , that is n (2q 1 1)(2q 2 2)(2q 3 3) with q 1,q 2,q 3 odd and dividing n-(n) 2q . First, assume that q 1 1 , so p 1 3 . Then p 2,p 35 so q 2,q 33 and n 3(2q 2 2)(2q 3 3)3(2q 2-1)(3q 3-1),(D,n) q 2q 3. Hence, equation split 4n-15(D,n) 12(2q 2-1)(2q 3-1)-15q 2q 3 33q 2q 3-24q 2-24q 3 12 33(q 2-3)(q 3-3) 75(q 2-3) 75(q 3-3) 165 0. split equation So we can assume that all q i 's are greater than 1. But q i 3 only if p i 5 or 7. If q 1 q 2 3 , then p 1,p 2 5,7 and q 35 . In this case n 57(2q 3 3) and (D,n) 4(q 3-1) 9q 3 . Hence equation split 4n-15(D,n) 457(2q 3-1)-60(q 3-1)-135q 3 85q 3-80 85(q 3-5) 345 0. split equation So we can assume that q 13 and q 2,q 35 . But q i 5 only if p i 11 . So we can assume that q 25 and q 37 . We have equation split n (2q 1-1)(2q 2-1)(2q 3-1) 8q 1q 2q 3-4(q 1q 2 q 1q 3 q 2q 3) 2(q 1 q 2 q 3)-1, split equation (D,n) (q 1-1)(q 2-1)(q 3-1) q 1q 2q 3. From this we easily deduce (if we are lucky to have good computing tools at hand) that equation split 4n-15(D,n) 2q 1q 2q 3-(q 1q 2 q 1q 3 q 2q 3)-7(q 1 q 2 q 3) 11 2(q 1-3)(q 2-5)(q 3-7) 13(q 1-3)(q 2-5) 9(q 1-3)(q 3-7) 5(q 2-5)(q 3-7) 51(q 1-3) 25(q 2-5) 15(q 3-7) 45. split equation This proves that 4n-15(D,n) 0 because we have assumed q 13 , q 25 , q 37 . The case s4 Lastly, the case where s4 . Lemma lem:5.2 shows that (D,n) D(n) 2 s-1 1 2 s-4 D(n) 8. Using the inequality 2.3, we obtain (D,n) 96 385 (7 13 ) s-4 n 96 385 n4 15 n. This finally ( ) concludes the proof. Worst cases and better bounds Twin primes We have noted that the only numbers n such that (D,n) 4 15 n are products n (2 k 1 q 1-1)(2 k 1 q 1 1) of twin primes with q 1 odd and (2 k 1 q 1-1) -1 , (2 k 1 q 1 1) 1 . The proof of Theorem thm:1.3 shows that in fact, we then have equation 11 n 3(D,n)n 2. equation If there are infinitely many twin primes p 1 p 2 satisfying the conditions (D p 1) -1 and (D p 2) 1 , then there are infinitely many n such that relations 11 hold. If p 1,p 2 are such twin primes satisfying the additional condition k 1 1 (that is p 11 modulo 4), then for n p 1p 2 , we have (D,n) n (q 1-1) 2 4 k 1 -1 3q 1 2 4 k 1 q 1 2-1 (q 1-1) 2 q 1 2 4q 1 2-1 2q 1 2-2q 1 1 4q 1 2-1 . This shows that (D,n) n tends to 1 2 as q 1 tends to . So, under the assumption that there are infinitely many such twin primes, we can find numbers n such that (D,n) n is as close as we want to 1 2. However, note that such numbers are easy to spot, so they do not really represent a nuisance for primality testing. ex Let D 2 and n 1 000 0371 000 039 1 000 076 001 443 . Then (D,n) 500 037 000 685 and 1 2-(D,n) n 10 -6 . ex The bound 4 15 Among numbers n such that (D,n) does to exceed 4 15 n , consider those such that n p 1p 2p 31 modulo 4 ,(p i) -1, and p i 1 n 1 for i 1,2,3 (these numbers were already encountered in 10 ). We have, in this case, (D,n) (q 1-1)(q 2-1)(q 3-1) q 1q 2q 3 which can be greater than n 4 , and very close to 4 15n . For example, consider the following ex Let D 7 and n 20705 , so that gather p 1 5,p 2 41,p 3 101, (p 1) (p 2) (p 3) (n) -1, p 1 1 2q 1 23,p 2 1 2q 2 2(37),p 3 1 2q 3 2(317), n 1 2q 2(371729), (7,20705) 5213. gather ex Better bounds There exist several ways to improve the Lucas test in order to make it more secure. One good idea yet found in 4 and 8 is to combine a Rabin-Miller test and a true'' (i.e. with (D n) -1) Lucas test. Such a combination seems much more secure than one might expect considering each test separately. But no precise result is known about this fact. Another approach is found in 6 where a strong test derived from the strong Lucas test is defined. It is shown that there the probability of error in each iteration of this new test is less than 1 8. amsplain