On Lucas Sequences With Applications

One-paramcter Lucas sequences Un = Un(u) and Vn = Vn{u) arc defined as: U0 = 0,V0 = 2,U1 = 1,V1 = u,Un = uUn-1 - Un-2,Vn = uVn-1 - Vn-2,n > 2. These sequences have extensive applications in Number Theory. ZHANG Zhenxiang uses them as main tools to get methods for factoring large integers and primality testing respectively in his two papers: "Using Lucas sequences to factor large integers near group orders" [Fibonacci Quarterly, Vol.39, 2001, pp.228-237; MR 2002c:11173) and "A one-parameter quadratic-base version of the Baillie-PSW probable prime test " [Math. Comp., Vol.71, 2003, pp.1699-1734; MR 2003f:11191]. The first paper discusses the problem of factoring a class of large integers TV, where N = pq is a product of two odd primes with q = k(p+1) + r,|r| < p+1/2, k > 7,(n2-4/p) = -1,gcd(u,N) = gcd(u2 - 4, N) = 1. Using Lucas sequences to factor such integers, we must consider solutions of the following congruence systemsGenerally speaking, the more u's satisfy the above congruence systems, the more easily N is to be factored. When Lucas sequences are used, how to efficiently compute Un{u) and Vn(u) becomes an important problem. In a usual algorithm, n is expressed as a binary form: . While in other algorithms, n is represented as the 2k-ary form: In this paper, we first give some necessary and sufficient conditions of the above congruence systems . Then we estimate the number of u's satisfying the above congruences systems, which is less than N/6 and N/2 respectively. At last we give an analysis of two algorithms and get a conclusion that the crucial factor affecting the speed of the algorithms is the number of l's in the binary representation of n, that is, the more 1's are in the binary representation of n, the faster the second algorithm is when compared with the first one.