Questions tagged [primality-test]

An algorithm for determining whether an input number is prime.

Filter by
Sorted by
Tagged with
0
votes
0answers
37 views

Primality test via Euler’s totient function [duplicate]

How can I prove the following theorem using Wilson’s theorem: Let n ≥ 2 be an integer. Show that n is prime if and only if $n|(φ(n)!+1$. The first direction is easy, but the other way I do not have an ...
3
votes
1answer
62 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 ...
24
votes
3answers
644 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 ...
0
votes
1answer
65 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?
3
votes
2answers
213 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 ...
5
votes
1answer
115 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-...
1
vote
1answer
61 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 ...
3
votes
1answer
58 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 ...
1
vote
1answer
41 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 ...
2
votes
0answers
23 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 : ...
4
votes
1answer
234 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 ...
1
vote
2answers
37 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, \...
1
vote
1answer
28 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/...
0
votes
2answers
18 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?...
1
vote
2answers
71 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 ...
0
votes
0answers
28 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 ...
5
votes
1answer
117 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 ...
0
votes
0answers
41 views

Show that if $p$ is a prime divisor of $n$ and we set $m = n/p$, then $n$ is a pseudoprime to the base $b$ if $b^{m−1} \equiv 1 \bmod p$

Show that if $p$ is a prime divisor of $n$ and we set $m = n/ p$, then $n$ is a pseudoprime to the base $b$ if $b^{m−1} \equiv 1 \bmod p$. (Hint: write $n = m(p−1 + 1)$) def: pseudoprime $n$ for ...
2
votes
2answers
45 views

Is it true that $[\pi^n] $ is a prime number for only finitely many integers $n$?

let $[\pi^n] $ be the integer part of $(\pi^n)$, I did mathematica code up to $10^4$ to test primality of $[\pi^n] $ , I have got it could be prime for $n=1,3,4,12$ , Now are there other ? and Is ...
1
vote
0answers
46 views

Extra strong Lucas pseudoprimes and Jacobi symbol

In order to decide out whether a number $n$ is extra strong Lucas pseudoprime, one usually chooses Lucas sequence where Jacobi symbol $(D/n) = -1$. Such a $D$ can be found by Method C by Robert ...
0
votes
0answers
61 views

Upper bound on r in the aks paper

I have been recently reading the paper "PRIMES is in P", but unfortunately a lot of the steps were skipped, which led to confusion. My main problem is with the upper bound on r which was not explained ...
1
vote
0answers
52 views

Prime counting formula considered by S.Wigert

Consider the following integral: $$π(n)=\frac{1}{(2πi)}\oint_{C_n}\frac{f'(x)}{f(x)}dx$$ Where , $$f(x)=\sin^2(πx)+\sin^2(π(1+\Gamma(x))/x)$$ The integral extends over a closed contour $C_n$ ...
2
votes
1answer
62 views

In Lemma 4.7 of AKS, why do distinct polynomials map to distinct elements modulo h(x)?

I am reading Primes is in P by Agrawal, Kayal and Saxena, and I can't understand part of the proof of Lemma 4.7 (already the subject of two questions here: PRIMES in P paper - Lemma 4.7 - why are the ...
6
votes
1answer
505 views

Primality test involving quartic fields and polynomials

Let $n$ be an odd number, $D=a^2+4$ and $(D | n)=-1$ where $(D | n)$ is the Jacobi symbol. Then $n$ is prime if and only if $(x^2 + ax)^n = x^3 - x^2 + (D-2)x - D \pmod {{x^4 + Dx^2 + D},n}$ or $...
2
votes
1answer
56 views

is there any deterministic versions of fermat test except this one?

fermat test says : if $a^{N-1} \equiv 1 \pmod N$, then N is probably prime number, but according to pocklington primality test if: $3^{N-1} \equiv 1 \pmod N $, then N is proven prime, where $N=2p+1$...
0
votes
1answer
52 views

Can Cipolla algorithm be used as a primality test?

https://en.wikipedia.org/wiki/Cipolla%27s_algorithm describes the steps to compute a modular square root, assuming a prime modulus. The converse of this algorithm could be: considering a quadratic ...
0
votes
0answers
53 views

How does “Miller–Rabin” primality test computed for big numbers?

According to Primality test Wikipedia page, Miller–Rabin primality test is described as; The Miller–Rabin primality test works as follows: Given an integer n, choose some positive integer a < ...
1
vote
2answers
70 views

how to run fermat test on large numbers

fermat test is a primality test, says that: if $a^{N-1} \equiv 1\mod N$, then N in is probably prime, but I have searched for any program that allows me to run this test on large numbers (...
2
votes
1answer
103 views

Proof of Test of primality from E.Dickson's book “History of theory of numbers vol.1”

E.Dickson mentioned the following result by E.Zondadari in his book "History of theory of numbers vol.1"(Chap XVIII): Consider the following 'function': $$ \frac{\sin²(πx)}{(πx)²(1-x²)^2} \prod_{n=2}...
0
votes
2answers
66 views

How to check the primality of $2^n + 1$?

With Mersenne Numbers, if $M = 2^n - 1$ is prime, $n$ is prime. Is there a trick (may be similar to that of Mersenne) to check the primality of $2^n + 1$?
1
vote
1answer
40 views

How one can reformulate the sentence: $T_{n}(x)/x$ is irreducible over the integers

The motivation to this question can be found in: Chebyshev Polynomials and Primality Testing My question is: How one can reformulate the sentence: $T_{n}(x)/x$ is irreducible over the integers ...
1
vote
1answer
43 views

Why do we choose random bases for the Fermat primality test?

As in title, why do people usually choose random bases for the Fermat primality test as opposed to just using bases $2, 3, 4, ...$ in succession? Say we want to know if $N$ is prime/Carmichael or ...
-2
votes
1answer
155 views

About how much time would it take to test the primality of a billion digit Mersenne number with a typical processor?

I'm wondering how long it might take to run a Lucas Lehmer primality test on a one billion digit Mersenne prime using a 3.0 ghz processor.
2
votes
1answer
79 views

Proof of Lehmann's primality test

I'm struggling to understand the details in the proof of Lehmann's primality test (Algorithm2 in the link). Explanations, and a more incremental walkthrough in general would be very appreciated. ...
1
vote
0answers
84 views

Primality testing when $n\equiv3\pmod{4}$ and $gcd(totient(n), (n-1)/2) = 1$

Euler proved that if $n$ is prime, $a^{\frac{n-1}{2}}\equiv \genfrac{(}{)}{}{}{a}{n}\pmod{n}$, which for primes is $1$ if $a$ is a quadratic residue mod $n$, $-1$ if $a$ is a non-quadratic residue mod ...
2
votes
1answer
37 views

Expected runtime analysis for sums of four squares (Rabin and Shallit)

I've been reading a paper of Rabin and Shallit ("Randomized Algorithms in Number Theory"), which gives a brief sketch of an ERH-conditional algorithm to compute a representation of a positive integer $...
0
votes
3answers
115 views

Heuristic primality test with an offer $620 for a counterexample

There is a heuristic primality test which combine the Fermat test and the Fibonacci test (with an offer $620 for a counterexample): $(1)\quad 2^{p−1} \equiv 1 \pmod p$ $(2)\quad f_{p+1} \equiv 0 \...
7
votes
1answer
397 views

Probability of a composite number passing the test

Inspired by Theorem 5 in this paper I have created the following algorithm: Let us define polynomials $P_n^{(b)}(x)$ as follows : $$P_n^{(b)}(x)=\left(\frac{1}{2}\right)\cdot\left(\left(x-\sqrt{x^2+b}\...
0
votes
0answers
25 views

Binomial coefficients and primality

This question is motivated by this another one. It is known that for every positive integer $n$, $$n\text{ is prime}\iff n\mid \binom nk\;\forall 1\le k \le n-1$$ My question if the number of ...
1
vote
1answer
34 views

Miller's Test Base a [closed]

Definition - Miller's test base a- For the following example, please advise on why Miller's test passes according to the output. Thank you!
5
votes
0answers
258 views

Primality test for numbers of the form $N=2 \cdot 6^n+1$

Can someone provide counterexample, if one exists, to the claim given below? Inspired by Lucas-Lehmer primality test I have formulated the following claim: Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^...
2
votes
0answers
72 views

Deterministic Miller-Rabin Primality Test

Looking into the Miller-Rabin Primality Test. At some point it is stated that if $b \approx \log_2(n) \ge 32$ then the probability of a number $n$ being prime after passing $k$ tests is: $4^{-k}$. ...
1
vote
1answer
53 views

Getting wrong result with Lucas probable prime test on specific composite

I'm trying to do the extra strong Lucas probable prime test on $15$ but keep getting the wrong result. $15=3 \cdot 5$ so it's composite, but the Lucas test says it's prime. The parameters are $Q=1, ...
8
votes
0answers
413 views

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

Can someone provide counterexample, if one exists, to the claim given below? Inspired by Lucas-Lehmer primality test I have formulated the following claim: Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^...
4
votes
2answers
142 views

Why am I getting the wrong result when applying the extra strong Lucas pseudoprime test?

I'm trying to do the Lucas extra strong pseudoprime test but get the wrong result. For example $13$ is prime but the test gives composite. Here is what I tried: $n=13$ then $n+1=14=7 \cdot 2^1$ gives ...
1
vote
0answers
90 views

How to prove that $n$ divides $\binom{n}{k}$ if $n$ is prime? [duplicate]

I want to prove that n divides $\binom{n}{k}$ and so I expanded the term to $\frac{n(n-1)..(n-k+1)}{k!}$. Clearly $n$ divides the numerator and also $n$ is relatively prime to all of the terms in the ...
5
votes
2answers
139 views

Probability that a number passing the Fermat test is prime

I'm studying a computer science textbook that has a section on the Fermat test as an example of a probabilistic method. Given a number $n$, the Fermat test is stated as pick a random number $a < ...
1
vote
1answer
96 views

Primality test $n \mid F_{n+1}+F_{n-1}-1$

I have found information and references about the Fibonacci primality test: $$n \mid F_{n-\left(\frac{5}{n}\right)}$$ but not about the following primality test: $$n \mid F_{n+1}+F_{n-1}-1$$ Which ...
1
vote
1answer
81 views

What is the rough upper bound to find nth prime? Also give the maximum error.

At first please don't mark this as duplicate. I couldn't get a satisfactory answer in previous questions. I want a simple upper bound calculating formula for n-th prime which should not have ...
1
vote
0answers
47 views

time complexity of some specific system of $(n-3)/2$ linear equations with $(n-3)/2$ unknowns.

let take n a odd integer greater than 3 if I have to solve this system of $(n-3)/2$ linear equations with $(n-3)/2$ unknowns to find some propriety about the number n, here is formula for every ...

1
2 3 4 5
7