Explicit Bounds for Primality Testing and Related Problems

DOI10.2307/2008811zbMath0701.11075OpenAlexW4235110860WikidataQ29042070 ScholiaQ29042070MaRDI QIDQ3478501

Eric Bach

Publication date: 1990

Full work available at URL: https://doi.org/10.2307/2008811

zbMATH Keywords

extended Riemann hypothesisabelian extensionprimality testingcomposite numberleast prime idealwitness for compositeness

Mathematics Subject Classification ID

Class numbers, class groups, discriminants (11R29) Nonreal zeros of (zeta (s)) and (L(s, chi)); Riemann and other hypotheses (11M26) Distribution of prime ideals (11R44) Power residues, reciprocity (11A15) Primality (11Y11)

Related Items (70)

The least inert prime in a real quadratic field ⋮ A public-key cryptosystem utilizing cyclotomic fields ⋮ A Terr algorithm for computations in the infrastructure of real-quadratic number fields ⋮ The Elkies curve has rank 28 subject only to GRH ⋮ Upper bounds on the heights of polynomials and rational fractions from their values ⋮ Recent results about the prime ideal theorem ⋮ Algorithms in Algebraic Number Theory ⋮ Orientations and the supersingular endomorphism ring problem ⋮ The least quadratic non-residue ⋮ Automaticity. II: Descriptional complexity in the unary case ⋮ Explicit two-cover descent for genus 2 curves ⋮ A proof of the conjectured run time of the Hafner-McCurley class group algorithm ⋮ Strong pseudoprimes to twelve prime bases ⋮ The CM class number one problem for curves of genus 2 ⋮ An explicit upper bound for the least prime ideal in the Chebotarev density theorem ⋮ Elliptic curve variants of the least quadratic nonresidue problem and Linnik’s theorem ⋮ Integer factoring and modular square roots ⋮ Log-\(\mathcal{S}\)-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP ⋮ Fast multiquadratic S-unit computation and application to the calculation of class groups ⋮ Generating subgroups of ray class groups with small prime ideals ⋮ Norm relations and computational problems in number fields ⋮ The class number one problem for some non-normal CM-fields of degree \(2p\) ⋮ Some results on pseudosquares ⋮ The Euclidean algorithm in quintic and septic cyclic fields ⋮ Fast algorithm of square rooting in some finite fields of odd characteristic ⋮ Constructing nonresidues in finite fields and the extended Riemann hypothesis ⋮ Polynomials with roots modulo every integer ⋮ Modular polynomials via isogeny volcanoes ⋮ Distinguishing eigenforms modulo a prime ideal ⋮ Some remarks concerning the complexity of computing class groups of quadratic fields ⋮ A low-memory algorithm for finding short product representations in finite groups. ⋮ Statistical Evidence for Small Generating Sets ⋮ Explicit bounds for generators of the class group ⋮ Solving systems of diagonal polynomial equations over finite fields ⋮ Ono invariants of imaginary quadratic fields with class number three ⋮ Approximate short vectors in ideal lattices of \(\mathbb{Q}(\zeta_{p^e})\) with precomputation of \({\mathrm {Cl}}(\mathcal{O}_K)\) ⋮ Minimal generators of the ideal class group ⋮ The least \(k\)-th power non-residue ⋮ Optimal bounds for Büchi's problem in modular arithmetic ⋮ The exponent three class group problem for some real cyclic cubic number fields ⋮ An 𝐿(1/3) algorithm for ideal class group and regulator computation in certain number fields ⋮ On the effectiveness of a generalization of Miller's primality theorem ⋮ Computing Generator in Cyclotomic Integer Rings ⋮ Short Stickelberger Class Relations and Application to Ideal-SVP ⋮ On the Ono invariants of imaginary quadratic fields ⋮ A deterministic version of Pollard’s $p-1$ algorithm ⋮ Practical Improvements to Class Group and Regulator Computation of Real Quadratic Fields ⋮ Norm-Euclidean Galois fields and the generalized Riemann hypothesis ⋮ The complexity of class polynomial computation via floating point approximations ⋮ Small generators of the ideal class group ⋮ Quadratic sieving ⋮ Explicit smoothed prime ideals theorems under GRH ⋮ Unconditional class group tabulation of imaginary quadratic fields to $\|\Delta \| < 2^{40}$ ⋮ Discrete logarithm problems with auxiliary inputs ⋮ Computing Hilbert class polynomials with the Chinese remainder theorem ⋮ A survey of computational class field theory ⋮ Expander graphs based on GRH with an application to elliptic curve cryptography ⋮ Explicit bounds for primes in residue classes ⋮ The complexity of solving low degree equations over ring of integers and residue rings ⋮ Computing $p$-adic $L$-functions of totally real number fields ⋮ Computing prime divisors in an interval ⋮ Computing the residue of the Dedekind zeta function ⋮ Decision problems in quadratic function fields of high genus ⋮ Explicit primality criteria for $(p-1)p^n-1$ ⋮ Computing discrete logarithms in real quadratic congruence function fields of large genus ⋮ Applying sieving to the computation of quadratic class groups ⋮ Conditional bounds for the least quadratic non-residue and related problems ⋮ On ideal class group computation of imaginary multiquadratic fields ⋮ An inequality between class numbers and Ono's numbers associated to imaginary quadratic fields. ⋮ Rational isogenies from irrational endomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On distinguishing prime numbers from composite numbers
• Riemann's hypothesis and tests for primality
• A bound for the least prime ideal in the Chebotarev density theorem
• Some effective cases of the Brauer-Siegel theorem
• Topics in multiplicative number theory
• Approximate formulas for some functions of prime numbers
• The least quadratic non residue
• A Monte Carlo Factoring Algorithm With Linear Storage
• Primality Testing and Jacobi Sums
• On the Zeros of the Riemann Zeta Function in the Critical Strip. IV
• A Probabilistic Factorization Algorithm with Quadratic Forms of Negative Discriminant
• Factoring polynomials over finite fields
• Factoring with Cyclotomic Polynomials
• The evalution of Dirichlet L -functions
• On the Zeros of the Riemann Zeta Function in the Critical Strip
• The Pseudoprimes to 25 ⋅10 9
• A Rapidly Convergent Series for Computing ψ(z) and Its Derivatives
• Estimation de la fonction de Tchebychef θ sur le k-ième nombre premier et grandes valeurs de la fonction ω(n) nombre de diviseurs premiers de n
• On Small Zeros of Dirichlet L-Functions
• A Fast Monte-Carlo Test for Primality
• On Computing Artin L-Functions in the Critical Strip
• On the Distribution of Spacings Between Zeros of the Zeta Function
• Lower bounds for discriminants of number fields
• An approximate functional equation for Dirichlet L -functions
• Chebyshev Approximations for the Exponential Integral Ei(x)
• Calculation of Dirichlet L-Functions
• Integer Sequence having Prescribed Quadratic Character

This page was built for publication: Explicit Bounds for Primality Testing and Related Problems