Questions tagged [primality-test]

An algorithm for determining whether an input number is prime.

Filter by
Sorted by
Tagged with
1 vote
1 answer
42 views

Miller-Rabin primality test final decision.

I feel like this question is more about math than, programming but it will include some simple code for the Miller-Rabin test (in scheme-lisp). ...
user avatar
  • 11
1 vote
1 answer
115 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 ...
user avatar
2 votes
1 answer
90 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 ...
user avatar
  • 1,424
12 votes
1 answer
454 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 ...
user avatar
3 votes
1 answer
92 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 ...
user avatar
  • 33
0 votes
0 answers
31 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 ...
user avatar
  • 10.2k
4 votes
1 answer
123 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 ...
user avatar
  • 822
3 votes
0 answers
75 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 ...
user avatar
  • 169
0 votes
1 answer
61 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. ...
user avatar
  • 1,365
0 votes
1 answer
53 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}\...
user avatar
2 votes
1 answer
41 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 $$a^{\mathcal N-1}\equiv 1 ...
user avatar
1 vote
2 answers
33 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).$$...
user avatar
  • 1,203
1 vote
1 answer
102 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 ...
user avatar
10 votes
4 answers
500 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}^...
user avatar
1 vote
1 answer
152 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 ...
user avatar
0 votes
0 answers
24 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^\...
user avatar
0 votes
0 answers
90 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}...
user avatar
1 vote
0 answers
43 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 ...
user avatar
0 votes
0 answers
86 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 ...
user avatar
  • 78.3k
2 votes
1 answer
64 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{...
user avatar
  • 12.5k
1 vote
2 answers
234 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 ...
user avatar
  • 1,507
1 vote
1 answer
78 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+...
user avatar
2 votes
1 answer
69 views

Confusion on the original Lucas test

I am currently researching on all primality tests deriving from Lucas' original paper Théorie des Fonctions Numériques Simplement Périodiques, which is of course known for its great deal of confusion. ...
user avatar
0 votes
0 answers
62 views

Legendre symbol in the Fibonacci primality test

The Legendre symbol $\left(\dfrac{5}{p}\right)$ is used in the Fibonacci primality test. I understand its significance, but why did 5 show up and not some other prime? Is it because $p$ is written in ...
user avatar
1 vote
0 answers
47 views

Lower bound on the number of distinct polynomials of degree less than $t$

In the Primes in P paper there is a section which states that there are at least $t+l \choose t-1$ distinct polynomials of degree $<t$ in a certain group. I think this can be deduced only from the ...
user avatar
1 vote
0 answers
37 views

Probabilistic primality test that might return a prime as a composite but never a composite as prime

I am currently analyzing the AKS algorithm and I saw that for practical purpose usually only probabilistic test are used due to faster runtime. I know that the probabilities in these test can be made ...
user avatar
1 vote
1 answer
213 views

Speedup Primality Test

I'm trying to speedup my primality test where every $n \in \mathbb{Z}$ is prime if all lattice points on $x+y=n$ are visible from the origin. It's really inefficient at the moment because it requires ...
user avatar
  • 805
0 votes
1 answer
231 views

Is this a new Primality Test? [closed]

Every $n \in \mathbb{Z}$ is prime if all lattice points on $x+y=n$ are visible from the origin. Graphed points on $x+y=n$ not visible from the origin for potential primes. ...
user avatar
  • 805
4 votes
1 answer
228 views

Pick's Theorem and Primes.

For $n$ prime, each of the remaining triangles contains exactly the same number of grid points. This was proved here. However, is the converse true i.e., triangles containing exactly the same number ...
user avatar
  • 805
5 votes
1 answer
354 views

Is Secp256k1's prime prime?

Bitcoin protocol relies on the elliptic curve secp256k1 for its cryptographic security. For that purpose the integer number $p = 2^{256}-2^{32}-977$ must be prime. How do they know $p$ is actually ...
user avatar
1 vote
1 answer
184 views

How is the AKS primality test Rosetta code so simple?

Skip to the end to see alternative question. The following is a Python implementation of the AKS Primality Test. ...
user avatar
1 vote
1 answer
32 views

Is the BPSW-test always correct for special kinds of numbers?

Here https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test a powerful primality test is mentioned for which no counterexample is known and it is claimed that none upto $2^{64}$ exists. Can ...
user avatar
  • 78.3k
-1 votes
2 answers
152 views

Primality Test in Finite Fields

Is there a name for the following primality test? Was it ever discussed in literature? We want to test if some $x \in \mathbb{N}$ is a prime number. Let $p = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot \...
user avatar
  • 245
5 votes
1 answer
362 views

Let $n=apq+1$. Prove that if $pq \ | \ \phi(n)$ then $n$ is prime.

Let $p$ and $q$ be distinct odd primes and $a$ be a positive integer with $a<p<q$. I need to prove that if $pq \ | \ \phi(n) $ then $n$ is prime. The proof for the trivial case when $a=2$ is ...
user avatar
  • 222
3 votes
1 answer
73 views

Primality test for specific class of $N=k \cdot 2^n+1$

Can you prove or disprove the following claim: Let $N=k \cdot 2^n+1$ be a natural number that is not a perfect square such that $ 2 \nmid k$ , $n>2$ . Let $c$ be the smallest odd prime number such ...
user avatar
  • 12.5k
25 votes
3 answers
738 views

$n$ is prime iff $\binom{n^2}{n} \equiv n \pmod{n^4}$?

Can you prove or disprove the following claim: Let $n$ be a natural number greater than two , then $$n \text{ is prime iff } \binom{n^2}{n} \equiv n \pmod{n^4}$$ You can run this test here. I have ...
user avatar
  • 12.5k
0 votes
1 answer
200 views

Every strong pseudoprime is an Euler-Jacobi pseudoprime to base $b$

Prove that every strong (i.e. Miller-Rabin) pseudoprime to base $b$ is also an Euler-Jacobi pseudoprime to base $b$ I am trying to prove the above but I am struggling. Any hints?
user avatar
  • 279
3 votes
2 answers
230 views

A generalization of Hurwitz's theorem about prime numbers

Can you prove or disprove a generalization of Hurwitz's theorem about prime numbers given below? Theorem.(Hurwitz) Let $F_n(x)$ denote an irreducible factor of degree $\phi(n)$ of $x^n-1$. Then if ...
user avatar
  • 12.5k
5 votes
1 answer
155 views

Primality testing using cyclotomic polynomials

Can you prove or disprove the following claim: Let $\Phi_m(x)$ be the mth cyclotomic polynomial , and let $n$ be a natural number greater than one . If there exists an integer $a$ such that $$\Phi_{n-...
user avatar
  • 12.5k
1 vote
1 answer
86 views

How does the AKS algorithm work?

I looked at the article of AKS in wikipedia (https://en.wikipedia.org/wiki/AKS_primality_test) and I don't understand how can I do the last level in a polynomial time (relatively to the number of ...
user avatar
3 votes
1 answer
77 views

Simple primality test

I am an amateur and have been doing some number theory for fun, so I apologize if my post is absolutely trivial:) I have been playing with primality tests and I thought of the following method: Pick ...
user avatar
1 vote
1 answer
59 views

Odd prime divisor of $ 3x^2+y^2$ (where $x$, $y$ are relatively prime) is again of the same form

Euler proved that any prime divisor $\neq2$ of an integer of the form $ 3x^2+y^2$ is again of the same form. I know there are proofs available using quadratic reciprocity. I was curious to know ...
user avatar
  • 1,036
3 votes
0 answers
45 views

if such counter example to Lehmer's totient problem exists then could we have more counter examples?

Lehmer's totient problem asks whether there is any composite number $n$ such that Euler's totient function $φ(n)$ divides $n − 1$. which it is unsolved problem or we may reformulate that question as : ...
user avatar
4 votes
1 answer
242 views

Primality test for specific class of $N=12k \cdot 5^n+1$

Can you prove or disprove the following claim: Let $P_m(x)=2^{-m}\cdot\left(\left(x-\sqrt{x^2-4}\right)^m+\left(x+\sqrt{x^2-4}\right)^m\right)$ . Let $N= 12k \cdot 5^{n} + 1 $ where $k$ is an odd ...
user avatar
  • 12.5k
1 vote
2 answers
61 views

Fermat's Prime test proof: Why does $\mathbb{Z}_n \setminus \mathbb{Z}_n^*$ consists of Fermat witnesses?

In a lecture I attended, we had a proof that if $n$ is a composite number, but not a Carmichael number, then it holds that the count of Fermat witnesses to the compositeness of $n$ in the set $\{1, \...
user avatar
1 vote
1 answer
120 views

Fermat factorization and primality proving

In Fermat factorization you can factor an integer $n$ if you find a nontrivial pair $(x,y)$ such that $x^2\equiv y^2 \mod n$. At the end of the description in https://mathworld.wolfram.com/...
user avatar
  • 11
0 votes
2 answers
23 views

Shall I take the cailed square root of n to test for a prime?

Algorithm: square root of $n$ test all primes lower than the square root of $n$ if they go evenly up into $n$; if not, $n$ is a prime But do I have to take ceil$(n)$ or floor$(n)$ as the square root?...
user avatar
  • 3
1 vote
2 answers
96 views

Why am I getting the wrong result with the Lucas Lehmer Riesel Test?

The Lucas Lehmer Riesel Test can test if a number of a certain form is prime or composite. Let $N=6143$. I already know this number is prime so the should find $N \vert u_{n-2}$ but the test ends with ...
user avatar
0 votes
0 answers
51 views

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 ...
user avatar
  • 587
4 votes
1 answer
141 views

How to find first term in sequence for Lucas Lehmer Riesel test

I'm trying to do the Lucas Lehmer Riesel primality test. It works on numbers of the form $k \cdot 2^n-1$ with $k<2^n$. The test basically involves calculating a term in a sequence and checking if ...
user avatar

1
2 3 4 5
8