Over the years, mathematicians have done much wiggling of fingers in ears & pencil-chewing, while pondering the inscrutable nature of prime numbers. Normally I'm wary of asking questions that might not have any answer at all, but in this case it looked like the answer might be before me, dangling just beyond reach, like fruit from a tree … overhanging a cliff-edge. So like many before, arm out-stretched, I lunged towards the precipice, issuing the fatal question, "Where exactly are they ?", followed by "What are they ?". What happens next is normally a sensation of falling, perhaps like Alice may have felt while descending the rabbit-hole, but in stark contrast to Jennifer Lopez, this one is almost bottomless.
Regrettably those prime swine have effortlessly repelled all boarders. All we really know is that by Euclid's Theorem, there're an infinite number of them, but by the Prime-number Theorem, they become progressively more widely spaced. Though one can use the Sieve of Eratosthenes to efficiently enumerate them, nobody has yet discovered any precise pattern to their distribution, or an efficient algorithm to decompose a composite integer to its prime factors. So one can easily obtain the product, just not the bill of materials, hence their relevance to public-key cryptography.
Mathematical circles (ironically shapeless) would have been filled with a lot more mathematicians peacefully reading the newspaper or eating buttered toast, had nobody thought to ask that wretched question, or wanted to know its answer. Regrettably, they did ask the question, & (as a mark of the breed) they always seem to want to know the answer, even when the question has no relevance to anything known … though this one does.
The question can be explored in separate stages:
- Prime-number generation:
What are the prime-numbers ?
Is my integer atomic ?
Okay, but if I smash it into atoms, what are they ?
Most of the other functions implemented on this web-site, have been tested using exponentially increasing abscissæ; typically 2n. This allows one to test a wide domain, without wasting an inordinately long time on a myriad of big integers of similar magnitude. Regrettably, that simple scheme is inappropriate for either primality-testing or prime-factorisation, because the integers in such sequences (other than potentially the first) are never prime.
Lacking a better idea, I've chosen the Fibonacci-sequence, which though rather arbitrary, does at least form a sequence which grows exponentially, & which contains some (possibly infinitely many) primes, including published values against which my implementations can be checked.
My usual test-platform was used.