# Riemann's Hypothesis and tests for primality

@article{Miller1975RiemannsHA, title={Riemann's Hypothesis and tests for primality}, author={Gary L. Miller}, journal={Proceedings of the seventh annual ACM symposium on Theory of computing}, year={1975} }

The purpose of this paper is to present new upper bounds on the complexity of algorithms for testing the primality of a number. The first upper bound is 0(n1/7); it improves the previously best known bound of 0(n1/4) due to Pollard [11]. The second upper bound is dependent on the Extended Riemann Hypothesis (ERH): assuming ERH, we produce an algorithm which tests primality and runs in time 0((log n)4) steps. Thus we show that primality is testable in time a polynomial in the length of the… Expand

#### Topics from this paper

#### 419 Citations

Riemann's hypothesis and tests for primality

- Mathematics
- 1976

In this paper we present two algorithms for testing primality of an integer. The first algorithm runs in 0(n1/7) steps; while, the second runs in 0(log4n) step but assumes the Extended Riemann… Expand

Explicit bounds for primality testing and related problems

- Mathematics
- 1990

Many number-theoretic algorithms rely on a result of Ankeny, which states that if the Extended Riemann Hypothesis (ERH) is true, any nontrivial multiplicative subgroup of the integers modulo m omits… Expand

Combinatorial primality test

- Computer Science, Mathematics
- IACR Cryptol. ePrint Arch.
- 2019

In 1879, Laisant-Beaujeux gave the following result without proof: If n is a prime, then [EQUATION] This paper provides proofs of the result of Laisant-Beaujeux in two cases explicitly: (1) If an… Expand

Miller's Primality Test

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1979

Theorem 1. Assume that for every integer d that is 1 mod 4 and either prime or the product of two primes, the L-function I= & (k/d) l kmS satisfies the generalized Riemann hypothesis, where {kid)… Expand

Primality and identity testing via Chinese remaindering

- Mathematics, Computer Science
- JACM
- 2003

We give a simple and new randomized primality testing algorithm by reducing primality testing for number n to testing if a specific univariate identity over Zn holds.We also give new randomized… Expand

Conditional bounds for the least quadratic non-residue and related problems

- Computer Science, Mathematics
- Math. Comput.
- 2015

The existing explicit bounds for the least quadratic non-residue and the least prime in an arithmetic progression are improved and the classical conditional bounds of Littlewood for L-functions at s=1 are refined. Expand

Pseudopowers and primality proving

- Computer Science, Mathematics
- Contributions Discret. Math.
- 2007

A generalization of the result for any odd prime r is presented, obtained by studying the properties of Gaussian and Jacobi sums in cyclotomic ring of integers, which are tools from which the r-th power Eisenstein Reciprocity Law is derived, rather than from the law itself. Expand

THE LEAST QUADRATIC NON-RESIDUE, VALUES OF L-FUNCTIONS AT s = 1, AND RELATED PROBLEMS

- Mathematics
- 2012

In this paper, we study explicit and theoretical bounds for several interesting quantities in number theory, conditionally on the Generalized Riemann Hypothesis. Specically, we improve the existing… Expand

Some observations on primality testing

- Mathematics
- 1978

Let N be an integer which is to be tested for primality. Previous methods of ascertaining the primality of N make use of factors of N ? 1, N2 ? N + 1, and N2 + 1 in order to increase the size of any… Expand

Algebraic Geometry Over Four Rings and the Frontier to Tractability

- Mathematics
- 2000

We present some new and recent algorithmic results concerning polynomial system solving over various rings. In particular, we present some of the best recent bounds on: (a) the complexity of… Expand

#### References

SHOWING 1-10 OF 21 REFERENCES

The distribution of quadratic and higher residues

In this paper we discuss some of the many problems that can be propounded concerning the distribution of the quadratic residues and non-residues, or more generally the kth power residues and… Expand

Topics in Multiplicative Number Theory

- Mathematics
- 1971

Three basic principles.- The large sieve.- Arithmetic formulations of the large sieve.- A weighted sieve and its application.- A lower bound of Roth.- Classical mean value theorems.- New mean value… Expand

The complexity of theorem-proving procedures

- Computer Science, Mathematics
- STOC
- 1971

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a… Expand

The distribution of quadratic residues and non-residues

- Mathematics
- 1957

If p is a prime other than 2, half of the numbers 1, 2, … p —1 are quadratic residues (mod p ) and the other half are quadratic non-residues. Various questions have been proposed concerning the… Expand

Reducibility among combinatorial problems" in complexity of computer computations

- Computer Science
- 1972

In his 1972 paper, Reducibility Among Combinatorial Problems, Richard Karp used Stephen Cooks 1971 theorem that the boolean satisfiability problem is. Expand

The Art of Computer Programming

- Computer Science
- 1968

The arrangement of this invention provides a strong vibration free hold-down mechanism while avoiding a large pressure drop to the flow of coolant fluid. Expand

Reducibility Among Combinatorial Problems," Complexity of Computer Computations, R.E. Miller and 3.W

- 1972

Schnelle Multiplikation Grosser Zahlen

- Computing
- 1971