Math Is Fun Forum

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,711

Large Number Factored

These people managed to factor 2[sup]1039[/sup]-1: http://actualites.epfl.ch/presseinfo-com?id=441

Big Deal? Yes ... because the ability to factor numbers of this size means that internet security is not so secure.

It did take them 9 months, though.

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

mikau

Member

Registered: 2005-08-22

Posts: 1,504

Re: Large Number Factored

Cool! But how does the ability to factor large numbers pose a threat to internet security?

---

A logarithm is just a misspelled algorithm.

luca-deltodesco

Member

Registered: 2006-05-05

Posts: 1,470

Re: Large Number Factored

encryption.

---

The Beginning Of All Things To End.
The End Of All Things To Come.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Large Number Factored

Internet security depends on the fact that it's very difficult to factor large numbers. So if a method gets found that makes it easier, then it doesn't work any more.

Think of this analogy. Albert wants to give Benjamin an expensive gift (because Albert's so generous and cool), but for some unexplained reason he can only send it through the post.
However, Clyde the evil postman would like nothing better than to open the parcel and claim the generic expensive item for himself.

So, Albert puts the present in a box and padlocks it. Naturally, it's now safe from Clyde, but Benjamin can't get into it either. However, Benjamin puts his own padlock on it and mails it back to Albert. Albert can then take his padlock off, and the new padlock still keeps it safe from Clyde. Then Benjamin can take the other padlock off and the present is then his.

Of course, this would probably cost more than the value of the present in postage, but the important thing is that it was kept safe from Clyde. Unless of course, Clyde managed to find a way to break the padlocks, because that's what the security was founded on.

---

Internet security works in a similar way. This time, Albert wants to give Benjamin a really big prime number, that is somehow very important and secret and that no one else must know. So he makes up his own very big number and multiplies the important number by that. He then emails it to Benjamin, and any potential interceptors of that email wouldn't be able to factor it and so the important number stays safe. Then Benjamin multiplies that number by his very big number, emails that back to Albert who divides it by his, and then Benjamin divides the result by his number and finally he and only he knows what the original important number was.

This is all done by computers and stuff rather than two strange people who send numbers to each other, but that's the principle of the thing.

Sorry if that sounded patronising. Still, at least it didn't include any smilies.

---

Why did the vector cross the road?
It wanted to be normal.

anwar_auctions

Member

Registered: 2007-05-22

Posts: 0

Re: Large Number Factored

how math involve in writing the algorithm

Anthony.R.Brown

Banned

Registered: 2006-11-16

Posts: 516

Re: Large Number Factored

To MathsIsFun

Quote:" Big Deal? Yes ... because the ability to factor numbers of this size means that internet security is not so secure. "

A.R.B

It is secure if Numbers are mixed with letters etc. for Passwords etc......................................

Sekky

Member

Registered: 2007-01-12

Posts: 181

Re: Large Number Factored

It is secure if Numbers are mixed with letters etc. for Passwords etc......................................

You have no idea what they're talking about.

On topic, I don't think it's that much of a threat, considering that the last mersenne prime found was 2^32,582,657 -1 (just under ten million digits), so modular combination of sufficiently large primes should make decryption pretty much impossible. Suppose you take smaller ones and aim for a modular combination of a million digits, that's a one meg key (if my theory is wrong, shoot me down), which will be tame by tomorrow's bandwidth standards.

I don't think we're in trouble for the moment.

Anthony.R.Brown

Banned

Registered: 2006-11-16

Posts: 516

Re: Large Number Factored

Quote:"
On topic, I don't think it's that much of a threat, considering that the last mersenne prime found was 2^32,582,657 -1 (just under ten million digits), so modular combination of sufficiently large primes should make decryption pretty much impossible. Suppose you take smaller ones and aim for a modular combination of a million digits, that's a one meg key (if my theory is wrong, shoot me down), which will be tame by tomorrow's bandwidth standards.

I don't think we're in trouble for the moment. "

A.R.B

You have no idea what they're talking about. or any others!...............................................