Prime numbers. A computational perspective
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to number theory (11-01) Primes (11A41) Factorization; primality (11A51) Elliptic curves over local fields (11G07) Factorization (11Y05) Primality (11Y11) Computational number theory (11Yxx) Symbolic computation and algebraic computation (68W30)
This is an absolutely wonderful book! Written in a readable and enthusiastic style the authors try to share the elegance of the prime numbers with the readers, thereby also unravelling some of the complexity and power hidden within such numbers. Weaving together a wealth of ideas and experience from theory and practice they enable the reader to have more than a glimpse into the current state of knowledge as well as the likely prospects for the immediate future. The titles for the chapters are: 1. Primes, 2. Number-Theoretic Tools, 3. Recognizing Primes and Composites, 4. Primality Proving, 5. Exponential Factoring Algorithms, 6. Subexponential Factoring Algorithms, 7. Elliptic Curve Arithmetic, 8. The Ubiquity of Prime Numbers, 9. Fast Algorithms for Large-Integer Arithmetic. Each chapter ends with a good collection of exercises set out in a well-organised manner. Many of these are research projects with suitable pointers, directions and useful suggestions. As part of the title of the book already indicates, the computational aspect takes on a prominent role. The driving force in the development in this area is, of course, the advent of powerful computing machines, followed by the construction of efficient algorithms, many of which making spectacular breakthoughs for some basic problems. There are countless algorithms accompanying the text; these are given in pseudocode -- a fusion of English and C languages -- together with plenty of helpful comments within the codes. The algorithms not only serve to illuminate and justify the methods used, they also underscore the practical power of a constructive argument. Almost any chapter or section can be singled out for high praise. Since the subjects of factorisation and the computation of discrete logarithms are now part of a vast research field, indeed even an industry, there is much to be learned for both the theoretician and the practitioner from the text. Thus the authors gave authorative background and much of the idea and excitement behind the development of the quadratic sieve, the number field sieve and the elliptic curve method. Some of the development highlights the interplay between theoretical complexity estimates and good programming intuitions; indeed it is clear that such recent rapid progress with these problems would not have taken place without this interplay. Such ideas and methods also give some urgency to the study of particular topics, one such being the distribution of smooth numbers. This second edition (see Zbl 0995.11072 for a review of the first ed.) is thoroughly revised, with up-dated listing of computational records and interesting new results -- one such being an exposition of the AKS test for recognising primes. The book is written so that newcomers to the subject will not find it daunting, and yet it has already acquired the status of a standard reference for research workers. Indeed it is destined to become a definitive text on the computational aspect of prime numbers and factoring.
- Prime numbers. A computational perspective
- Prime numbers and computer methods for factorization.
- Prime numbers and computer methods for factorization
- Prime numbers and computer methods for factorization
- scientific article; zbMATH DE number 6696406
- scientific article; zbMATH DE number 53147
- scientific article; zbMATH DE number 4019139
- Computing pairings using x-coordinates only
- On the classification of integers \(n\) that divide \(\varphi(n)+\sigma(n)\)
- Computational strategies for the Riemann zeta function
- The reciprocal sum of primitive nondeficient numbers
- The complexity of primes in computable unique factorization domains
- Prime numbers as a tool to design distributed algorithms
- Prime numbers and computer methods for factorization.
- Looking for Fibonacci base-2 pseudoprimes
- The distribution of the number of points modulo an integer on elliptic curves over finite fields
- Integer factoring and compositeness witnesses
- Mechanisation of the AKS algorithm
- Orbit counting in polarized dynamical systems
- Weak pseudoprimality associated with the generalized Lucas sequences
- Tabulating Carmichael numbers \(n=Pqr\) with small \(P\)
- Controlled SWAP attack and improved quantum encryption of arbitrated quantum signature schemes
- A new primality test for natural integers
- Pseudoprimality related to the generalized Lucas sequences
- A survey on delegated computation
- Tight upper and lower bounds for the reciprocal sum of Proth primes
- On some new arithmetic properties of the generalized Lucas sequences
- On Balazard, Saias, and Yor's equivalence to the Riemann hypothesis
- Prime simplicity
- A primality test for \(4Kp^n-1\) numbers
- Polynomial evaluation and interpolation on special sets of points
- Highly parallel modular multiplier for elliptic curve cryptography in residue number system
- Computing the endomorphism ring of an ordinary elliptic curve over a finite field
- Modulated string searching
- On practical aspects of the Miller-Rabin primality test
- On functions taking only prime values
- Towards a generic view of primality through multiset decompositions of natural numbers
- On the complexity of matrix reduction over finite fields
- Distributional properties of the largest prime factor
- Some remarks on primality proving and elliptic curves
- Quantum computation and quantum information
- Explicit methods in number theory. Abstracts from the workshop held July 18--24, 2021 (hybrid meeting)
- On oracle factoring of integers
- On Grosswald's conjecture on primitive roots
- A framework for deterministic primality proving using elliptic curves with complex multiplication
- A deterministic algorithm for integer factorization
- Large-order multiple recursive generators with modulus \(2^{31}-1\)
- Adversary-dependent lossy trapdoor function from hardness of factoring semi-smooth RSA subgroup moduli
- On a pair of zeta functions
- Tabulation of cubic function fields via polynomial binary cubic forms
- Faster deterministic integer factorization
- Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields
- On near-perfect numbers with two distinct prime factors
- Algorithmic number theory
- On group structures realized by elliptic curves over a fixed finite field
- The least inert prime in a real quadratic field
- Computational Number Theory and Cryptography
- Mechanisation of AKS algorithm. I. The main theorem
- On fast calculation of addition chains for isogeny-based cryptography
- On taking square roots without quadratic nonresidues over finite fields. With an Appendix by Lawrence C. Washington
- Even faster integer multiplication
- Counting Carmichael numbers with small seeds
- Computing Hilbert class polynomials with the Chinese remainder theorem
- Emulating primality with multiset representations of natural numbers
- scientific article; zbMATH DE number 5994749 (Why is no real title available?)
- Primality testing of Woodall numbers
- On the number of strong primes
- Compositeness test with nodal curves
- Finding elliptic curves with a subgroup of prescribed size
- Few Product Gates But Many Zeros
- Improved Bounds on Brun’s Constant
- Complexity of inverting the Euler function
- Construction of strong elliptic curves suitable for cryptographic applications
- Algorithms for the Multiplication Table Problem
- A generalised Lucasian primality test
- Implementing the asymptotically fast version of the elliptic curve primality proving algorithm
- Generating random factored Gaussian integers, easily
- Running Time Predictions for Factoring Algorithms
- On the length of critical orbits of stable quadratic polynomials
- On the existence and non-existence of elliptic pseudoprimes
- Gaussian Mersenne and Eisenstein Mersenne primes
- Two kinds of strong pseudoprimes up to $10^{36}$
- VSH, an Efficient and Provable Collision-Resistant Hash Function
- The Elliptic Curve Discrete Logarithm Problem and Equivalent Hard Problems for Elliptic Divisibility Sequences
- On Williams numbers with three prime factors
- scientific article; zbMATH DE number 51161 (Why is no real title available?)
- scientific article; zbMATH DE number 66939 (Why is no real title available?)
- Computing Dirichlet character sums to a power-full modulus
- scientific article; zbMATH DE number 177274 (Why is no real title available?)
- Prime numbers. A computational perspective
- scientific article; zbMATH DE number 653244 (Why is no real title available?)
- On sharp transitions in making squares
- scientific article; zbMATH DE number 715020 (Why is no real title available?)
- scientific article; zbMATH DE number 1078084 (Why is no real title available?)
- Some finite solvable groups with non-trivial lattice endomorphisms
- Arithmetic functions and irreducible binary forms of degree 3
- A Superpowered Euclidean Prime Generator
- If the Primes are Finite, Then All of Them Divide the Number One
- Squarefree smooth numbers and Euclidean prime generators
- Could, or should, the ancient Greeks have discovered the Lucas-Lehmer test?
- A prime-representing constant
- Finding 𝐶₃-strong pseudoprimes
- The continuing search for Wieferich primes
- Computing Prime Factorization And Discrete Logarithms: From Index Calculus To Xedni Calculus
- scientific article; zbMATH DE number 3440487 (Why is no real title available?)
- Proof of three conjectures on congruences
- scientific article; zbMATH DE number 3448642 (Why is no real title available?)
This page was built for publication: Prime numbers. A computational perspective
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317673)