On distinguishing prime numbers from composite numbers
From MaRDI portal
Publication:594912
DOI10.2307/2006975zbMath0526.10004OpenAlexW2329291360WikidataQ29543607 ScholiaQ29543607MaRDI QIDQ594912
Leonard M. Adleman, Robert S. Rumely, Carl B. Pomerance
Publication date: 1983
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2006975
probabilistic algorithmdeterministic algorithmJacobi sumprimality testingnearly polynomial timep-th power residue symbols in cyclotomic fieldspseudoprimality tests
Software, source code, etc. for problems pertaining to number theory (11-04) Cyclotomy (11T22) Primes (11A41) Algorithms in computer science (68W99)
Related Items (58)
New amicable pairs of type $(2,2)$ and type $(3,2)$ ⋮ The second largest prime divisor of an odd perfect number exceeds ten thousand ⋮ Compositeness test with nodal curves ⋮ Fast generation of prime numbers and secure public-key cryptographic parameters. ⋮ Sharpening ``Primes is in P for a large family of numbers ⋮ Algorithms in Algebraic Number Theory ⋮ It is easy to determine whether a given integer is prime ⋮ The generation of random numbers that are probably prime ⋮ Small exponent point groups on elliptic curves ⋮ Squarefree smooth numbers and Euclidean prime generators ⋮ Computation of Jacobi sums of orders \(l^2\) and \(2l^2\) with odd prime \(l\) ⋮ An application of Jacobi type polynomials to irrationality measures ⋮ Primality test for numbers \(M\) with a large power of 5 dividing \(M^{4}-1\). ⋮ Interactions of computational complexity theory and mathematics ⋮ Some uses of microcomputers in number theory research ⋮ Finding strong pseudoprimes to several bases ⋮ The influence of computers in the development of number theory ⋮ Some results on pseudosquares ⋮ Greatest common divisors and Vojta's conjecture for blowups of algebraic tori ⋮ An appraisal of computational complexity for operations researchers ⋮ Classroom Notes ⋮ Classroom Notes ⋮ Classroom Notes ⋮ Cyclotomic Numbers and Jacobi Sums: A Survey ⋮ Primality test for numbers of the form \(A p^n + w_n\) ⋮ Identifying the Matrix Ring: Algorithms for Quaternion Algebras and Quadratic Forms ⋮ Elliptic Curves and Primality Proving ⋮ Special factors of holomorphic eta quotients ⋮ A faster pseudo-primality test ⋮ Prime values of polynomials and irreducibility testing ⋮ FLAT PRIMES AND THIN PRIMES ⋮ A lower bound for primality ⋮ Faster polynomial multiplication over finite fields using cyclotomic coefficient rings ⋮ The third largest prime divisor of an odd perfect number exceeds one hundred ⋮ Unnamed Item ⋮ A Rigorous Time Bound for Factoring Integers ⋮ Explicit Bounds for Primality Testing and Related Problems ⋮ Information and computation: Classical and quantum aspects ⋮ Prime-number algorithm for public-key systems ⋮ Lower bounds on the lengths of double-base representations ⋮ An 𝑂̃(log²(𝑁)) time primality test for generalized Cullen numbers ⋮ Randomized algorithms over finite fields for the exact parity base problem. ⋮ Synchronization points and associated dynamical invariants ⋮ Unnamed Item ⋮ Generalized strong pseudoprime tests and applications ⋮ Proving primality in essentially quartic random time ⋮ Implementing the asymptotically fast version of the elliptic curve primality proving algorithm ⋮ Primality Test Via Quantum Factorization ⋮ Recent developments in primality proving ⋮ Complete congruences of Jacobi sums of order \(2l^2\) with prime \(l\) ⋮ Strong pseudoprimes to base 2 ⋮ Compositions with the Euler and Carmichael functions ⋮ Factoring on a computer ⋮ An Overview of Factoring ⋮ Infinite Sets of Primes with Fast Primality Tests and Quick Generation of Large Primes ⋮ Computing in general Abelian groups is hard ⋮ Short effective intervals containing primes ⋮ A cyclotomic generalization of the sequence \(\gcd(a^n-1, b^n-1)\)
This page was built for publication: On distinguishing prime numbers from composite numbers
