I am trying to find out if a number is prime on a computer but I am only try a very few and far apart numbers so don't want to use a sieve. I am quite good at maths but am only doing my GCSEs so can you please explain the answers clearly. I am looking for the most time efficient primality test algorithm as my numbers quickly get to sizes like 2^2^20 which needs a very efficient primality test. I am really looking for a polynomial time algorithm.
2026-02-22 21:17:12.1771795032
What is the most speed efficient primality test available
771 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
There are 1 best solutions below
Related Questions in PRIME-NUMBERS
- New prime number
- Confirmation of Proof: $\forall n \in \mathbb{N}, \ \pi (n) \geqslant \frac{\log n}{2\log 2}$
- How do I prove this question involving primes?
- What exactly is the definition of Carmichael numbers?
- I'm having a problem interpreting and starting this problem with primes.
- Decimal expansion of $\frac{1}{p}$: what is its period?
- Multiplying prime numbers
- Find the number of relatively prime numbers from $10$ to $100$
- A congruence with the Euler's totient function and sum of divisors function
- Squares of two coprime numbers
Related Questions in PRIMALITY-TEST
- A variation on Giuga's conjecture
- A congruence involving Chebyshev polynomials
- Is there any simple primality test for large integer for students in the high school level?
- What is the most speed efficient primality test available
- A congruence involving Lucas polynomials
- Primality test for repunits in bases $\pm 3$
- Why $n=4$ the only integer satisfying :$-1+2^{n²+n+41}$ to be prime from $n=0$ to $n=40$?
- How to prove that if $n$ is prime then ${{n}\choose{i}} = 0 \mod{n}$?
- Is there any pseudoprime, $p$ such that $p\not\equiv\pm{1\bmod{18}}$?
- How many operations are required to check the congruence $(x+a)^n \equiv x^n + a \pmod{x^r-1, n}$?
Trending Questions
- Induction on the number of equations
- How to convince a math teacher of this simple and obvious fact?
- Find $E[XY|Y+Z=1 ]$
- Refuting the Anti-Cantor Cranks
- What are imaginary numbers?
- Determine the adjoint of $\tilde Q(x)$ for $\tilde Q(x)u:=(Qu)(x)$ where $Q:U→L^2(Ω,ℝ^d$ is a Hilbert-Schmidt operator and $U$ is a Hilbert space
- Why does this innovative method of subtraction from a third grader always work?
- How do we know that the number $1$ is not equal to the number $-1$?
- What are the Implications of having VΩ as a model for a theory?
- Defining a Galois Field based on primitive element versus polynomial?
- Can't find the relationship between two columns of numbers. Please Help
- Is computer science a branch of mathematics?
- Is there a bijection of $\mathbb{R}^n$ with itself such that the forward map is connected but the inverse is not?
- Identification of a quadrilateral as a trapezoid, rectangle, or square
- Generator of inertia group in function field extension
Popular # Hahtags
second-order-logic
numerical-methods
puzzle
logic
probability
number-theory
winding-number
real-analysis
integration
calculus
complex-analysis
sequences-and-series
proof-writing
set-theory
functions
homotopy-theory
elementary-number-theory
ordinary-differential-equations
circles
derivatives
game-theory
definite-integrals
elementary-set-theory
limits
multivariable-calculus
geometry
algebraic-number-theory
proof-verification
partial-derivative
algebra-precalculus
Popular Questions
- What is the integral of 1/x?
- How many squares actually ARE in this picture? Is this a trick question with no right answer?
- Is a matrix multiplied with its transpose something special?
- What is the difference between independent and mutually exclusive events?
- Visually stunning math concepts which are easy to explain
- taylor series of $\ln(1+x)$?
- How to tell if a set of vectors spans a space?
- Calculus question taking derivative to find horizontal tangent line
- How to determine if a function is one-to-one?
- Determine if vectors are linearly independent
- What does it mean to have a determinant equal to zero?
- Is this Batman equation for real?
- How to find perpendicular vector to another vector?
- How to find mean and median from histogram
- How many sides does a circle have?
For numbers of ~315k digits, they either need to be of a special form (e.g. Proth, LLR, Mersenne, etc.) that allows a fast proof, or you will have to settle for a PRP test. The record for general form proofs is about 35k digits, so 315k digits is far beyond today's practical limit. ECPP is polynomial time in practice, and we don't know anything faster for general-form proofs.
Re PRP tests, your choices include Fermat, Euler (Jacobi), Euler (Plumb base 2), Miller-Rabin, BPSW, Frobenius and its variants, and more. All polynomial in the size of the input. Of course for speed you want some simple pre-tests such as trial division for small factors (perhaps implemented as a gcd with a large primorial, but it's the same thing), but after that you really need to run one of the tests.
Also critical at this size is the implementation. In a test I did a few years ago with a 140k digit PRP, PFGW's Fermat test took under 6 minutes, GMP took 30 minutes, and Pari/GP took 63 minutes. PFGW uses gwnum which is highly optimized for this operation on large numbers, while the GMP library is massively more portable, much easier to use in implementations, and is faster for smaller inputs (under ~2000 digits). Using something other than these is probably going to be really, really slow.
The good news (maybe) is that it took only 6 minutes to run a Fermat test on a single 140k number. 315k digits should be reasonably practical. You could also run a few numbers in parallel if desired. Once you find something that passes, at this size it's very likely to be prime, and running a more stringent test like BPSW for more certainty should finish under a day.
Realistically at this size, just use PFGW. Once you found a candidate, you can try more bases or apply more stringent tests using various other tools. If you have a range you're looking in, you want to use a sieve of some sort to efficiently remove small divisors.