## Comment Lears (Score 5, Funny) 272

Apparently, it hasn't leared how to spell yet.

Attend or create a Slashdot **20th anniversary party!** **DEAL:** For $25 - **Add A Second Phone Number To Your Smartphone for life! Use promo code SLASHDOT25.** Check out the new **SourceForge HTML5 Internet speed test.**
×

Apparently, it hasn't leared how to spell yet.

It's very possible that this is just a coincidence and that this has nothing to do with the meaning of the bits. Sure, it seems like there's no way it could be by accident that a number around 6.8 billion is prime, but there is:

The chances of a random number x being prime are about ln x. ln 6830770643 ~= 22.6, but it's possible that the first number had to be 1, which would mean (since it's palindromic) the last number has to be 1 (making the number odd), excluding 2 as a possible factor. This puts the chance at more like 11.3. It's quite possible that we're reading too much into this. This might've just been randomly picked by an artist, (and then made symmetrical by making it a palindrome) instead of designed by a geek (and intentionally including a hidden meaning or just making it a prime or something).

In searching for additional evidence that primes were an intentionally selected theme, I looked at:

11001011100100101

10100100111010011

0100100111010011

1100101110010010

(each half of the palindrome, with and without the 1 in the center)

One of these is prime: 0100100111010011_2=18899_10, 18899 is prime. I'm not sure what it means, but I doubt those substrings were chosen for their primality.

Hugh Pickens writes *"CIOL reports that Wikipedia has revealed the secret of Agatha Christie's famous murder mystery 'The Mousetrap' by identifying the killer in the world's longest running play, now at over 24,000 performances ever since its maiden performance in 1952, despite protests from the author's family and petitions from fans who think the revelation is a spoiler. Angry at the revelation, Matthew Prichard, Christie's grandson, who describes the decision of Wikipedia as 'unfortunate,' says he will raise the matter with the play's producer, Sir Stephen Waley-Cohen. 'My grandmother always got upset if the plots of her books or plays were revealed in reviews — and I don't think this is any different. It's a pity if a publication, if I can call it that, potentially spoils enjoyment for people who go to see the play.' Unrepentant, Wikipedia justifies the decision to reveal the ending of the play. 'Our purpose is to collect and report notable knowledge. It's exceedingly easy to avoid knowing the identity of the murderer: just don't read it.'"*

I'm from the UK, is 4+3+2=( )+2 a commonly used / commonly understood way of presenting the problem in the US?

No, that's not standard usage in the US or anywhere else that I'm aware of.

It's always possible the report was not properly representing what he was trying to convey, but the report definitely shows usage that isn't clear for anyone, unless it was explained on the test. No wonder people are confused.

Meshach writes *"In Canada, a nineteen-year-old man has lost his driving license for six months and is facing one year of probation after the police arrested him for dangerous driving as a result of a post on an online message board. The tip apparently came from an uninvolved American who called the Canadian authorities after he saw the post bragging about how fast the man went."*

An anonymous reader noted a report confirming the first ever exoplanet actually photographed from telescopes on earth. Every other exoplanet so far 'observed' has been done by measuring wobbles of stars pulled by planetary gravity. But this one is a photograph. And that's just plain cool.

l_i_g_h_s_p_e_e_d writes *"The trailer for **Sintel* is ready. (We discussed the beginnings of this project in 2007.) *Sintel* is a Blender Open Movie project created using only FLOSS software. 'For the entire creation pipeline in the studio, we will only use free/open source software. We have less than two months now to finish this completely. ... Imagine the tension that's building up here to get everything perfect. For today, we'll celebrate a big step forward.' Download here."

Blizzard announced today that *StarCraft II: Wings of Liberty*, the first game in a series of three, will be released on July 27. The game will contain the Terran campaign (29 missions), the full multiplayer experience, and "several challenge-mode mini-games," with "focused goals designed to ease players into the basics of multiplayer strategies." It will launch alongside the revamped Battle.net, which we've previously discussed. Blizzard CEO Mike Morhaime said, "We've been looking forward to revisiting the *StarCraft* universe for many years, and we're excited that the time for that is almost here. Thanks to our beta testers, we're making great progress on the final stages of development, and we'll be ready to welcome players all over the world to *StarCraft II* and the new Battle.net in just a few months."

Seahawk was one of several readers to write in with news of Denmark's decision to embrace ODF. *"On Friday morning Denmark decided to choose ODF over Microsoft's OOXML. For now the decision is only effective for governmental institutions, but regions and municipalities will most likely follow some time in the future. The decision has unfolded over a period of four years, and many open source advocates were fearing the worst, but it looks like the minister finally caved in and listened to what a lot of people were saying."* While in transition away from Microsoft Office formats, the Danes may find use for this new OpenOffice integration guide (sent in by reader AdeleWard).

digitalPhant0m writes to tell us that IBM researchers have set a new world record for areal data density on linear magnetic tape, weighing in at around 29.5 billion bits per square inch. This achievement is roughly 39 times the density of current industry standard magnetic tape. *"To achieve this feat, IBM Research has developed several new critical technologies, and for the past three years worked closely with FUJIFILM to optimize its next-generation dual-coat magnetic tape based on barium ferrite (BaFe) particles. [...] These new technologies are estimated to enable cartridge capacities that could hold up to 35 trillion bytes (terabytes) of uncompressed data. This is about 44 times the capacity of today's IBM LTO Generation 4 cartridge. A capacity of 35 terabytes of data is sufficient to store the text of 35 million books, which would require 248 miles (399 km) of bookshelves."*

The first time you encounter the concept of factoring (as per OP's question) is probably not the best time to introduce mathematics requiring groups and rings.

Granted.

And while the GNFS is indeed magnificently superior to naive searching, it is not sufficiently fast to make a significant difference to the cryptographic strength of a system based on the difficulty of finding large factors - hence, I judged it was not worth mentioning.

While the fact remains that you can make the number large enough for it to be impractical even with GNFS, I must disagree that it makes no significant difference. If the only thing we could do was trial division by primes, a 44 digit RSA composite would need at most ~200 quintillion divisions to find the factors. (see http://primes.utm.edu/howmany.shtml, there are ~200 quintillion primes below 10^22) More than sufficient for safe encryption. Even if you could do 1 billion per second, you'd need almost 6400 years to crack it.

But since there's GNFS, a 309 digit (1024 bit) number is currently the standard, and is being phased out.

In any case, you could've said something along the lines of "There are some more efficient ways, but they are still difficult for large numbers." instead of "There are some tricks you can use to speed it up, but that's essentially it."

It is cryptographically useful because it doesn't have a short way of doing it: you have to simply try dividing by 2, 3, 4, 5, etc, till you get an answer. When you have a number that's several hundred digits long and only has two relatively large factors, this takes a very long time. There are some tricks you can use to speed it up, but that's essentially it.

This is very, very wrong. What you describe is the most naive possible way to factor a number, a.k.a. trial division (without an obvious "trick" to speed it up: not bothering dividing by composites). There are far more efficient ways to factor large numbers. The fastest, currently, for numbers over about 90 digits without any easily-found smaller factors, is the General Number Field Sieve.

http://en.wikipedia.org/wiki/Integer_factorization

http://en.wikipedia.org/wiki/Trial_division

http://en.wikipedia.org/wiki/General_number_field_sieve

you could crack a 768-bit RSA in... roughly guessed...

Sorry, no. That doesn't take into account the fact that some parts can't be run in parallel on many home computers. Not to mention that the longest part, sieving, for a number this size, needs about 1 GB of RAM free, which I'd think people would be likely to notice and shut down pretty quickly...

Sieving is the step that takes the most time, in this case 1500 CPU years ("On a single core 2.2 GHz AMD Opteron processor with 2 GB RAM per core, sieving would have taken about fifteen hundred years."), but can easily be run in parallel. Let's say you have access to 100,000 cores, each with at least 1 GB of RAM that you can use (read the PDF...). It will now take you 5.475 days to do the sieving.

Polynomial selection can, like sieving, be easily distributed, and is a relatively trivial task with 100,000 cores available. (roughly 20 CPU years, or under 2 botnet-hours, and a non-enormous amount of RAM)

The hard parts are the final steps: filtering, building a matrix, solving it, and finding the factors. You basically need one or more supercomputers to do it, with at least one of them having 1 TB of RAM and fast access to 5 TB of data. To do it like they did, you'd also need to write your own block Wiedmann implementation. If not, you'd have to use the block Lanczos, which can only be run on a single computer/supercomputer/cluster.

Doubtless, someone could botnet enough computing power to sieve for an RSA-768 key in a matter of weeks, but to actually finish it and get the factors would require an expensive supercomputer, be it purchased, (better hope whatever's behind that key is valuable...and thank goodness that they were stupid enough to use just a 768-bit key on it) botnetted, (good luck to get one and not have anyone notice!) or otherwise acquired.

Frequent Slashdot contributor Bennett Haselton writes *"An estimated 200,000 Hotmail users currently have their auto-reply set to a message spamming an advertisement for Chinese scam websites, which sell "discounted" electronics. Presumably the spammers compromised a large number of Hotmail accounts to pull this off, but wouldn't it be pretty easy for Hotmail to query for which users have that set as their auto-reply, and turn the auto-reply off for them?"* Read below for Bennett's thoughts.

What they did was factor a 768-bit number, like one that could be used as a 768-bit RSA public key. e.g. to factor 15, you need to find that it is equal to 3*5, which can be easily done by dividing the first few primes and finding that 3 divides 15. To factor a very large number, like a 768-bit number that is semiprime with the two factors both about the same size, (as is the case with RSA public keys) is a very difficult task. It is currently best done by the General Number Field Sieve (GNFS). For more info on any of these concepts, use Wikipedia.

This demonstrates the possibility of breaking any given 768-bit RSA key by factoring the public modulus, and shows how much work that takes. Note, however, that it is still very difficult, and in this case took multiple years of calendar time and hundreds of years of CPU time to crack.

This does not mean that every 768-bit RSA key can be cracked any more easily than it could before, it just demonstrates that we have the ability to crack any 768-bit RSA key (given the time and resources).

"The voters have spoken, the bastards..." -- unknown