Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [primality-test]

An algorithm for determining whether an input number is prime.

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input).

401 questions
21
votes
3 answers

Primality testing for 64 bit numbers

For very small numbers, say 32 bits unsigned, testing all divisors up to the square root is a very decent approach. Some optimizations can be made to avoid trying all divisors, but these yield marginal improvements. The complexity remains $O(\sqrt…
user65203
3
votes
2 answers

Check primality of large prime by Miller-Rabin

I need to check whether $7150309735704750359$ is prime. Naive methods, Sieve algorithm and AKS didn't work. So I tried Miller-Rabin. Now it says here that checking for some small set of $a$ is enough. But the data given are for numbers smaller than…
Faustus
  • 143
2
votes
1 answer

Combining strong pseudoprime test to base 2 and an Elliptic Curve test

I read Kubra Nari, Enver Ozdemir and Neslihan Aysen Ozkirisci: Strong pseudoprimes to base 2, in The Ramanujan Journal, 2022-04-26 (paywalled¹). Compared to a free earlier version at arXiv, the text is improved², and there are some algorithmic…
fgrieu
  • 1,758
2
votes
1 answer

implementing Lucas Primality Test

Im trying to implement the Lucas Primality test as described in FIPS 186-3 C.3.3. However, ive hit a problem: im just testing my code with the value 33, im getting $D = 5$ as the first value for $\left(\frac{D}{33}\right) = -1$. with that, at step…
calccrypto
  • 235
2
votes
1 answer

Why it is so difficult to perform primality test on huge fermat numbers?

I am not good in computer programming at all, but I know that it will take a lot of times to perform primality test on huge numbers (10 million or billion of digits). But I particularly get interested on fermat numbers,which is numbers of the form…
Bulldogisthebestdog
  • 21
1
vote
0 answers

Recursive boolean function for primality testing

Let us define a logical function $p(n)$ that returns the primality of numbers of $n$ bits $x_{n-1}x_{n-2}\dots{x_0}$. Assume there is some recursive definition $p(n)=f(p(n-1))$ Let us start from two-bit numbers of the form $x_1x_0$ decimal binary…
Jaume Oliver Lafont
  • 5,212
1
vote
0 answers

Is number of prime factors in P?

We know primality is in P which gives an answer for all prime numbers that the number of prime factors of a prime number is 1. Is there an algorithm in P that would give answers for composite numbers about the number of their prime…
Alexander Weps
  • 11
0
votes
0 answers

Are there good probabilistic primality tests which give definitely-prime vs probably-compound outcome?

Typical probabilistic primality test (e.g. Miller-Rabin) tend to give definite outcome in case of composite number and iffy outcome in case of a prime number. Are there iterated primality tests with the reverse propery, i.e. they either give…
Vi0
  • 331
0
votes
0 answers

Small Miller-Rabin bases for 82 ... 307 bits

Let's suppose we want to test the positive integer $n$ for primality using Miller-Rabin and a few pre-chosen bases ($a$). Previous results ([1], [2] and Theorem 1.1 in [3]) indicate that if $n$ is smaller than $2^{81}$, then the first 13 primes are…
pts
  • 607
0
votes
1 answer

Primality test with form of n

I was reading about primality test and at the wikipedia page it said that we just have to test the divisors of n from 2 to √n This part about √n is fine But the next part is hard to understand quote : "The algorithm can be improved further by…
xuoimai
  • 89
-1
votes
4 answers

Can an odd number be evenly divisible by an integer bigger than its square root?

I've seen this before on a programming website. It was an efficient algorithm to check if a number is prime. I've never seen any proof for this algorithm, so I'd like someone to provide it here. The algorithm operates as follows: Step #1: Check if…
Saif Taher
  • 160
-3
votes
1 answer

Is this a new deterministic primality test???

$|(x-1)^p -(x^p-1)-(x^{p-1} -2)| \equiv -1 \mod p$ It seems to work. Can anyone refute it or improve it?
user124808
  • 19