An algorithm for determining whether an input number is prime.

learn more… | top users | synonyms

-6
votes
0answers
66 views

Lepore primality test and factorization . What is the complexity?

I have found an algorithm which tests if a number NR is primes . What is the complexity? I show only NR = X * Y, where NR = 6G + 1, X = 6a + 1, Y = 6b + 1, G, a and b natural numbers. X and Y are ...
3
votes
1answer
216 views

Conjectured primality test for specific class of $N=k\cdot 6^n-1$

How to prove that this conjecture is true ? Definition : $\text{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)~ , \text{where}~ m ~\text{and}~ x ...
1
vote
3answers
50 views

Fermat primality test $\gcd$ condition and carmichael numbers

Consider the following quote (I read similar thing in a couple of sources but this one illustrates the issue I'm having): By Fermat's Theorem if $n$ is prime, then for any $a$ we have $a^{n-1} = 1 ...
1
vote
2answers
128 views

Primality of $2^{255}-19$

I need a test for primality that I apply to $2^{255}-19$ (which is claimed to be prime) and certify to be correct with the ACL2 theorem prover. This means that I must be able to code the test in ...
0
votes
0answers
17 views

$S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$, $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ iwth composite and prime numbers

I have two sets with $n>2$ natural number: $S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$ $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ Can anyone explain me if there are prime ...
-1
votes
1answer
25 views

Rabin-Miller compositeness

Find a witness Rabin-Miller of compositeness of $n=25$ Can anyone explain and show me a way on how to solve this question?and generally how to find witness Rabin-Miller
6
votes
0answers
135 views

Is there a quicker way to generate integers which are hard to factor than multiplying two large primes?

An easy way to generate an integer which is hard to factor is to find two large primes and multiply them. As a bonus, you know the factors. I'm interested in whether it's possible to find integers ...
0
votes
1answer
27 views

Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n

Given the number $n=35$.Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n I found this problem on internet and i am trying to find a solution ...
4
votes
1answer
65 views

Why are there not primality tests based on comparing the candidate $n$ with values of some $k \in [0,n]?$

I am learning basic number theory and as far as I could read, basically all the primality tests (or proven primality theorems) that are able to decide if a given $n$ is prime (or a special ...
5
votes
1answer
77 views

Non existence of absolute euler pseudoprimes

A natural number $n$ is called an Euler pseudoprime(sometimes Euler-Jacobi pseudoprime) wrt to $a$ iff $$a^{(\frac{n-1}2)} \equiv \Big(\frac an\Big) \pmod n$$ where $\Big(\frac an\Big)$ is the ...
3
votes
0answers
60 views

Is there an advantage in using continued fractions for Catalan or Fibonacci-Lucas primality tests?

I am studying the basic theory about continued fractions and also reviewed here at MSE former questions to learn more. While reviewing the questions and answers, I found references to the Fibonacci ...
0
votes
0answers
31 views

Primality test similar to Pocklington

I'm working on a series of number theory proofs and I'm stumped on this one. The idea is to extend each result for the subsequent proof. I just succeeded in proving the following: Suppose $n > 1$. ...
1
vote
1answer
45 views

Fermat witness to compositeness of $n=21$

I have to find a Fermat witness to compositeness of $n=21$. I found this The Fermat compositeness test is a primality test based on the observation that by Fermat’s little theorem if $b^{n-1} ...
0
votes
0answers
31 views

Motivation for $r$ in AKS Primality Test

I've been reading up on the AKS primality test, and I understand the big ideas and proofs as they are pretty elementary number theory. I am confused about how to value of $r$ is selected. In the ...
7
votes
3answers
229 views

Conjectured Primality Test for $N=8\cdot 3^n-1$

Definition 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)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=8\cdot 3^n-1$ ...
2
votes
0answers
176 views

Primality Test for $N=2\cdot 3^n-1$

Definition 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)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=2\cdot 3^n-1$ such ...
12
votes
3answers
374 views

Mental Primality Testing

At a trivia night, the following question was posed: "What is the smallest 5 digit prime?" Teams (of 4) were given about a minute to write down their answer to the question. Obviously, the answer is ...
2
votes
4answers
55 views

Certificate of primality based on the order of a primitive root

Reading my textbook, it tells me that to prove $n$ is prime, all that is necessary is to find one of its primitive roots and verify that the order of one of these primitive roots is $n-1$. Now, why ...
0
votes
1answer
78 views

Is there a primality test based on the sum of squares of the first $n$ natural numbers $\sum_{x = 1}^{n} x^2$?

The Fibonacci and Catalan primality tests are based on the calculation of the congruences of those numbers versus the possible prime $n$ (the rules are different depending on the primality test), and ...
0
votes
0answers
42 views

How to simplify finite product?

I've got such equation: $$f(x) = (\sin(2 π x/2 - π / 2) + 1)(\sin(2 π x/3 - π / 2) + 1) \cdots (\sin(2 π x/(x-1) - π / 2) + 1)$$ I want to know if the function $f(x) = 0$ or not because this states ...
4
votes
4answers
147 views

Can we predict when a polynomial can take more than one perfect square value?

We consider only polynomial with integer coefficients. We know how to determine the first perfect square value but we don't know how to determine subsequent perfect square values except by testing ...
2
votes
0answers
47 views

Determine whether permutation of the digits of a number is prime

Given a number $m$ in decimal representation. I want to find a permutation of the digits of $m$, so it is prime. (Or output that there exists none) Do i have in the worst case check every possible ...
3
votes
1answer
140 views

New primality test, now what (publishing and proof)? [closed]

Over my research, I found a new relatively simple way to calculate whenever a number is prime or not. What's exciting is that it runs in $O(\log^2 n)$ running time (where $n$ is the number of digits ...
2
votes
1answer
54 views

How many Fermat tests are needed to verify a Carmichael number

If $n$ is a Carmichael number, then for all values $a$ such that $0<a<n$ (and $a \perp n$): $a^{n-1} \equiv 1 \mod n$ However, is it not necessary to check check all $a$ values because for a ...
6
votes
0answers
500 views

2015-related question: why are Lucas-Carmichael numbers named after Lucas?

Summary 2015 is a so called Lucas-Carmichael number. I believe (for reasons that I will explain below) that the 'Carmichael' in the name is a reference to ordinary Carmichael numbers and not to the ...
4
votes
1answer
191 views

Determining the starting value for primality test

This question is about Lucasian primality test for numbers of the form $N=3\cdot 2^n-1$ . There is a following statement in Wikipedia article : Lucas-Lehmer-Riesel test : "If $k = 3$ : if $n = 0$ ...
6
votes
0answers
61 views

How probable is that a randomly typed 47 digit odd integer is a prime?

So, I have been playing around with prime numbers, I have installed gmp and gmpy2 gmpy2 has ...
0
votes
2answers
23 views

Polynomial modulo n

http://en.wikipedia.org/wiki/AKS_primality_test How can I interpret what the "mod n" means? I have watched the Numberphile video on the AKS primality test, and based on that, I am assuming that ...
3
votes
2answers
124 views

Do we still need probabilistic primality testing methods for practical applications?

Probabilistic primality testing methods like Rabin Miller and Solovay Strassen, were created at the time when mathematicians were not sure whether there is a deterministic polynomial algorithm. After ...
0
votes
2answers
76 views

Make a prime number from specified number, by concatenating some more digits on its right?

I am given a number, I don't know whether it's prime or not. The algo says, For eg - Step 1 - Convert char to ints. (Hello - 72101108108111) Ascii values Step 2 - Make a large number. Convert char ...
3
votes
1answer
61 views

Finding a lower bound to the probability that a number will be shown to be composite?

Given the following method to decide whether a number $m$ is prime or not: Choose a random number $1<a<m-1$, and check whether $a^{m-1} = 1 \mod m$. If its equal, return true, otherwise - ...
4
votes
2answers
108 views

Bases required for prime-testing with Miller-Rabin up to $2^{63}-1$

This webpage (as well as Wikipedia) explains how one can use the Miller-Rabin test to determine if a number in a particular range is prime. The size of the range determines the number of required ...
0
votes
1answer
38 views

Primality Test for Safe Primes

Is this proof acceptable ? Theorem Let $N$ be of the form $N=2p +1$ with $p$ prime , then $N$ is prime iff $N \mid 2^{2p}-1$ Proof In one direction , if $2p+1$ is a prime then by Fermat ...
8
votes
0answers
125 views

Primality of $n! +1$

I came across with a problem where I was required to examine primality of $n! +1$ (17! + 1 was the actual number). Although Wilson's Theorem could be manipulated for determining primality of $n! + ...
1
vote
1answer
118 views

Primality Criterion for Specific Class of Proth Numbers

Is this proof acceptable ? Theorem : Let $N = k\cdot 2^n+1$ with $n>1$ , $k<2^n$ , $3 \mid k $ , and $\begin{cases} k \equiv 3 \pmod {30} , & \text{with }n \equiv 1,2 \pmod 4 \\ k ...
1
vote
2answers
75 views

A Generalization of Carmichael Numbers

Obviously, from Fermat's Little Theorem, the condition of $p$ being prime is equivalent to there being some number $a$ of multiplicative order $p-1$ mod $p$. Moreover, this is equivalent to saying ...
7
votes
1answer
94 views

PRIMES is in P, page 4: Why is $(X+a)^{\frac{n}{p}} \equiv X^{\frac{n}{p}}+a$ implied?

PRIMES is in P, page 4, equasion (5) Edit: I should probably add that $p$ is a prime factor of some $n$. $a$ is any number from 1 to some irrelevant limit. $r$ also shouldn't matter because as far as ...
0
votes
4answers
79 views

Is it true that $2^{p}-1$ is a prime number?

Let $p$ be an odd prime such that $$p \equiv 1 \pmod{4}$$ and $p$ and $p-2$ form a twin prime pair. My question: Is it true that $2^{p}-1$ is a prime number?
0
votes
0answers
68 views

Proof for divisibility on a prime test: (p-1)!/(n!(p-n)!)

$p$ is a prime only if $\forall n \in\{ 2, 3, .. ,\lfloor \frac{p}{2}-1\rfloor, \lfloor \frac{p}{2}\rfloor \}$: $\dfrac{(p-1)!}{n!(p-n)!}\in \mathbb N$ The remainders and n's that don't divide when ...
3
votes
0answers
70 views

Are there any primes that are never a factor of a Carmichael number?

Is there a prime number $p$ that $p > 2$, and in which $p$ is a never a factor of any Carmichael number $C_n$: (p ∤ $C_n$) Extended this to all numbers $m$, instead of just $p$, will prove the ...
3
votes
1answer
74 views

If $p$ is prime, prove that $\exists k\in\lbrace 5,-7,9,-11,..\rbrace$ in $(\mathbb{Z}/p\mathbb{Z})^*$ so that the Legendre symbol $(\frac{k}{p})=-1$

The BSPW primality test, when given $p$ as input, iterates over $k \in \lbrace 5,-7,9,-11,...\rbrace$ as long as the Legendre symbol $(\frac{k}{p})=1$. If $(\frac{k}{p})=0$, it returns "composite". So ...
1
vote
0answers
87 views

Fast check of safe primes or Sophie Germain primes

If $p=2q +1$ with $p,q$ prime then $p$ is called safe prime and $q$ is a Sophie Germain prime. I want a faster algorithm for a safe prime test than doing two primality checks for $p$ and $q$. In ...
2
votes
1answer
210 views

What's the best software for primality tests of huge numbers? (check if an integer is prime or not)

I just read an article about huge prime numbers (some with more than 10millions digits!) that are discovered using software that check if an integer is prime or not (primality test sofwares). What is ...
5
votes
2answers
84 views

Analogue of Fermat's primality test for polynomials and irreducibility

We've got Fermat's primality test to test if a number is probable prime. Is there an analogous test for polynomials in $\mathbb{F}_{p^n}[X]$ and irreducibility?
1
vote
1answer
46 views

How many $\overline{a}\in\left(\mathbb{Z}/91\mathbb{Z}\right)^\times$ pass the Fermat and Miller-Rabin primability tests?

Let $$\text{F}_{91}:=\left\{\overline{a}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times:91\text { passes the Fermat primality test to base }a\right\}$$ and ...
0
votes
1answer
81 views

Numbers that pass every known primality test

Was having fun reminding myself of the inner workings of a few primality tests today and wondered if there exists a composite number that (perhaps provably) passes all known tests? (Ignoring tests ...
3
votes
2answers
178 views

Check primality of large prime by Miller-Rabin

I need to check whether $7150309735704750359$ is prime. Naive methods, Sieve algorithm and AKS didn't work. So I tried Miller-Rabin. Now it says here that checking for some small set of $a$ is enough. ...
3
votes
1answer
696 views

What is a non Trivial Square Root?

I need to understand the concept behind a non trivial square root. Also how to answer these two questions and how to get to the answer? Give a non-trivial square root of 30 Give a non-trivial ...
1
vote
1answer
104 views

Meaning of double vertical bars in context: “let $q$ be a prime divisor of $n$ with $q^s|| n$.”

I've been doing some reading about the AKS primality test. I specifically have been reading this. On page 19, I don't understand the notation involving the double vertical bars: Let $q$ be a prime ...
2
votes
0answers
121 views

Will anyone check my primality test?

The proof is very straightforward and simple. We all know that all prime numbers have a last digit of 1, 3, 7 or 9, and I found that any composite number with a last digit of 1,3,7 or 9 is a product ...