scientific article; zbMATH DE number 3912454
algorithmscomplexitycomposite numberscomputational number theorycryptographypreassigned factoring patternprimality testingstrong pseudoprimes
Research exposition (monographs, survey articles) pertaining to number theory (11-02) Power residues, reciprocity (11A15) Primes (11A41) Factorization (11Y05) Primality (11Y11) Number-theoretic algorithms; complexity (11Y16) Computational number theory (11Yxx) Symbolic computation and algebraic computation (68W30) Cryptography (94A60)
The book has two chapters. Chapter I deals with some questions of analysis, arising particularly in the use of strong pseudoprimes as witnesses to the composite character of an unknown integer \(m\) [see \textit{G. L. Miller}, J. Comput. Syst. Sci. 13, 300--317 (1976; Zbl 0349.68025)]. The sufficiency of witnesses \(<2(\log m)^ 2\) requires something like the ERH (Extended Riemann Hypothesis). In this connection, the first use of ERH was by \textit{N. C. Ankeny} [Ann. Math. (2) 55, 65--72 (1952; Zbl 0046.04006)] showing that every prime has a quadratic nonresidue of logarithmic size. More recently this technique was extended to prime ideals by \textit{J. C. Lagarias}, \textit{H. L. Montgomery}, and \textit{A. M. Odlyzko} [see Invent. Math. 54, 271--296 (1979; Zbl 0401.12014)]. Although the theory is very involved, the author explains the relevance of the roots of the zeta-function to the estimation of witnesses in an intuitive sketch which is extremely helpful to the non-expert. Numerical tests are also cited [see \textit{J. van de Lune} and \textit{H. J. J. te Riele}, Math. Comput. 41, 759--767 (1983; Zbl 0521.10030)]. Chapter 2 presents an algorithm for generating composite numbers of any size with a preassigned factoring pattern (and some preassigned factors). This is useful for cryptography. The algorithm is of the same complexity as generating a random prime of the same size. This chapter is more technical and more original in terms of the author's own work. There is a strong probabilistic element in the use of trial ``primes to complete an essentially deterministic algorithm.
- Solving dense subset-sum problems by using analytical number theory
- Generalized strong pseudoprime tests and applications
- A fast and robust RNS algorithm for evaluating signs of determinants
- Short effective intervals containing primes
- Realistic analysis of some randomized algorithms
- Computing the endomorphism ring of an ordinary elliptic curve over a finite field
- Explicit Bounds for Primality Testing and Related Problems
- A generalization of Miller’s primality theorem
- On the Distribution of Quadratic Residues and Nonresidues Modulo a Prime Number
- Comments on search procedures for primitive roots
- Generating random factored ideals in number fields
- Efficient oblivious transfer from lossy threshold homomorphic encryption
- The least quadratic non-residue
- scientific article; zbMATH DE number 5590087 (Why is no real title available?)
- Primality testing
- Isogeny problems with level structure
- The counting function for Elkies primes
- On the effectiveness of a generalization of Miller's primality theorem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3689236)