3
votes
0answers
46 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
61 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
45 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
41 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 ...
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 ...
5
votes
3answers
855 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
98 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 ...
19
votes
2answers
362 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
44 views

Finding errors in primality tests?

How do you know when a primality test generates a number that is not prime?
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
2k 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
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
149 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
91 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 ...
2
votes
1answer
130 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
303 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
160 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
2answers
210 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
89 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 ...
5
votes
4answers
240 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
158 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 ...
1
vote
1answer
125 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
112 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
137 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
3answers
159 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$) $ ...
0
votes
2answers
138 views

Use Lucas' test with $a=7$ and prove $71$ is prime

My working so far: $71-1=70$ and Prime factors of $70$ are $2 \times 5 \times 7$ Check $a=7$: $7^{(\frac{70}{2})} \equiv 7^{35} \equiv x (mod 71)$ How do I find $x$? Usually I would use Fermat's ...
3
votes
2answers
174 views

Can all primes be written as a Mersenne prime?

Do all primes can be written in form of Mersenne prime? If not, why Mersenne form is important?
5
votes
1answer
162 views

P[random x is composite | $2^{x-1}$ mod $x = 1$ ]?

Select a uniformly random integer $n$ between $2^{1024}$ and $2^{1025}$ (Q) What is the probability that n is composite given that $2^{n-1}$ mod $n = 1$ ? How did you calculate this? More info: ...
5
votes
7answers
3k views

Prime number generator, how to make

Can anybody point me an algorithm to generate prime numbers, I know of a few ones (Mersenne, Euclides, etc.) but they fail to generate much primes... The objective is: given a first prime, ...
1
vote
2answers
90 views

Primality test of quadratic polynomials

There are some quadratic polynomials like $n^2+1$ that there exist infinitely many integers $n$ such that their value is either prime or the product of two primes (if I am right!). I wanted to know if ...
3
votes
1answer
140 views

Check for prime

I know there are a lot of questions on this board about finding prime numbers, and I've gone through a bunch of them. I even came across this interesting site about primes: ...
9
votes
2answers
640 views

On proof of AKS primality test algorithm

Just studying the paper PRIMES is in P, although I've tried great efforts, some proofs are still not so clear(or obvious) to me, especially the proof of ...
8
votes
1answer
519 views

Finding the first number larger than N that is a relative prime to M

I am not sure if this question is best suited for math exchange. I already tried on stackoverflow without any luck, so I hope that your bright minds will be more helpful. So, basically the tile says ...
0
votes
1answer
123 views

An alternative way to test primality of Mersenne numbers?

Theorem : If Mersenne number can be uniquely written in the form : $x^2+3 \cdot y^2$ , where $\gcd(x,y)=1$ and $x,y \geq 0$ then that number is a prime number . Primality test for ...
6
votes
1answer
671 views

Implementing Fermat's Primality Test

I am trying to implement Fermat's primality test to test whether a given number n is prime or not. According to Wikipedia the test is as follows: Given an integer n, choose some integer a coprime ...
8
votes
3answers
368 views

Understanding AKS

new user here. Where does a layman go to get a basic understanding of AKS primality testing. I am not talking about the optimal choice of "r" (which I am told is the hardcore number theoretic part of ...
3
votes
1answer
151 views

Miller primality test bound

Good morning! I'm on my way to implement a deterministic (though unproven due to GRH) Miller primality test. On Wikipedia, it is said that it suffices to test all numbers in $[2, ...
15
votes
4answers
8k views

Simple explanation and examples of the Miller-Rabin Primality Test

Coming from an understanding of Fermat's primality test, I'm looking for a clear explanation of the Miller-Rabin primality test. Specifically: I understand that for some reason, having non-trivial ...