Az Eszterházy Károly Tanárképző Főiskola Tudományos Közleményei. 2004. Sectio Mathematicae. (Acta Academiae Paedagogicae Agriensis : Nova series ; Tom. 31)

LUCA, F., Primitive divisors of Lucas sequences and prime factors of ... and ...

Primitive divisors of Lucas sequences and prime factors of x

2+\ and .r

4 + l 23 follows, for a positive real number y we use logy for the maximum between the natural logarithm of y and 1, and for a positive integer k we use \og

k y for the Arth fold iterate of the function logy. From this result, if follows that if P(x

2 -f 1

) < A, then x < exp (exp (0(A log

2 A/log A"))), so if one wants to find all the positive integer solutions x of the inequality P(x

1 -f 1) < K by simply factoring x

2 + 1 for all positive integers x up to the above upper bound, then the running time of such a naive algorithm will be almost doubly exponential in A

. In this section, we present the following result. Theorem 3.1. The algorithm presented in section 2 finds all positive integer solutions x of the inequality P(x

2 + 1) < A after at most exp(0(K)) elementary hit operations. Proof. Here, we keep the notations from section 2. First, to generate A, one first generates the 2

7

r'

A;

4'

1,+ 1 = exp(0(A)) squarefree numbers d all whose prime factors are 2 or congruent to 1 (mod 4) and having P[d) < A. Secondly, to find i>, for each one of the numbers d £ A one computes the minimal solution (A'i (rf), V] (</)) of the Pell equation X

2 - dY

2 = ±1. Then B is the subset of those d £ A such that (A'i(</), Y\(d)) is a solution of the equation X

2 — d,Y

2 = — 1. The continued fraction algorithm for quadratic irrationalities shows that this is computable in 0(d

x!

2) = exp(0(/v")) steps and since d < 4

A

, it follows that at each step only numbers of the form exp(0(A )) are being handled. Now with each one of these numbers Y\(d), we test if P[d) < A. This step requires exp(0(A')) elementary operations. Indeed, let, p < A be a fixed prime and assume that p

a||i'i(i/). Then alIAogY\(d) = exp(0(A')). Moreover, since a (mod b) requires O (log

2(a + 6)) elementary bit operations (using naive arithmetic, and even less using Fast Fourier Transform), it follows that this part of the computation requires exp(0(A

)) elementary bit operations. Thus, the subset C of B consisting of those d £ B such that P(d) < A can be generated after at most exp(0(A')) elementary bit operations. Finally, one now generates Y

k(d) for k < A and tests again if P(Yk{d)) < A'. As previously, this requires again at most exp(0(A")) elementary bit operations after which the set consisting of all the positive integers x such that X

2 + 1 = dY'K(d)

2 has the largest prime factor < A is obtained. Acknowledgments. The computations were carried out on the machines at the Tata Institute for Fundamental Research in Mumbai, India, on June 25 and June 26, 20U1.1 would like to thank the Tata Institute for its hospitality, Professors Yann Bugeaud, Maurice Mignotte, Igor Shparlinski and Tarlok Shorey for useful advice, and the Third World Academy of Sciences for financial support. References [1] BUCHMANN, J., GYŐRY, K., MIGNOTTE, M., TZANAKIS, N., Lower bounds for P{x D 3 + A*), an elementary approach, Publ. Math. Debrecen 38 (1991), no. 1-2, 145-163.