Sharpening ``Primes is in P for a large family of numbers

DOI10.1090/S0025-5718-05-01727-8MaRDI QIDQ5315434zbMATH OpenOpenAlexFDO

Authors Pedro Berrizbeitia

Publication date 8 September 2005

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0211334

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Primality (11Y11)

Abstract: We give Deterministic Primality tests for large families of numbers. These tests were inspired in the recent and celebrated Agrawal-Kayal-Saxena (AKS) test. The AKS test has proved polynomial complexity O ((log n)^12) and they expect it to be O ((log n)^6) . Our tests have proved complexity O ((log n)^6). The complexity decreases to O ((log n)^4) as the power of 2 dividing n + 1 or n - 1 increases. On large enough primes, our tests, in their worst case, run at least 2^9 times faster than the AKS test.

Recommendations

• Primality test for numbers of the form \((2p)^{2^n}+1\)
• scientific article; zbMATH DE number 2123628
• Primality Testing and Jacobi Sums
• Proving primality in essentially quartic random time
• scientific article; zbMATH DE number 4215363

Cites work

• scientific article; zbMATH DE number 981695 (Why is no real title available?)
• scientific article; zbMATH DE number 3126031 (Why is no real title available?)
• scientific article; zbMATH DE number 47996 (Why is no real title available?)
• scientific article; zbMATH DE number 1131675 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• A generalization of Proth's theorem
• Biquadratic reciprocity and a Lucasian primality test
• Divisors in Residue Classes
• On distinguishing prime numbers from composite numbers
• PRIMES is in P
• Primality Testing and Jacobi Sums
• Primality testing and Abelian varieties over finite fields

Cited in

(16)

• On the effectiveness of a generalization of Miller's primality theorem
• scientific article; zbMATH DE number 2123628 (Why is no real title available?)
• scientific article; zbMATH DE number 7556735 (Why is no real title available?)
• Implementations of the improved AKS primality testing algorithm
• It is easy to determine whether a given integer is prime
• Sharper ABC-based bounds for congruent polynomials
• Elliptic periods and primality proving
• Analyzing the AKS algorithm and its improved algorithm in detail
• Primality tests --- from Eratosthenes to today
• PRIMES is in P
• Primality testing with Gaussian periods
• A generalization of Miller’s primality theorem
• Implementing the asymptotically fast version of the elliptic curve primality proving algorithm
• Proving primality in essentially quartic random time
• An \(\tilde{O}(\log^{2}(N))\) time primality test for generalized Cullen numbers
• On the construction of finite field elements of large order

This page was built for publication: Sharpening ``Primes is in P for a large family of numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5315434)