Primes and Primality Testing
clerro.com
clerro.com
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.
> 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.
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.
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. :-)
Says that 199^883467 is difficult to factorise. Well, all 883467 factors are shown already.
67741756636479844500840...
and the last few are:
...12967674786324684253399
Just over half the length of A Suitable Boy by Vikram Seth, and probably just as entertaining. Heyooo!
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?
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 2 says that 1 is not a prime: it does not have exactly two factors, but just one.
That's indeed a special case which can be mentioned in the article.