Surely they have computer programs that can work out if it's a prime number in like, a few seconds? (As in, so how's what they've got now an improvement?) Still, makes a change from it being Americans. Please Register or Log in to view the hidden image!
. Computers can only find prime factorization quickly if it's a small number - if you have a humongous 500 digit number it can take a computer a very long time. Does anyone know if this poses a threat to encryption schemes that are based on prime numbers, like RSA?
A prime number with hundreds of digits, takes weeks for a computer to check. Yes if primes can be found and numbers checked for primeness quickly it will weaken RSA and other cryptos. The method the dudes found is simple to program, and different from the brute force of try dividing by each number till you get a hit or get above the square root. BUT (according to comentators) the new method is not drastically faster.
Heh, thought computers were faster than that. Still, suppose every little helps. Why are prime nunbers so essential in an encryption? (I really don't belong in this forum Please Register or Log in to view the hidden image!)
here is a small demonstration of how prime numbers are important for encryption: it is not currently possible to factor very large numbers in a short amount of time. I will use that fact to encrypt my message. Lets say my message has 100 characters. i choose 100 primes, in ascending order. make them large primes. at least 10-100 digits each. then, i change each letter a-z to 1-26, and raise the corresponding prime to that power. for example, if the first prime is 11, the second is 13, and the first word of the message is "ad", then i will get 11^1 and 13^4 as my first two numbers. Finally, i multiply all those numbers together. it will be an enormous number, on the order of 10^1000 digits. but computers can do multiplication very very very fast. now i send my huge number to my friend, and if she knows my list of primes, then she can just start dividing them and see if they are factors. it is quite easy to take a list of 100 primes and see if they are factors. dividing is almost as fast as multiplying. someone who doesn t know the list of primes will never be able to factor the number. there is no way to check and see whether a number is prime (quickly). it would take many times the age of the universe to check a number with as many digits as i mention. because of the prime factorization uniqueness theorem, when the friend factors the number, she will see a list of exponents over her primes, the exponents will be in the range 1-26, each one corresponding to a letter of the alphabet. she can now easily decode the message. this is not really how encryption is done, this is too simple, and rather unpractical, but the underlying principal is the same. the key is this: multiplying primes is easy, factoring them is hard. any process that cannot be undone is a loss in information. a gain in entropy. as soon as someone develops a way to easily check whether a number is a prime, then she won t need a key, a list of primes, to decode the message.
Might this breakthrough help in solving the Clay Mathematics Institute's Millenium Prize Problem concerning the Riemann Hypothesis? http://www.claymath.org/prizeproblems/riemann.htm Solve it and win $1,000,000! Please Register or Log in to view the hidden image!
By the way the fx was constructed (and extended) all even negative numbers were immediate --uninteresting-- solutions
That's very interesting. I would have thought computers were faster than that. From reading this thread, it seems like what the researchers did lessons the strength of common day encryption. Why is that a good thing? Does this new algorithm make it easier to develop a better encryption algorithm in some way? As you can tell, I'm lost in how this is better for security.
