# Questions tagged [primality-test]

An algorithm for determining whether an input number is prime.

408 questions
Filter by
Sorted by
Tagged with
48 views

### Justification for the Sequence in the Lucas-Lehmer Primality Test for Mersenne Primes.

A Mersenne prime is a prime number of the form $M_p = 2^p -1$, for $p$ a prime number. We have the sequence $$s_i = \begin{cases} 4, \text{ if } i = 0;\\ s_{i-1}^2 - 2 \text{ otherwise. }\end{cases}$$ ...
• 53
1 vote
165 views

### Optimizing Miller-Rabin by selecting bases calculated from the number to test

(First to say, i am not a mathematician, so possibly this is all well known since 1000 years and boring for you. Tell me if so...) I tried to optimize Miller-Rabin prime test by selecting better bases,...
34 views

### Why is it that for prime factors $p_i$ of a Carmichael number $n$, the identity $(p_i - 1) \mid (n-1)$ holds? [duplicate]

Carmichael numbers are composite $n$ for which $$a^{n-1}\equiv1\quad(mod\ n)$$ is true for every prime $a<n$. Part of a proof I'm currently working through includes the condition that for ...
• 243
1 vote
30 views

### Question about the proof that composite numbers are Euler pseudoprimes to at most half of their coprime bases [closed]

Euler pseudoprimes are composite numbers $n$ for which the congruence $$a^{\frac{n-1}{2}}\equiv \left(\frac{a}{n} \right) \quad (mod \ n)$$ holds, where $\left(\frac{a}{n} \right)$ is the Jacobi ...
• 243
1 vote
56 views

### Changing the uniform distribution range of the Miller-Rabin primality test

When implementing the Miller-Rabin probabilistic primality test - determine if $N$ is likely prime; prior to running the test for performance and robustness reasons one typically uses a list of the ...
• 11
66 views

### Manual Primality Testing methods

I am curious to know some other interesting manual methods for Primality testing. Here is one of the methods I know as of now. Suppose let us say, we need to check whether $397$ is Prime or not. We ...
• 13.2k
23 views

### Miller-Rabin primality test and random

Miller-Rabin primality test need random choosing number in each round. Time of random() is negligible compared to time of round ? Problem is, how to generate big random numbers? Maybe best would be ...
• 199
247 views

### Is $N=3\cdot 2^k+1$ prime if and only if $2^{N-1}\equiv 1 \pmod N$?

Is the following statement true? Let $k\geq 1$ be an integer and $N=3\cdot 2^k+1$. Then $N$ is a prime prime if and only if $2^{N-1}\equiv 1 \pmod {N}$ One implication is simply a Fermat's Little ...
• 17k