# Questions tagged [primality-test]

An algorithm for determining whether an input number is prime.

393 questions
Filter by
Sorted by
Tagged with
185 views

### Generating a random prime

How can I generate a random prime of the form $2^ab+1$ for small $b$ value without actually creating a list of such primes, and then choose from the list at random? For example: I can generate a ...
63 views

### Chebyhev polynomials and Primality Testing

It is a well known Theorem that an odd positive integer $n$ is prime if and only if $T_{n}(x) \equiv x^n \pmod{n}$, where $T_{n}(x)$ is the $n^{th}$ Chebyshev polynomial of the first kind. Do we ...
73 views

### Is there a base such that the fermat test is always correct?

The Fermat primality test base $a$ says $N$ is probably prime if $a^{N-1}=1\mod N$. $N$ is a pseudoprime base $a$ if it is probably prime, but not prime. Does there exist a base $a$ such that the only ...
1 vote
33 views

### For the Miller-Rabin primality test why must the witnesses be chosen randomly?

Why do the witnesses in the Miller_rabin primality test have to be chosen randomly? Wouldn't just a deterministic set of witnesses, say starting with 1 and 100 or 1000, etc. apart work just as well?
43 views

### Characterization of prime rings

Let $R$ be a noncommutative ring without identity. Recall that a ring $R$ is said to be a prime ring if $aRb=(0), a,b\in R$ implies that $a=0$ or $b=0$. I have to prove that $R$ is a prime ring if ...
33 views

### Can you prove that my candidate PRP test for Wagstaff numbers (based on Elliptic Curve Primality Proving for Fermat numbers) is a true Primality Test?

The test is explained and described in the forum of the GIMPS project: https://www.mersenneforum.org/showthread.php?t=28658 In short: $$x_1=W_3=3 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$$...
18 views

1 vote
61 views

### Given $x$ find minimum positive $N$ for which the following is composite $1^x+2^x+3^x+4^x+\cdots+N^x$

Problem: Given positive integer $x$ find minimum value of positive integer $N$ starting which the following is always composite $$1^x+2^x+3^x+4^x+\cdots+N^x$$ My Thoughts: This is a followup to this ...
63 views

### What's the link from $2^u-1$ to the multiplicative order?

I am reading this paper, but I will write everyting I need for my question here. So, long story short, we have a proth-number $n$, i.e. $n = h\cdot 2^k+1$ for odd $h<2^k$. We are looking for ...
27 views

### Is there a finite set $\mathfrak{D}$ such that $\left(\frac{h\cdot 2^k+1}{p}\right) \neq 1$ for all $p\in\mathfrak{D}$?

I am reading this paper, but you don't have to, since I will write down here what is needed for the question. So, there is this test: Now the paper raises the question whether , for fixed $h$, there ...
27 views

### Jacobisymbol for Proth-Numbers

As some might know, I am reading this paper. I did my own research and got some results. So let's say we have a Proth-number $n = h\cdot 2^k+1$ with $h$ odd, $h<2^k$. Now we look for a $D$ such ...
89 views

1 vote
49 views

### Checking if $(2^p+1)/3$ is prime with multiplicative order and recurrence relation?

Here is what I observed : Let $(2^p+1)/3$ be a Wagstaff number $W_n$. Let the sequence $a_n = ord({a_{n-1}},\frac{2^{p}+1}{3}), a_0 = 2p$, where $p$ is a prime number. Then $W_n$ is prime if the ...
57 views

### Is this a correct expression for a primality test using the Dirac delta?

$$\int_{1/2}^{n+1/2} \delta(1 - \cos(2 \pi x) + |sin(n \pi / x)|) \,dx$$ The idea here is $1- cos(2 \pi x)$ is zero at the integers, positive otherwise, and $|sin(n \pi / x)|$ is zero at real factors ...
56 views

### Sieving the range $[a,b]$

In Sieve of Eratosthenes we sieve the range $[1,N]$ by crossing out 1, then crossing out 2 and multiples of 2, then take 3 and then cross out 3 and multiples of 3 and so on... picking the next ...
73 views

### Is $n$ always a strong probable prime to base $n - 1$?

Here is the Miller–Rabin extension to Fermat’s little theorem: If $p$ is an odd prime and $p - 1 = 2^s d$ with $d$ odd, then for every $a$ coprime to $p$, either $a^d ≡ 1 \pmod p$ or there exists $r$ ...
161 views

### Is $P+1$ prime for the perfect number $P$ corresponding to the exponent $74207281$?

The even perfect numbers are closely related to the Mersenne primes. We currently know $51$ Mersenne primes and hence $51$ perfect numbers. It has already been checked for which of those perfect ...
1 vote
236 views

1 vote
36 views

### 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-...
196 views