4 ms·
Primes and Primality Testing
- mbid 9y agoThe two definitions of primality given in the beginning of the article are not equivalent -- one rules out 1, the other one doesn't.
- animeshk 9y agoI'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?
- stablemap 9y agoIf in (2) “itself” is 1 then you are listing the same thing twice—that shouldn’t count as two factors.
- yorwba 9y agoDefinition 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.
- animeshk 9y agoOkay.. 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.
- mbid 9y agoI 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 https://en.wikipedia.org/wiki/Prime_element)
- kmill 9y ago"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.
- coldcode 9y agoPrimes 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).
- pavel_lishin 9y agoI think just about every non-mathematician has at some point been enamoured with either primes, or pi.
- animeshk 9y agoSame here.. My fascination began when I learned about Glitch Primes, Cyclops numbers and the bloody Riemann Hypothesis!
- hannob 9y ago"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 is one of the most challenging aspects of mathematics and computing. 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.
- animeshk 9y agoYou're absolutely right. I just made that change in the article. Thanks for pointing it out!
- deleted 9y ago[deleted]
- graemewicksted 9y agoI 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.
- nightcracker 9y agoI 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.
- akalin 9y agoYou 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 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.
- slitaz 9y agoHas typos. Says that 199^883467 is difficult to factorise. Well, all 883467 factors are shown already.
- animeshk 9y agoI wish i could type out that number without losing my sanity.
- lisper 9y agoIt's not so bad, only 2030961 digits. The first few are: 67741756636479844500840... and the last few are: ...12967674786324684253399
- jabretti 9y agoThat'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!
- btilly 9y agoThere 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. :-)
- animeshk 9y agoWow. didn't know that! Will add it to the section on Rabin-Miller. Thanks :)
- finchisko 9y agoIt 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?
- animeshk 9y agoWhen 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'.