Primes and Primality Testing(clerro.com)
clerro.com
Primes and Primality Testing
http://www.clerro.com/guide/571/primes-and-primality-testing
27 comments
You're absolutely right. I just made that change in the article. Thanks for pointing it out!
You still mention that:
> There's no slick trick to check fast enough, whether or not a large number is prime. So much so that finding large prime numbers has been an obsession for mathematicians.
But that's still false; in fact, the rest of your article talks about the Fermat and Miller-Rabin primality test, which are indeed slick tricks that can check fast enough whether or not a large number is prime (to whatever degree of confidence you desire)!
Also, finding large prime numbers isn't really an obsession anymore -- you can use any of the fast primality test algorithms mentioned above, randomly generate numbers of a desired bit length, and stop when you hit a (probable) prime, which happens fairly quickly by the prime number theorem: https://en.wikipedia.org/wiki/Prime_number_theorem
You may be thinking of the search for Mersenne primes, or other primes of a specific form.
> There's no slick trick to check fast enough, whether or not a large number is prime. So much so that finding large prime numbers has been an obsession for mathematicians.
But that's still false; in fact, the rest of your article talks about the Fermat and Miller-Rabin primality test, which are indeed slick tricks that can check fast enough whether or not a large number is prime (to whatever degree of confidence you desire)!
Also, finding large prime numbers isn't really an obsession anymore -- you can use any of the fast primality test algorithms mentioned above, randomly generate numbers of a desired bit length, and stop when you hit a (probable) prime, which happens fairly quickly by the prime number theorem: https://en.wikipedia.org/wiki/Prime_number_theorem
You may be thinking of the search for Mersenne primes, or other primes of a specific form.
[deleted]
I thought modern RSA crypto intentionally stays away from real primes because it's less secure. They use two semi-prime co-primes of significant size and with a large enough difference between them.
I think you're confused.
A RSA private key uses large primes, two to be exact. Those two primes form your private key. Multiplying them together gives your public key. The idea is that undoing that operation: finding which two primes multiplied together form the public key, is an intractable problem.
Those two primes multiplied together is what's called a semiprime. The one part that you're correct on is that these two primes should be sufficiently distant, otherwise just trying a couple numbers near sqrt(pq) will give you either p or q.
A RSA private key uses large primes, two to be exact. Those two primes form your private key. Multiplying them together gives your public key. The idea is that undoing that operation: finding which two primes multiplied together form the public key, is an intractable problem.
Those two primes multiplied together is what's called a semiprime. The one part that you're correct on is that these two primes should be sufficiently distant, otherwise just trying a couple numbers near sqrt(pq) will give you either p or q.
[deleted]
There is a mistake in the description of the Rabin-Miller test.
The test itself is deterministic. If you try it for more than half of the numbers in the range, it gives you an exact answer.
In practice we run it as a probabilistic test because we don't want to test all of those numbers. :-)
The test itself is deterministic. If you try it for more than half of the numbers in the range, it gives you an exact answer.
In practice we run it as a probabilistic test because we don't want to test all of those numbers. :-)
Wow. didn't know that! Will add it to the section on Rabin-Miller. Thanks :)
Primes have always fascinated me despite not being a mathematician. Counting numbers are regular yet the pattern of primes seems not to be (although there is a way of plotting them that makes pretty spiral like structures).
I think just about every non-mathematician has at some point been enamoured with either primes, or pi.
Has typos.
Says that 199^883467 is difficult to factorise. Well, all 883467 factors are shown already.
Says that 199^883467 is difficult to factorise. Well, all 883467 factors are shown already.
I wish i could type out that number without losing my sanity.
It's not so bad, only 2030961 digits. The first few are:
67741756636479844500840...
and the last few are:
...12967674786324684253399
67741756636479844500840...
and the last few are:
...12967674786324684253399
That'd have roughly as many characters as a 338,000 word book... longer than The Brothers Karamazov (365,000) but shorter than Gone With The Wind (418,000).
Just over half the length of A Suitable Boy by Vikram Seth, and probably just as entertaining. Heyooo!
Just over half the length of A Suitable Boy by Vikram Seth, and probably just as entertaining. Heyooo!
It might be late and me being tired, but isPrime function will return false for 1 and any other prime? Shouldn't it be true when function is called isPrime?
When a test is contrapositive, it's actually testing for composites. So technically, it should output True for composite but then, the name isPrime doesn't do justice. So I changed the outputs to strings 'Prime' and 'Composite'.
The two definitions of primality given in the beginning of the article are not equivalent -- one rules out 1, the other one doesn't.
I'm trying to look for the inequivalence you pointed at. The two definitions written are-
1.A prime number is a natural number that has no positive divisors other than 1 and itself.
2. A prime number is a number that has exactly two factors - 1 and itself.
Both statements clearly seem to be accounting for 1. Am I missing something here?
1.A prime number is a natural number that has no positive divisors other than 1 and itself.
2. A prime number is a number that has exactly two factors - 1 and itself.
Both statements clearly seem to be accounting for 1. Am I missing something here?
"Itself" might be 1 in the first definition. The "exactly two" in the second definition is what makes the definitions different.
I'm not able to read the article because of a 503 timeout, so I can't see this in context, so the following might be irrelevant or off the mark (sorry).
A more interesting/usual pair of definitions is
1. A non-unit p is prime if whenever p divides ab then p divides a or p divides b.
2. A nonzero number n is composite if there are non-units a and b such that n = ab.
Then there is a short proof that, for nonzero non-units, being prime is equivalent to not being composite. (A unit is a number with a reciprocal in the number system. For the integers, that would be 1 and -1.)
The two definitions capture different (but equivalent) parts of the atomic nature of primes.
Elsewhere in mathematics, there are the concepts of irreducibility (whether an object has a subobject) and indecomposibility (whether an object splits into subobjects), where in general irreducible things are indecomposible. Basically, the fact that long division works implies that indecomposible numbers are irreducible and that irreducible factors don't straddle the decompositions.
I'm not able to read the article because of a 503 timeout, so I can't see this in context, so the following might be irrelevant or off the mark (sorry).
A more interesting/usual pair of definitions is
1. A non-unit p is prime if whenever p divides ab then p divides a or p divides b.
2. A nonzero number n is composite if there are non-units a and b such that n = ab.
Then there is a short proof that, for nonzero non-units, being prime is equivalent to not being composite. (A unit is a number with a reciprocal in the number system. For the integers, that would be 1 and -1.)
The two definitions capture different (but equivalent) parts of the atomic nature of primes.
Elsewhere in mathematics, there are the concepts of irreducibility (whether an object has a subobject) and indecomposibility (whether an object splits into subobjects), where in general irreducible things are indecomposible. Basically, the fact that long division works implies that indecomposible numbers are irreducible and that irreducible factors don't straddle the decompositions.
Definition 1 says that 1 is a prime (it has no positive divisors except 1 and itself (1)).
Definition 2 says that 1 is not a prime: it does not have exactly two factors, but just one.
Definition 2 says that 1 is not a prime: it does not have exactly two factors, but just one.
Okay.. so 1 should neither be prime nor composite. Because -
a) 1 cannot be written as a product of two different factors : ruling out 1 to be composite
b) 1 has only 1 positive divisor : ruling it out to be prime
That's indeed a special case which can be mentioned in the article.
That's indeed a special case which can be mentioned in the article.
I would simply not define "prime" or "composite" for 1, yes. If you check abstract algebra books (or wikipedia [1]), you'll usually find definitions along the lines of "a non-invertible, non-zero element is prime if and only if ...", and the nice thing about this definition is that it is a useful concept in more general structures than just natural numbers, namely (semi)rings.
[1](https://en.wikipedia.org/wiki/Prime_element)
[1](https://en.wikipedia.org/wiki/Prime_element)
If in (2) “itself” is 1 then you are listing the same thing twice—that shouldn’t count as two factors.
This very fact, that large prime numbers are hard to find, is the basis of cryptography which is fundamental to cyber security."
That is simply flat out wrong.
What they probably are referring to is RSA. However the basis of RSA is not that it's hard to find a large prime number. (Actually if that would be hard then RSA would be impossible, as it needs large primes for key generation.) The basis is that it's hard to factorize a composite number.