Elliptic curves and number-theoretic algorithms. (English) Zbl 0686.14039

Proc. Int. Congr. Math., Berkeley/Calif. 1986, Vol. 1, 99-120 (1987).
[For the entire collection see Zbl 0657.00005.]
The problem under consideration is the prime factor decomposition problem and the use of elliptic curve to find solutions to it. One considers two stages: firstly one decides whether a given large integer is a prime or not; secondly, if it is composite, one searches for a nontrivial divisor.
Applications are found in cryptography. This is based on the fact that primality testing is relatively easy, whereas factorization is hard. After surveying the older algorithms, the author explains the necessary tools from elliptic curve theory, especially point counting theorems and algorithms. He then applies the theory to primality testing on the one hand and to factorization on the other, providing solutions that lead (e.g. method of Atkins) to algorithms that can be used in practical implementations.
Together with the algorithms, the author discusses running time or probable running time. Not only primality test are discussed. A number is called pseudo-prime if it passes a test which every prime number passed and most of the composites don’t. A variety of pseudo-prime test are considered in the article.
Reviewer: G.Molenbergh


14H45 Special algebraic curves and curves of low genus
68W30 Symbolic computation and algebraic computation
14-04 Software, source code, etc. for problems pertaining to algebraic geometry
11A41 Primes
14H52 Elliptic curves
94A60 Cryptography


Zbl 0657.00005