Questions tagged [primality-test]
An algorithm for determining whether an input number is prime.
393
questions
4
votes
0
answers
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 ...
- 737
0
votes
1
answer
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 ...
- 1
2
votes
0
answers
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 ...
- 113
1
vote
0
answers
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?
0
votes
0
answers
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 ...
- 11
2
votes
0
answers
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)}$$...
- 363
0
votes
0
answers
18
views
$n$ odd composite number, at most $\frac{n-1}{4}$ integers $a$ such that $n$ is a strong pseudoprime with respect to $a$
The problem I'm trying to solve is:
Let $n$ be an odd composite number. Show there are at most $\frac{n-1}{4}$ integers $a$ such that $1 \leq a \leq n$ and $n$ is a strong pseudoprime with respect to $...
- 99
0
votes
1
answer
44
views
Faster primality testing? [closed]
I have to make a list of primes, and I found out that all primes are of the form 6n+1 or 6n+5 (however not all numbers of this form are prime). Thus, I use it to find primes more quickly as such:
<...
3
votes
0
answers
87
views
A question about a primality test for $3^n-2$ and $N-1$ or $N+1$ factorization
Context :
I'm interested by numbers, prime and composite numbers and their properties, perfect and hyperperfect numbers and primality testing.
Recently, I discovered the Lucas-Lehmer primality test ...
- 31
0
votes
0
answers
79
views
Is 3 a primitive root to all potential Mersenne primes?
Potential Mersenne primes are of form $2^p - 1$ where p is an odd prime.
A primitive root would imply that:
$3^M \equiv 3 mod(M)$ => aka Fermats little theorem works
Can you please provide proof of ...
- 19
1
vote
1
answer
239
views
Lucas-Lehmer test for Mersenne and Wagstaff numbers?
Here is what I observed :
Let $M_p = 2^p-1$ for Mersenne numbers and $W_p = (2^p+1)/3$ for Wagstaff numbers with $p$ a prime number > $2$
Let the sequence $S_i = 6 \cdot S_{i-1}^2 + 18 \cdot S_{i-1}...
- 333
1
vote
0
answers
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 ...
- 460
-1
votes
1
answer
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 ...
- 160
0
votes
0
answers
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 ...
- 160
2
votes
0
answers
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 ...
- 160
3
votes
1
answer
89
views
Generalized Pépin-Test (Problem understanding a paper)
I am reading this paper (but you don't need to, I will write down what is needed for the question), and I have difficulty understanding a certain conclusion.
$(1.1)\ \ $ $n = 2^k+1$ is prime $\...
- 160
-1
votes
1
answer
105
views
Proth's Theorem [duplicate]
I am trying to understand Theorem (2.1) in this Paper.
Here it is:
Let $n = h\cdot 2^k+1$ with $0<h<2^k$ and $h$ odd.
If $\left(\frac{D}{n}\right) = -1$, then:
$n$ is prime $\Leftrightarrow D^{\...
- 160
1
vote
0
answers
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 ...
- 333
0
votes
0
answers
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 ...
- 79
0
votes
0
answers
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 ...
- 3,133
2
votes
1
answer
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$ ...
- 251
2
votes
1
answer
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 ...
- 82.2k
1
vote
0
answers
236
views
Remarks on Lucas–Lehmer test
I was looking for a way to derive the elements of the sequence in a different way in the Lucas–Lehmer test with $ \quad p \quad$an odd prime.
we know that $ \quad s_0=4 \quad $ and $ \quad s_i=s_{i-1}^...
- 617
0
votes
0
answers
71
views
Formula that is divided only by Wagstaff primes?
Here is what I observed :
Let's put the number $W_p = \frac{2^p+1}{3}$ where $p$ is prime and $W_p$ is a Wagstaff number.
Let's put the formula $\omega_p = (\frac{1}{2} (1 + i \sqrt7))^{(\frac{2^{p - ...
- 333
1
vote
0
answers
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-...
- 5,144
0
votes
2
answers
196
views
Condition for $8p+1$ divides $2^p-1$?
Here is what I observed :
Let $8p+1 = (2a-1)^2+64(2b-1)^2$ with $a$ and $b$ be a positive integers, $p$ and $8p+1$ both prime numbers.
Then $8p+1$ divides $2^p-1$ only if you can write $8p+1$ as $(2a-...
- 333
4
votes
0
answers
49
views
Testing if a number has a positive divisor of a specific form
My problem is the following:
Given a positive integer $n$, determine if $n$ has a divisor of the form $d=3+8k$ where $k$ is a non-negative integer.
I'm aware there are fast algorithms for checking ...
- 41
0
votes
0
answers
31
views
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 ...
- 331
0
votes
0
answers
94
views
Primality test for numbers of the form $\frac{a^p-1}{a-1}$?
This question is cross-linked with Mathoverflow and I didn't get an answer for the question.
Here is what I observed :
Inspired by Lucas-Lehmer primality test, I think I made a primality test for ...
- 333
1
vote
1
answer
129
views
23 and arithmetic progression
Starting at prime $23$,
$$
23 + 3 \cdot n \cdot(n+1)
$$
is prime for $n=1$ to $21$. Is there
a starting prime with more successes? Does this suggest that $23$ from
$n=1$ to $1000$ would have the ...
- 902
2
votes
1
answer
120
views
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 ...
- 1,631
12
votes
1
answer
517
views
Primality testing with binomial coefficients
Here is what I observed :
Let $n$ be a natural number greater than 2.
Let $A = 2\cdot\binom{3n+1}{n}-\binom{3n}{n-1}+\binom{3n-1}{n-2}$
Let $p=2n+1$
$p$ is prime iff $A \equiv 2 \pmod{p}$
You can run ...
- 333
3
votes
1
answer
196
views
Randomized algorithm for finding a prime number between $n$ and $2n$
I have already seen some threads conjecturing that there is at least one prime between $n$ and $2n$. I am given an exercise, where I have relaxed this conjecture to the assumption that between $n$ and ...
- 57
0
votes
0
answers
33
views
Asymptotic probability of prime divisors
I was curious about methods of finding primes. One method is to keep a list of the first $n$ primes, then check if the input modulo any prime less than its square root is zero. If none of those primes ...
- 10.5k
3
votes
1
answer
199
views
Primality test based on the properties of Pascal Triangle sum of a given row
I will list the properties of a row of Pascal triangle that will be used in the test.
1-Every number of a given row $n$ is divisible by the row number $n$ if the row number is a prime except of course ...
- 970
4
votes
1
answer
121
views
A question on (trigonometric) prime counting function and twin prime counting function
Consider the following sum:
$$S(t)=\sum_{n=5}^t\sin^2\left(\frac{π\Gamma(n)}{2n}\right)$$
As we can see this approximates $π(t)$ i.e. prime counting function pretty well.
For details visit this paper ...
- 181
0
votes
1
answer
64
views
Tweaking Fermat's primality test - Why does it work and should I expect different results?
Fermat's primality test states that for any $p$ as a positive odd integer, IF:
$$a^{{p-1}}\equiv 1{\pmod {p}}$$
or in a different way:
$$a^{{p}}-a\equiv 0{\pmod {p}}$$
THEN $p$ is probably prime.
...
- 1,395
0
votes
1
answer
63
views
$n$ is prime if $M_n\equiv 1\pmod{n}$
Let $M_n$ the $n$-th Mersenne number (A000225).
I am trying to prove that if n is prime then $2^n-1=M_n\equiv 1\pmod{n}$. I'm sure it should be easy to get out of fermat's little theorem ($c^{n-1}\...
- 1,170
2
votes
1
answer
73
views
A Pocklington theorem failed proof of mine that baffles me
With the following conditions for some $a,p$, we can assure that $\mathcal N$ is a prime, where $\mathcal P$ denotes a set of all primes, as the Pocklington's theorem stated
$$
\begin{align}
a^{\...
- 1,025
1
vote
2
answers
41
views
$a \in \mathbb{Z}$,$(a^{n-1}\equiv 1 (mod~n) $ and $\forall q|n-1$, $q$ is prime, $a^q\not\equiv 1 (mod~n)$ then $ n$ is a prime number
Consider an integer $n \geq 2$ verifying:
$$ \exists a \in \mathbb{Z}, (a^{n-1} \equiv 1 (\textrm{mod}\ n) \text{ and }\forall q|n-1, q\text { is prime numbre }, a^q\not\equiv 1 (\textrm{mod}\ n).$$...
- 1,249
1
vote
1
answer
128
views
Primality test for numbers of the form $(10^p-1)/9$ (and maybe $((10 \cdot 2^n)^p-1)/(10 \cdot 2^n-1)$)
This question is successor of Primality test for numbers of the form (11^p−1)/10
Here is what I observed:
For $(10^p-1)/9$ :
Let $N$ = $(10^p-1)/9$ when $p$ is a prime number $p > 3$.
Let the ...
- 333
10
votes
4
answers
551
views
Primality test for numbers of the form $(11^p-1)/10$
This question is the successor of Primality test for numbers of the form (3^p−1)/2
Here is what I observed:
Let $N$ = $(11^p-1)/10$ when $p$ is a prime number $p > 3$.
Let the sequence $S_i=S_{i-1}^...
- 333
0
votes
1
answer
179
views
Primality test for numbers of the form $(3^p-1)/2$
Here is my observation :
Let $N$ = $(3^p-1)/2$ when $p$ is a prime number $p > 3$
Let $S_i=S_{i-1}^3-3 S_{i-1}$ with $S_0=52$ . Then $N$ is prime if and only if $S_{p-1} \equiv S_{0}\pmod{N}$.
I ...
- 333
0
votes
0
answers
26
views
what is q & n in Primality Testing using Elliptic Curves
Shafi Goldwasser and Joe Kilian's paper on Primality Testing using Elliptic Curves under the header "A PRIMALITY CRITERION USING ELLIPTIC CURVES" on page 9 contains a formula
$$\ q > n^\...
0
votes
0
answers
94
views
A new primality test for prime of the form $(n^p-1)/(n-1)$ and $(n^p+1)/(n+1)$ when $p>n$?
Here is what I observed:
Let $R_{p}$ = $(n^p-1)/(n-1)$ or $(n^p+1)/(n+1)$ when $n$ is a positive integer $> 1$ and $p$ a prime number $> 2$ and $p > n$.
$R_{p}\text{ is a prime iff: } \ s_{p}...
- 333
1
vote
0
answers
58
views
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 ...
0
votes
0
answers
94
views
How to repair this false statement about idoneal numbers?
In the german wikipedia , I found this site about idoneal numbers.
The mentioned statement is false :
$D=1848$ is an idoneal number and $m=1849$ is an odd number.
$x^2+1848y^2=1849$ has only one ...
- 82.2k
2
votes
1
answer
91
views
Primality criterion for Mersenne numbers involving Euler's totient function
I am looking for a proof of the following claim:
Let $M_p=2^p-1$ where $p$ is a prime . Denote Euler's totient function by $\varphi(n)$ . Then,
$$M_p \text{ is prime iff } \varphi(M_p) \equiv 2 \pmod{...
- 12.8k
1
vote
2
answers
689
views
Miller Rabin primality accuracy
I have been reading about the Miller-Rabin primality test. So far I think I got it except the part where the accuracy is stated.
E.g from wiki
The error made by the primality test is measured by the ...
- 1,581
1
vote
1
answer
88
views
Primality Formula Conjecture
Primality Formula Conjecture
To test any $(6x-1)$ numbers for primality.
$$
4^{3x-1} \bmod (6x-1)
$$
If that is equal to 1 then $(6x-1)$ is prime.
To test any $(6x+...
- 31