Fast primality testing algorithm study and implementation

Abstract

In the previous chapters we discussed the details of some primality testing algorithms and the implementation of a fast deterministic primality testing algorithm. Our implementation consists of programs written in Pascal with the exception of multiprecision integer arithmetic routines which are coded in Fortran. The Pascal code is about 2000 lines and the Fortran code runs to 206 lines. As we remarked, there has been an increasing interest in the study of algorithms for generating and testing prime numbers. In this chapter we make some concluding remarks on the role of these algorithms in the context of number-theoretic computations and cryptographic applications. In Chapter 2, we studied different probabilistic and deterministic algorithms for primality testing. A polynomial time algorithm for primality testing, though easy to justify heuristically, has been notoriously elusive; this alone makes number theory interesting from the purely complexity-theoretic point of view. Barring an outright proof that the problem PRIMES is in P, it would be highly desirable to have an implementable probabilistic algorithm that shows PRIMES is in RP. For then, given a number N,one could use simultaneously and repeatedly , the two probabilistic algorithms for PRIMES and COMPOSITES on N. About a hundred repetitions would suffice to yield a proof of N's status with near certainty. This type of algorithm (i.e. one that shows both a problem and its complement are in RP) is called a Las Vegas algorithm, to distinguish it from Monte Carlo algorithms which 47 commonly refer to the type of algorithm showing a problem is in RP. Unfortunately, the recent algorithms of Goldwasser and Kilian (described in Chapter 2) and of Adleman and Huang[l] are only of theoretical interest. Their efforts have led to the novel idea of using arithmetic on elliptic curves as a tool for solving interesting number-theoretic problems. It would be interesting to come up with a cryptosystem (or a digital signature scheme) that makes use of the theory of elliptic curves. In Chapter 3, we presented details of our implementation. Our program can routinely handle integers of size 120 digits. It is flexible to the extent that it can be made to handle much larger inputs by effecting suitable changes in the sizes of the data structures used. This can be done in a straight forward manner. We make use of Lenstra's algorithm[19], in version 2 of the final stage of the algorithm,, to determine divisors d of n such that d=r (mods). We strongly feel that this algorithm can be "improved" by making use of the additional information that r is of the form r=n^ (mod s). Such an improvement would make version 2 of the implementation far more superior to version 1. We now make a few remarks on the "usefulness" of our programs. There is a growing interest in exploiting number theory for encryption. How safe is an RSA cryptosystem ? One pitfall is that certain choices of p and q make N comparatively easy to factorize. A knowledge of the theoretical background of the various factorization methods in use can help us to avoid certain dangerous situations such as the case when p-1 or q-1 has only small prime factors. In this case N can 48 be factored easily using Pollard's (p-l)-method (see [25, 35, 40]). In this situation it is better to choose p and q such that p=2p'+l, q=2q'+l with p', q' primes (see [16], [Al]). A fast deterministic primality testing algorithm is very helpful in selecting such large primes of specific forms. Some of the schemes for cryptography and pseudo-random number generation require not just large primes but large random numbers with conditions on their factors (see [7, 17, 24]). Bach[5] presents an algorithm, using primality testing as a primitive operation, that can be used to generate such numbers. The expected number of primality tests needed in this method to generate a random kbit number (in factored form) is 0(k). Our implementation provides the following computational tools as byproducts. Routines for m ulti p e c i s i o n arithmetic, computing multiplicative inverses, computing primitive roots, finding square roots and cube roots, and computation of arithmetic in polynomial rings, which are useful in other areas of computational number theory and computer algebra, form a part of our implementation. Collectively, these provide a means for establishing computational evidence for certain types of number-theoretic questions.