Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [primality-test]

An algorithm for determining whether an input number is prime.

0
votes
2answers
35 views

Should you use Euler's generalization of fermat's little theorem for primality testing?

The title is a bit long, but i think it explains my question well. Let's say we want to test if an integer p is prime With Fermat's Little Theorem this is a simple check if $a^{p-1} \equiv 1 (mod \ ...
4
votes
1answer
149 views
+100

Primality test for numbers of the form $N=k \cdot 3^n-1$

Can you provide proof or counterexample for the claim given below? Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following claim: Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(...
1
vote
0answers
45 views

How could factordb apply the p-1-method on this number?

The following partial factorization http://factordb.com/index.php?id=1100000001285565404 was used by factordb to prove this number ($\ 32^{2133}+4^{2133}+1\ $) to be prime. http://factordb.com/...
-1
votes
1answer
37 views

Is there a prime number $p$ such that : $p\bmod n =1 $ for $n <10$? and if yes , Are there infinity of them?

I want to know set of primes such that satisfies the below question : Question: Is there a prime number $p$ such that : $p\equiv 1\bmod n $ for all $n <10$ ? And if yes, are there infinity of ...
0
votes
0answers
13 views

Help me to understand statistical testing [duplicate]

Why does a statistical test returns the p value? I am looking at the Diebold-Mariano-Test (DM Test): https://github.com/johntwk/Diebold-Mariano-Test Basically, this test gives me a DM statistics, ...
42
votes
4answers
2k views

Does $(n+1)(n-2)x_{n+1}=n(n^2-n-1)x_n-(n-1)^3x_{n-1}$ with $x_2=x_3=1$ define a sequence that is integral at prime indices?

My son gave me the following recurrence formula for $x_n$ ($n\ge2$): $$(n+1)(n-2)x_{n+1}=n(n^2-n-1)x_n-(n-1)^3x_{n-1}\tag{1}$$ $$x_2=x_3=1$$ The task I got from him: The sequence has an ...
2
votes
1answer
151 views

Modular arithmetic rules, of iteration of a polynomial function are?

What are the modular arithmetic properties of iterating a polynomial function ? Iteration if you aren't familiar, is repeated composition of a function with itself. It follows the rules:$$\begin{...
8
votes
1answer
139 views

New property of Mersenne primes?

While playing with Mersenne numbers, I found the following property distinguishing Mersenne prime numbers from Mersenne composite numbers. A Mersenne number, $\text{M}p$, is a number of the form $2^p ...
5
votes
1answer
62 views

Criteria for Leyland Numbers to be Prime

Inspired by a Black Pen Red Pen video on Youtube where he proved that $4^{2019}+2019^4$ is not prime using the Sophie Germain identity, I began exploring when numbers of the form $a^b+b^a;a,b\in\...
3
votes
3answers
53 views

Fermat primality test for $a=n-1$

If we want to know if $n$ is prime, we can do the Fermat primality test: if $a^{n-1}\not\equiv 1 \mod n$, then $n$ is not prime. Now I often find that we choose therefore $a\in\{2,\ldots, n-2\}$. ...
-1
votes
1answer
134 views

Miller-Rabin Primality Test-Witnesses and Liars - Implementing in Python

I have been studying the Miller-Rabin Primality Test, and am interested in implementing a code in Python to count witnesses and liars. In the basic code to determine if a number is probably prime or ...
5
votes
1answer
449 views

Conjectured primality tests for specific classes of $k\cdot b^n \pm 1$

Can you provide proofs or counterexamples for the claims given below? Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following two claims: First claim Let $P_m(x)=2^{-m}\...
6
votes
0answers
196 views

Conjecture: $n>2$ is prime iff $\sum_{k=1}^{n-1}\left(3^k-2\right)^{n-1} \;\equiv\; n \cdot 2^{n-1}-1 \pmod{\frac{3^n-1}{2}}$

This question is closely related to: Conjectured primality test Can you provide a proof or a counterexample for the following claim : Conjecture. Let $n$ be a natural number greater than $2$. Then ...
3
votes
0answers
148 views

Congruence satisfied by primes and only by primes II

This question is closely related to: Congruence satisfied by primes and only by primes Can you provide a proof or a counterexample for the following claim : Let n be a natural number greater than ...
0
votes
0answers
135 views

Primality test using the sum of 2 squares representation of a prime $p^2= a^2+b^2$

We have seen that the sum of two squares (2 sq rep) of an integer $N^2$ can be used to factor $N$. Can the sum of two squares be used to factor large numbers? Here we use the same method to show ...
1
vote
1answer
81 views

Integers of this form that pass the Fermat Primality test are prime, proof?

If an integer, $2p + 1$, where $p$ is a prime number, is a divisor of the Mersenne number $2^p - 1$, then $2p + 1$ is a prime number. My argument is that because divisors of the Mersenne number $2^p -...
2
votes
1answer
62 views

PRIMES in P paper - Lemma 4.7 - why are the polynomials $X^m$ distinct in $F$?

I'm working through the original AKS paper, available here: https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf. There's a single transition which I don't know how to justify, I will ...
0
votes
1answer
152 views

Is really a new Mersenne prime has been discovered for 2018 year? [duplicate]

I have read in this link if it is true that $2^{282589933}-1$ is a new Mersenne prime which was discovered in 07 december 2018 , Really I want to know how this was tested to be a prime number ?
0
votes
1answer
59 views

Bases for deterministic Miller-Rabin primality test

Miller-Rabin primality test can be made deterministic when the number $n$ is small, for example "if $n < 2047$, it is enough to test [with base] $a = 2$". How are those bases found? By brute force?...
2
votes
1answer
110 views

AKS - proving that $\frac{n}{p}$ is introspective

I have a problem with showing that $\frac{n}{p}$ is introspective. Recall that we are in state where a composite integer $n$ fools the AKS test and $p\mid n$ a prime number. First of all, recall ...
1
vote
0answers
63 views

Questions about a proof of the error-bound of the Miller-Rabin-Test

I am trying to understand a proof (from the German book "Einführung in die Kryptografie" by Johannes Buchmann) that there are at most $(n-1)/4$ non-wittnesses against the primality of $n$ in the ...
-1
votes
1answer
42 views

Name of the theorem used for testing the primality of a number

$n$ is prime $\iff$ $a^{n-1} \equiv 1 \mod n \hspace{10mm} \forall 1 \le a \le n-1$ What is the name of this theorem in literature?
0
votes
0answers
31 views

primality test speed

Noticed using a lattice with line x+y=n for n prime, every grid point on the line is co-prime. For example: Lattice with x+y=n To test, I wrote a C program to specify a number (e.g., 104729) then ...
3
votes
1answer
229 views

Probable prime tests for generalized repunit numbers

Can you provide proofs or counterexamples for the following two claims: First claim Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $M_p(a)= \frac{a^p-1}{a-1} $ where $a$ ...
1
vote
1answer
349 views

Compositeness tests for numbers of the form $k \cdot b^n \pm c$

Can you provide proofs or counterexamples for the following claims? Claim 1 Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $M= k \cdot b^{n}-c $ where $k,b,n,c$ are ...
1
vote
1answer
226 views

Compositeness tests for generalized repunit numbers

Can you provide proofs or counterexamples for the following two claims: First claim Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $M_p(a)= \frac{a^p-1}{a-1} $ where $a$ ...
1
vote
0answers
51 views

Efficient Reduction of $q\mod k2^n+1$?

In the Lucas Lehmer Primality Test, the following identity is used: $q\equiv (q\mod 2^n)+\lfloor\frac{q}{2^n}\rfloor(\mod 2^n-1)$. This allows the modulus operation to converge with only addition ...
4
votes
1answer
289 views

Primality criteria for specific classes of generalized Fermat numbers

Can you provide proofs or counterexamples for the following two claims: First claim Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $ F_n(b)= b^{2^n}+1 $ where $b$ is an even ...
1
vote
2answers
352 views

Hermite polynomials and primality testing

Can you provide a proof or a counterexample for the claim given below ? Inspired by Agrawal's conjecture in this paper I have formulated the following claim : Let $n$ be a natural number greater ...
1
vote
1answer
48 views

Time complexity of finding the largest Goldbach partition

Suppose we are given a large even integer $N$, and we want to determine primes $p$ and $q$ such that $N = p + q$, subject to the conditions that $p \geqslant q$ and $p - q$ is as small as possible. (...
3
votes
1answer
324 views

Jacobi polynomials and primality testing

Can you provide a proof or a counterexample for the claim given below ? Inspired by Agrawal's conjecture in this paper I have formulated the following claim : Let $n$ be an odd natural number ...
2
votes
1answer
47 views

Isn't the estimate for the smallest counterexample of the BPSW-test far too optimistic?

Here : http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html it is described how the BPSW-test was verified. If I understand the description right, the test was circular because intermediate ...
0
votes
0answers
30 views

Is this a proper superset of Carmichael numbers?

While looking into the Lucas primality test I noticed an interesting thing. Using the following test* I discovered a sequence of numbers which, for lack of a better ...
1
vote
0answers
55 views

Concern about the Lucas primality test

The Lucas primality test states that a number N is prime iff for any given base B we find that: [a] $\ B^{N-1} \equiv 1 \mod N$ ...and... [b] For all prime factors F of N-1 the congruence $B^{(N-1)...
-2
votes
1answer
116 views

How to verify large Mersenne Primes [duplicate]

As of December 2017, the largest known prime number was the Mersenne prime $2^{77232917} – 1$. For such a large Mersenne prime, what are the techniques available for one to verify that it is in fact ...
4
votes
1answer
90 views

What does 3-PRP means exactly ? (in pfgw primality test)

When i do primality test for large integers with the software pfgw, it returns either composite or 3-PRP. 1: What does 3-PRP means exactly? 2: What is the error ratio? 3: When the test return ...
0
votes
0answers
30 views

Does c#k + i actually generate all primes above c# (plus some composites)?

The Wikipedia page for "Primality test", linked below [1], states that "all primes are of the form c#k + i for i < c# where c and k are integers, c# represents c primorial, and i represents the ...
0
votes
1answer
34 views

Primality test calulating on paper. Specific case

How to make primality test on paper without any calculator for high numbers like $$ (32^{200}) - 1 $$ $$ (400^{555}) - 1 $$ What specific test is useful in such cases: $$(a^b) - 1$$ where a ...
2
votes
1answer
126 views

Lucas Lehmer Test

I have tried to write a function that test if it is prime using Lucas Lehmer Test ...
0
votes
1answer
46 views

Distribution of non-negative $y$ in OEIS A205535

While implementing Paul Underwood's algorithm[1] for a small machine with only 16 bit native wordsize I found that $y$ ($y$ in OEIS, $a$ in the paper) cannot exceed 177 without using big integers and ...
2
votes
1answer
138 views

Chinese Remainder Theorem, Miller-Rabin Primality test, and more…

Good day, I was going over the proof of the Miller-Rabin Primality Test and have a few questions regarding it. THE BOOK IS COMPLEXITY AND CRYPTOGRAPHY: AN INTRODUCTION Where $B_t = \{a\in\Bbb Z_n^...
4
votes
2answers
271 views

Fermat primality test

Is the following a correct statement for the Fermat primality test? For all $b$ if $n$ is prime and $(b,n)=1$ then $b^{n-1} \equiv 1 \bmod{n}$. The contrapositive is if $b^{n-1}...
1
vote
1answer
161 views

What's the difference between a Fermat pseudoprime and a Carmichael number?

I've read a lot of definitions in different places on the Internet and I'm confused since all of them express the same thing, but using seemingly different explanations. Can somebody please point out ...
25
votes
11answers
4k views

A quick way, say in a minute, to deduce whether $1037$ is a prime number

So with $1037 = 17 \cdot 61$, is there a fast method to deduce that it's not a prime number? Say $1037 = 10^3+6^2+1$. Does $a^3 + b^2 + 1$ factorize in some way? As part of their interviews, a ...
0
votes
0answers
90 views

What's the fastest free software to test primality of a Mersenne prime?

Mersenne primes are primes of the form $2^n-1$ for positive integer $n$. Currently, the most widely known (and employed) software for testing large Mersenne prime candidates is Prime95, which is also ...
4
votes
0answers
418 views

Initial values of Inkeri's primality test for Fermat numbers

Can you provide a proof or a counterexample to the claim given below ? First , we shall give a definition of the Inkeri's primality test for Fermat numbers : Fermat's number $F_m=2^{2^m}+1$ ($m \...
0
votes
1answer
34 views

Modular equivalence in Agrawal's conjecture

In Agrawal's conjecture: If $r$ is a prime number that does not divide $n$ and if $(X-1)^n ≡ X^n-1 \pmod{X^r-1, n}$, then either $n$ is prime or $n^2 ≡ 1\pmod r$. How to understand $\pmod{X^r-1, n}...
0
votes
2answers
76 views

How many bases do you need to check to know that a number is a Carmichael number?

Suppose that $N$ is a Carmichael number, but we don't know that yet and we perform the Fermat test on it: that is for numbers $a$ such that $gcd(a,N) = 1$ we check if $a^{N-1} \equiv 1 \pmod N$. ...
0
votes
0answers
55 views

Fermat Test for compositeness, how many bases needed?

The Fermat Test base $a$ checks for a number $n$ whether or not $(a,n) = 1$ and $a^{n-1} \equiv 1 \pmod n$. If for some base $a$, $n$ does not pass this test then we know $n$ is composite. But, ...
1
vote
1answer
118 views

Lucas Sequence and primality tests. is this test deterministic?

consider lucas parameters $(P, Q)$ and $D = P^2 - 4Q$. Let $n>0$,$\big(\frac{D}{n}\big)= - 1$ then $U_{n + 1}\equiv{0 \pmod{n}}$ and $n$ is a Lucas probable prime. This test base only on the ...