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

DOI10.1090/S0025-5718-05-01727-8zbMATH Open1071.11071arXivmath/0211334OpenAlexW2105443299MaRDI QIDQ5315434FDOQ5315434

Authors: Pedro Berrizbeitia 

Publication date: 8 September 2005

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On distinguishing prime numbers from composite numbers
• PRIMES is in P
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Biquadratic reciprocity and a Lucasian primality test
• Divisors in Residue Classes
• Title not available (Why is that?)
• Primality Testing and Jacobi Sums
• A generalization of Proth's theorem
• Primality testing and Abelian varieties over finite fields

Cited In (16)

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the effectiveness of a generalization of Miller's primality theorem
• 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)