Originally Answered: What is the significance of prime numbers?
To give an idea how hard it is:
The RSA Laboratories published several very large numbers that they had obtained by multiplying two prime numbers together
They did it in a way that guaranteed that nobody, even they themselves knows what the factors are, created using a hardware randomizer (so no algorithm) on a computer with no connection to any network, and then the numbers extracted, and the hard drive destroyed.
The RSA Factoring Challenge FAQ
They announced the challenge in 1991. And some of them were gradually factored, but only the smaller ones.
RSA numbers
Here is one of them (RSA-220):
2260138526203405784941654048610197513508038915719776718321197768109445641817966676608593121306582577250631562886676970448070001811149711863002112487928199487482066070131066586646083327982803560379205391980139946496955261
Has 220 digits
Has not yet been factored, 23 years later.
So, we believe that factoring numbers is hard. While multiplying is easy - only takes a fraction of a second to multiply two numbers of this size on a computer.
But - if someone did invent some really fast easy way of factorizing large numbers - our https type websites would no longer be secure, and we'd have to find some radically new approach.
So far no signs of that happening luckily!
We would need to think about changing to a new system if this number ever gets factored (RSA-1024)
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
Has 309 decimal digits.
The largest one factored so far is 232 digits (RSA-768)
12301866845301177551304949583849627207728535695953347921973224521517264000726365751874520219978646938995647494277406384592519255732630345373154826807917026122142913461670429214311602221240479274737794080665351419597459856902143413
=
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
×
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
So have a fair bit yet to go before we need to start thinking about what to replace it with, another 70 or so digits.
I imagine will happen eventually in the decades to come as computers get more powerful - that is if they do.
If it does happen - probably would start by news that someone factoredr a 309 digit number with say 1000 work stations working on the problem full time for six months, or whatever.
If it happens like that, probably most people don't need to worry too much about their day to day transactions instantly - would need to be a high profile or valuable secret to be worth 500 years of computer time to crack it - but would be a sign that we need to find a better system pretty soon probably.
But - it depends on maths. If some mathematician came up with some brilliant novel idea of a new way of looking at the problem from a surprising angle - could it be solved? Suddenly able to factorize huge numbers in seconds, almost as fast as we can multiply them? Or is it intrinsically hard in some way?
Quantum computers also could make factoring large numbers much easier.
About the Author
Robert Walker
Writer of articles on Mars and Space issues - Software Developer of Tune Smithy, Bounce Metronome etc.Studied at Wolfson College, Oxford
Lives in Isle of Mull
4.8m answer views110.4k this month
Top Writer2017, 2016, and 2015
Published WriterHuffPost, Slate, and 4 moreHuffPost, Slate, Forbes, Newsweek, Business Insider, and Science 2.0