An algorithm for determining whether an input number is prime.

learn more… | top users | synonyms

2
votes
0answers
34 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
106 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
42 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
372 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
172 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$ ...
4
votes
0answers
42 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
16 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
67 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
70 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
38 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 - ...
2
votes
2answers
56 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
24 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 ...
0
votes
0answers
29 views

Estimate, using the Knuth-Trabb-Pardo table, how many values of $r$ would be needed in order to factor…

Use the Knuth-Trabb-Pardo table to estimate, for the original Quadratic Sieve, with all $r \ge \sqrt{n}$, approximately how many values of $r$ would be needed in order to factor a forty-digit ...
5
votes
0answers
86 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
105 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
66 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 ...
6
votes
1answer
88 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
72 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
48 views

Modified Lucas-Lehmer Test

Conjecture (Modified LL) Let $M_p=2^p-1$ such that $p$ is odd prime and $p\equiv 5 \pmod{6}$ . Let $S_i=S_{i-1}^8-8\cdot S_{i-1}^6+20\cdot S_{i-1}^4-16 \cdot S_{i-1}^2+2$ with $S_0=4$ , then $M_p$ ...
0
votes
0answers
57 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
56 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
72 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 ...
0
votes
0answers
60 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 ...
1
vote
1answer
80 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
67 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
44 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
74 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
104 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. ...
0
votes
1answer
273 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
60 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 ...
0
votes
0answers
49 views

On Lucas Lehmer primality Test

http://primes.utm.edu/notes/proofs/LucasLehmer.html is proof of the Lucas Lehmer Test I read. The part I do not understand is why did he consider the sequence $S_n=S_{n+1}^2-2$. I mean why would ...
1
vote
0answers
105 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 ...
9
votes
1answer
146 views

I made a primality test and want to publish it

So I am a high school student, and I am very interested in maths, and I made my own primality test which also expresses all composite numbers with last digits of 1,3,7, or 9 in just 9 simple ...
5
votes
3answers
2k views

Is a cube root of a prime number rational?

The question is: if $P$ is prime is $P^{1/3}$ rational? I have been able to prove that if $P$ is prime then the square root of $P$ isn't rational (by contradiction) how would I go about the cube ...
1
vote
1answer
145 views

How to use Euler's primality test

I am trying to understand how Euler's primality test works. I use this paper as a guide. To summarize Euler's criterion Euler's criterion(in my uderstanding). For an integer $a$, and an odd prime ...
-1
votes
2answers
47 views

Probabilistic Primality Tests

I know most primality tests are probabilistic, but doesn't that pose a major problem to security like RSA that depend on the prime numbers always having no smaller factors? And if you can repeat the ...
20
votes
2answers
414 views

How to either prove or disprove if it is possible to arrange a series of numbers such the sum of any two adjacent number adds up to a prime number

I'm wondering if it's possible to write a theorem to prove or disprove the possibility of arranging a sequence of numbers (1,2,...n) such that the sum of any two numbers adds up to a prime number. An ...
0
votes
1answer
50 views

Finding errors in primality tests?

How do you know when a primality test generates a number that is not prime?
0
votes
1answer
31 views

Miller's test for pseudoprimes explanation for why we check $b^t \equiv 1 \pmod n$ and $b^{2^{j}t} \equiv -1 \pmod n$

I was just wondering if there's an intuitive reason why for the Miller-Rabin primality test, we check whether $b^t \equiv 1 \pmod n$ oror $b^{2^{j}t} \equiv -1 \pmod n$ for some j with $0 \leq j \leq ...
1
vote
0answers
70 views

AKS algorithm: How to do the polynomial modulo part.

I have a question about the last part of the AKS algorithm. I already know how to compute $p \pmod{(x^r-1,n)}$ for a given polynomial $p$ but only once $p$ is in canonical form. In order for AKS to ...
0
votes
0answers
90 views

Is my sieve generalisable?

I was curious about extending Euler's polynomial generator n^2 - n + 41 for n > 41, and looking for the simplest sieves. I examined the gaps between non-primes and found a set of simple sieves of the ...
2
votes
2answers
4k views

Most efficient algorithm for nth prime, deterministic and probabilistic?

What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically? Deterministic Iterate through only odd values, incrementing by $2$. Divide each ...
1
vote
2answers
309 views

Miller-Rabin primality test, begginer reading pseudo code

I was reading Miller-Rabin primality test Wiki and I can't understand something, it says that: Now, let $n$ be prime with $n > 2$. It follows that $n − 1$ is even and we can write it as $2s \cdot ...
1
vote
1answer
70 views

What is the well-known result used to prove primality of $n=2pq+1$ under certain conditions?

On Henri Lifchitz's website, we find: If $n=2pq+1$, $p$ and $q$ primes and $q>2p$, if there is an integer $a$ such $a^{n-1} \equiv 1 \pmod n$ and $\gcd(a^{2p}-1,n)=1$ then $n$ is prime. It is ...
0
votes
0answers
34 views

Primality Test with some condition

Given a prime number p, how can I quickly determine the primality of 10p+a, where a is an integer between 0 and 9? O(1) test is preferred Thanks!
0
votes
2answers
2k views

How do I prove $\gcd(a,b) = \gcd(a+b, b)$ [duplicate]

How do I prove $\gcd(a, b) = \gcd(a+b, b)$. I know that by the euclidean algorithm, I can obtain the following equations $ax_1 + by_1 = \gcd(a, b)\tag{1}$ $(a+b)(x_2) + (b)(y_2) = \gcd(a+b, ...
0
votes
2answers
153 views

What is mod(a,b)?

I was reading the AKS Primality Test. AKS. I could not understand the line : $(x - a)^{n} = (x^{n} - a) \pmod{(n,x^{r}-1)}$ What is $\mod{(a,b)}$ in it ?
1
vote
2answers
123 views

Looking for a more efficient primality testing Algorithm than Miller-Rabin

I am looking for a practical probabilistic primality testing algorithm that is more superior than Miller-Rabin. By "more superior", I mean that the probability of giving the wrong answer is better ...
11
votes
1answer
292 views

Why is factorization of large number hard

Why factoring a number is difficult compared to finding out if it is prime (which can be done in polynomial time) ? I would think they might be of similar difficulty in terms of computational ...
2
votes
2answers
102 views

practical arithmetic in prime factorizations

I am quite adept at doing arithmetic mentally or on paper, but I know little about the relatively sophisticated stuff that software experts use to crunch numbers. My question is whether the following ...