An algorithm for determining whether an input number is prime.

learn more… | top users | synonyms

0
votes
0answers
39 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
35 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
43 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
42 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
68 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
46 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
111 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
37 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
42 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
84 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 ...
8
votes
1answer
125 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
794 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
95 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 ...
0
votes
0answers
45 views

Primality of a binary number

I'm interested in finding out if there is a way to detect if a given binary number is prime. I do not which to convert it to base 10 then use some primality test. Does anyone know it there's a pattern ...
0
votes
2answers
33 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 ...
19
votes
2answers
348 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 ...
2
votes
0answers
72 views

General Primality Conditions in the UFD $\mathbf{Q}(\sqrt{-d})$

Suppose $\mathcal{O}_{\mathbf{Q}\left(\sqrt{-d}\right)}$ is a UFD, so $d=1,2,3,7,11,19,43,67,163$. Are there general criteria determining whether an element in the integers of $\mathbf{Q}(\sqrt{-d})$ ...
0
votes
0answers
44 views

How to find gcd sum for some combination of numbers?

The problem is , Given an n-dimensional hyperrectangle length of each dimension is given. Now the value of each cell is the gcd of its co-ordinates. Now How do we find the sum of all cells ? I have ...
0
votes
1answer
44 views

Finding errors in primality tests?

How do you know when a primality test generates a number that is not prime?
0
votes
1answer
28 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
48 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
82 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 ...
1
vote
2answers
1k 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
235 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
66 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
32 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
1k 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
147 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
1answer
89 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 ...
10
votes
1answer
222 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
93 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 ...
2
votes
1answer
128 views

Probability of 2 as a liar in the SPRP test - Miller-Rabin

I've used number-theoretic results for p(k, t) (e.g., DLP) to create a utility, mrtab, that generates the Miller-Rabin iterations (as a k-bit threshold table) required to satisfy a given ...
2
votes
2answers
291 views

Primality test square root of n

I was reading about primality test and at the wikipedia page it said that we just have to test the divisors of $n$ from $2$ to $\sqrt n$, but look at this number: $$7551935939 = 35099 \cdot 215161$$ ...
0
votes
1answer
79 views

Prime divisibility in a prime square bandtwidth

I am seeking your support for proving (or fail) formally the following homework: Let $p_j\in\Bbb P$ a prime, then any $q\in\Bbb N$ within the interval $p_j<q<p_j^2$ is prime, if and only if ...
2
votes
0answers
158 views

Making fermat's little theorem for composite numbers the ultimate test.

It is a programming question but mathematics has a major role to play in it. I have to find the largest prime less than a number $n$. Note that $n\leq10^{18}$. I can go for Fermat's Little Theorem ...
2
votes
0answers
35 views

Does Miller Rabin algorithm becomes faster if $a$ is choosen from the set $\mathbb{Z}_n^*-(\mathbb{Z}_n-\{0\})$ rather than randomly

In Miller-Rabin Primality Test for $n$ we first represent $n-1$ as $u\times2^k$ and then random choose some $a$ from the set $\{2 ,3 \cdots n-2\}$ and then we compute $b_0(=a^u),b_1(=b_0^2)\cdots ...
2
votes
1answer
112 views

Computing the running time of the Fermat primality test

I have a question concerning the Fermat primality test and its running time. According to Wikipedia: "Using fast algorithms for modular exponentiation, the running time of this algorithm is $$O(k ...
2
votes
2answers
204 views

Miller-Rabin Primality Test

I am trying to work out the potential primality of 341 using the Miller-Rabin algorithm. Below is as far as I get, I'm not really sure where to go from there. I believe I am supposed to use modular ...
-1
votes
1answer
88 views

How to test a real number a prime number [closed]

if $p^{1/n}$ where $p$ is a prime number and $n$ is an integer, will it be a prime number? should $n$ be prime? for example $\sqrt3^{1/3}$, $\sqrt3^{1/10}$ what is the algorithm to test a real ...
0
votes
0answers
116 views

AKS algorithm pseudoprimes

The AKS algorithm is based on the following fully deterministic primality check: Let input $n>1$ and $a \in \mathbb{Z}$ such that $(a,n)=1$. Then $n$ is prime if and only if $$\tag{1}(x+a)^n ...
1
vote
1answer
64 views

probability of a number not having factors below n?

I want to know the probability that a number is not divisible by any prime smaller than or equal to n. ie, I find a big number, I trial division it up to 300000 and don't find any factors. I want to ...
5
votes
4answers
238 views

Constructing arbitrary sized Miller-Rabin Primality Test Case Numbers

The Miller–Rabin (or Rabin-Miller) primality test is an algorithm that determines whether a given number is prime. Is it possible to construct a number that will pass an arbitrary number of ...
3
votes
1answer
156 views

What is this shortcut to determine primality?

I'm watching this, he says that David Slowinski discovered the biggest prime in 1984: $2^{132,049}$-1 and that it took 1 week on a Cray supercomputer: using some shortcut and that the absence of this ...
5
votes
0answers
154 views

Carmichael number factoring

The task I'm faced with is to implement a poly-time algorithm that finds a nontrivial factor of a Carmichael number. Many resources on the web state that this is easy, however without further ...
1
vote
1answer
122 views

Lucas' primality test == finding a primitive root?

I'm looking at some definitions of Lucas' primality test and as far as I can see the algorithm for the examples shown on most sites seem to just be "For some number $n$ if $n$ has a primitive root ...
1
vote
2answers
111 views

primes and patterns/representations

As we know that primes other than 2 and 3 can be expressible as: $p \equiv 1\pmod{6}$ or $p \equiv -1\pmod{6}$. In other words, 6|(p-1) or 6|(p+1). Or, p = 6h+1 or 6h-1. Now, for any integer h, ...
1
vote
0answers
87 views

Is This a Good Prime Sieve?

I have played around with deriving a Boolean IsPrime function. http://science.niuz.biz/boolean-t313980.html?s=5e8b6805a1b73daa7c1062fabbe74e90 I have found a simple method for deriving a single ...
0
votes
0answers
135 views

Is there an emirp greater than $10^{10006}+941992101 \times 10^{4999}+1$?

An emirp is a prime such that a distinct prime is formed when its digits are reversed. According to Wikipedia (and its references), the largest known emirp is \[p:=10^{10006}+941992101 \times ...
1
vote
1answer
214 views

Prove an odd natural integer is composite if and only if it can be written in the form $n=x^2-y^2, y+1 < x$

Prove an odd natural integer is composite if and only if it can be written in the form $n=x^2-y^2, y+1 < x$ I do not see why $y+1 < x$ and I do not really know where to start. Proof: ...
1
vote
3answers
158 views

Explain why 67 is prime based on the fact that order of 2 mod 67 is 66

Without using the fact that 67 is prime, show that the order of 2 mod 67 is 66. Explain why this result proves that 67 is prime What I understand: The order of 2 in $\mathbb{Z}_{67}$(or mod $67$) $ ...