Skip to main content

Questions tagged [primality-test]

An algorithm for determining whether an input number is prime.

Filter by
Sorted by
Tagged with
5 votes
0 answers
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}$$ ...
YesYer's user avatar
  • 53
1 vote
2 answers
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,...
PrimeTester's user avatar
0 votes
0 answers
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 ...
299792458's user avatar
  • 243
1 vote
1 answer
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 ...
299792458's user avatar
  • 243
1 vote
2 answers
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 ...
Perri P's user avatar
  • 11
0 votes
2 answers
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 ...
Ekaveera Gouribhatla's user avatar
0 votes
0 answers
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 ...
Saku's user avatar
  • 199
4 votes
0 answers
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 ...
Sil's user avatar
  • 17k
2 votes
0 answers
61 views

Conjecture about Proving Primality of Fermat numbers by Elliptic Curves technic

In 2008 and 2009, Denomme-Savin and Tsumura provided 2 papers providing a Primality Test for Fermat numbers based on Elliptic Curves technic: $$ \text{Let } DST(x)= \frac{\displaystyle x^4+2x^2+1}{\...
Tony Reix's user avatar
  • 393
1 vote
1 answer
84 views

Practical fast primality test

I want to test the primality of some numbers. To do this I have tried PARI/GP and from the command line: ...
Fabius Wiesner's user avatar
0 votes
1 answer
68 views

Primality test based on the properties of Pascal Triangle partial sum of a given diagonal

The test involves a partial sum of a diagonal whose second element is a prime. Because of the symmetry of Pascal Triangle each prime has two diagonals parallel to the sides of the triangle. These two ...
user25406's user avatar
  • 1,058
3 votes
2 answers
151 views

New conjecture? $(\varphi(n))! = -1 \pmod n \iff n$ is prime (nearly the same as Wilson's) [duplicate]

$$ (n-1)! = -1 \pmod n \text{ iff } n \text{ is prime}, \text{ is Wilson's theorem,} $$ But coincidentally for now the expression passed to factorial is $n - 1$ which is (iff $n$ is prime) equal to $\...
SeekingAMathGeekGirlfriend's user avatar
2 votes
0 answers
41 views

AKS primality test lower bound

In this paper, in the first part of Section 7, D.J. Bernstein mentions that the original AKS paper (Lemma 4.4 and its proof) uses an extremely crude lower bound for the number of elements in $G$ (as ...
DisplayName's user avatar
0 votes
1 answer
87 views

How to find what $b$ satisfies $b^{176} \equiv -1 \mod 353$

How do I find what $b$ satisfies $b^{176} \equiv -1 \mod 353$? This all comes from the original problem of using Proth's Theorem to prove the primality of $353$. Using Wolfram Alpha, $3^{176} \equiv -...
Cotton Headed Ninnymuggins's user avatar
0 votes
1 answer
47 views

Congruence in AKS algorithm

In the AKS algorithm, we consider the congruence $$(X+a)^n \equiv X^n + a \pmod{X^r-1}$$ in $(\mathbb{Z}/n\mathbb{Z})[X]$. The motivation for this is that when taking $r$ in the order of $\log n$, we ...
user avatar
1 vote
0 answers
269 views

An explanation of why the Lucas-Lehmer Primality Test works: is this OK?

I've always wondered why the Lucas-Lehmer Primality Test works. After studying it, I came up with an explanation. I hope you can help me confirm and complete it. A Mersenne prime is a number of the ...
CuriousAboutNumbers's user avatar
4 votes
0 answers
236 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 ...
Jaynot's user avatar
  • 737
0 votes
1 answer
83 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 ...
Matrend's user avatar
2 votes
0 answers
97 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 ...
settheory's user avatar
1 vote
0 answers
55 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?
richard gostanian's user avatar
0 votes
0 answers
95 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 ...
mary's user avatar
  • 11
2 votes
0 answers
50 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)}$$...
Tony Reix's user avatar
  • 393
0 votes
1 answer
66 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: <...
Mathematically Clueless's user avatar
3 votes
0 answers
131 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 ...
Aurel-BG's user avatar
  • 141
2 votes
1 answer
268 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}...
kijinSeija's user avatar
1 vote
0 answers
65 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 ...
sibillalazzerini's user avatar
-1 votes
1 answer
66 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 ...
mathquester's user avatar
1 vote
0 answers
31 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 ...
mathquester's user avatar
3 votes
1 answer
97 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 $\...
mathquester's user avatar
-1 votes
1 answer
110 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^{\...
mathquester's user avatar
1 vote
0 answers
55 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 ...
kijinSeija's user avatar
0 votes
0 answers
58 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 ...
Noman's user avatar
  • 99
1 vote
1 answer
94 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 ...
vvg's user avatar
  • 3,341
2 votes
1 answer
82 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$ ...
Géry Ogam's user avatar
2 votes
1 answer
172 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 ...
Peter's user avatar
  • 85.1k
1 vote
0 answers
254 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}^...
user140242's user avatar
0 votes
0 answers
82 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 - ...
kijinSeija's user avatar
1 vote
0 answers
38 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-...
Jaume Oliver Lafont's user avatar
1 vote
2 answers
208 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-...
kijinSeija's user avatar
4 votes
0 answers
51 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 ...
Lumorti's user avatar
  • 41
0 votes
0 answers
36 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 ...
Vi0's user avatar
  • 331
0 votes
0 answers
103 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 ...
kijinSeija's user avatar
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 ...
J. M. Bergot's user avatar
2 votes
1 answer
132 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 ...
fgrieu's user avatar
  • 1,768
12 votes
1 answer
535 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 ...
kijinSeija's user avatar
3 votes
1 answer
266 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 ...
NiRvanA's user avatar
  • 57
0 votes
0 answers
47 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 ...
SlipEternal's user avatar
  • 10.5k
3 votes
1 answer
230 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 ...
user25406's user avatar
  • 1,058
4 votes
1 answer
140 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 ...
TPC's user avatar
  • 181
0 votes
1 answer
68 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. ...
Isaac Brenig's user avatar
  • 1,405

1
2 3 4 5
9