Portal de Periódicos da CAPES

Divisors in Residue Classes

1984; American Mathematical Society; Volume: 42; Issue: 165 Linguagem: Inglês

10.2307/2007582

1088-6842

H. W. Lenstra,

Computability, Logic, AI Algorithms

In this paper the following result is proved.Let r, s and n be integers satisfying 0 < r < s < n, s > hi/\ gcd(r, s) -I.Then there exist at most 11 positive divisors of n that are congruent to r modulo v.Moreover, there exists an efficient algorithm for determining all these divisors.The bound 11 is obtained by means of a combinatorial model related to coding theory.It is not known whether 11 is best possible; in any case it cannot be replaced by 5. Nor is it known whether similar results arc true for significantly smaller values of log s/\og n.The algorithm treated in the paper has applications in computational number theory.In this paper we prove the following theorem.Theorem.Let r, s and n be integers satisfying 0^r<s nx/\ gcd(r,s)=l.Then there exist at most 11 positive divisors of n that are congruent to r modulo s, and there is a polynomial algorithm for determining all these divisors.The algorithm referred to in the theorem is described in Section 1.It is polynomial in the sense that the number of bit operations required by the algorithm is bounded by a polynomial function of the binary length of n.More precisely, we shall see that this number of bit operations is 0((log«)3).Employing fast multiplication techniques we can improve this bound to 0((log «)2 + e) for every e > 0.We mention two applications of the algorithm.In several primality testing algorithms (see [3], [7]), the number n to be tested is subjected to a collection of "pseudo-prime" tests.If n does not pass all these tests it is composite.If n does pass all these tests, one knows that each divisor of n lies in one of a small and explicitly known set of residue classes modulo an auxiliary number s.In the latter case, all divisors of n can easily be found if s satisfies the condition s > nx/2.Our algorithm shows that the same can be done if s satisfies the weaker condition s > nx/3.In special cases this observation was already made in [2, Theorems 5 and 17].The second application is to the related problem of factoring n.Choosing 5 to be a suitable integer exceeding nx/i and applying our algorithm to all residue classes rmod s, we obtain an algorithm that factors n in time 0(/i(,/3)+e) for every e > 0. The same bound was achieved by Lehman [6] and, conjecturally, by Pinter [9], by methods that are similar in spirit.There exist better factoring methods, both in theory and in practice (see [7]), but this application indicates at least that it may be difficult to extend the algorithm to significantly smaller values of 5.