Many comments here assume that the time to factor a composite integer N is proprotional to N, which is, happily, quite incorrect. Even by trial division, you only have to test prime divisors <=sqrt(N), and there are many far more efficient factoring methods.
A good paper, "A Survey of Modern Integer Factorization Algorithms" by P.L.Montgomery, can be found at Crypto World. It is slightly math-inclined but definitvely a worthwhile read for anyone interested in the topic.
Now for the bad news: 2048 bits can't be done today. Even GNFS, the best algo in town, has only managed to factor a 512 bits RSA key (and a 158 decimal digit number, with a 576 bits RSA coming soon, though) but 2048 bits will be million times harder. Right now there's no way to factor that, if Microsoft has chosen the primes for the key even remotely securely. I'm sorry to say that but with present technology, this project is a waste of time.
Alex
Re:Encryption and compression make a lot of sense.
on
PKWare Zips to Growth
·
· Score: 5, Interesting
Hopefully, if this is what they want to do, they will do better than the embarrasingly insecure "encryption" that the old DOS PKZip included (a cryptographically-weak LFSR-based stream cipher).
Yeah, the cipher was pretty weak. Interested people might like to read the paper A Known Plaintext Attack on the PKZIP Stream Cipher by Biham and Kocher. Esentially, a string of 13 known bytes and a few hours on a good PC will decrypt the rest of the file.
But what's even worse, imho, is the horribly bad implementation. They encrypted only the file contents; file name, size and (what were they thinking?) the CRC were all in the clear. If you were using encryption to hide the fact that you possess a file you're not meant to, Pkzip will do you in real nice.
All in all an excellent example of how crypto works not.
Man, I hate to think of the spam we are going to get. YUCK!
Wife (enters room): "Uuargh - What the hell are you doing?" Husband: "I got in in the mail, I swear!"
Alex
Re:What are you going to do? Beat cancer!
on
ECCp-109 Solved
·
· Score: 2, Insightful
I'd *love* to switch from SETI to the cancer research program, but I'm definitely not switching to Windows to do it!
Not sure what OS you are using, but if it's Linux or MacOS, folding is a go for you. See the client download page. Studying protein folding is maybe not as directly aimed at curing diseases as Cure Cancer@Home, but odds are that if we understand folding better, a good antibody or two (or more efficient means of looking for them) will spring off.
It's really a shame SuSE wouldn't wait for this release before shipping their product a couple weeks before.
As others have noted, there are too many major projects with unsynced release schedules that waiting to include all the great updates will imply waiting forever.
SuSE usually makes update packages available when a new version of KDE is released, check out LinuKS: SuSE Linux KDE Service (this is the german page). You should have no problems installing KDE 3.1 from there once it is released.
In a nutshell, you start with a composite number, write down the prime factors in decimal in ascending order of size and so get a new number, which may either be prime or composite. If prime, then this is the Home Prime of the number you started with. If composite, repeat.
All the numbers below 100 reach their Home Primes rather quickly - except for 49 (and thus, 77). This one is expanded to 95 steps by now and has grown into a 194 digit number which is becoming increasingly difficult to factor. The last 15 steps of this sequence were done by Paul Leyland of Microsoft Research, Cambridge, and myself. The 95th step is factored down to a 153 digit composite which we are struggling with right now. See
Patrick De Geest's page for the current status of this problem.
A difference between Home Primes and the 196 problem is that Home Primes can be shown to exist for every number - the probability that no Home Prime is found in as the number of expansion steps goes to infinity converges to zero. It is, however, quite possible that the number gets too large to factor with today's resources before the Home Prime is found. (That seems to be happening in the 49 case right now.) AFAIK no guarantee of a terminating sequence exists for the Palindrome problem, it is possible (and likely) that the 196 sequence spins off into infinity without ever becoming palindromic.
As far as I can tell, there is no practical use for either Palindromic numbers of Home Primes. It's just recreational - a way to spend spare time no better or worse than board games or sports on the TV. Except it involves massive amounts of cpu time and pretty advanced algorithms (i.e. ECM and GNFS) - the study of which I find extremely intriguing. It's probably one of the geekiest ways to spent your time (not that I were proud of that, I merely can't help it).
>Negative. Factoring reduces to RSAP (The RSA Problem).
>And RSAP reduces to factoring. They are computationally equivalent.
Are you sure about that? Decrypting an RSA message is taking a cubic root or 65537-th root (or whatevery your encryption exponent is) in a finite group modulo N, your public modulus.
Taking roots is easy if you know the cardinality of the group and you get the cardinality of the multiplicative group (mod N) easily if you know the factorization of N by Euler's totient function \phi(N).
If you know \phi(N) and N, getting the factorization of N is also easy, so these two are equivalent.
But, afaik, it has not been proven that you need \phi(N) to do discrete roots (mod N). If you have different information, please post it. That'd be interesting news (to me, anyways).
>But can you prove (not show with arbitrary probability)
>in your head that a given number is prime? For that matter,
>can you prove using a computer that a given large number
>(if you go for any) is prime? For some reason, I don't think so...
It depends on how much time you are willing to afford. A trivial algorithm is to try every (prime) number sqrt(N) to see if it divides N, if there is none, N is prime. But in practice this is too slow to let you get much beyond N ~20 digits.
Elliptic Curve Primality Proving is state of the art for general primality proofs today, try Primo which has been used to prove a 5020 digit number prime.
Integer factoring is much harder than proving primality, the current record for a GNFS factorization is a 158 digit composite, see
here.
>As it turns out, I know where socks go. According to a friend whose ex-husband used to repair washing machines, there is usually a gap between the basin and the top of the machine. Socks (and other light items) are occasionally sloshed over the top and into the internals of the washing machine.
Nope, sock disappear due to quantum mechanical effects in the confined space of the washer/dryer. Please check Laundry: A Quantum Mechanical Approach by Dr. Brian J. Reardon for the many surprising details.
The Wrong Trousers don't just hypothetically work well without dialogue, there hardly *is* any dialogue. The only character that talks is Wallace, and he talks only rubbish. "But.. this is the wrong trousers! Grooooomiiiiiiiiit....!"
*Everything* is going on with subtle expressions, hints in the scenery, skillful editing.. which makes The Wrong Trousers, compared to Final Fantasy, the more skillfully crafted movie, ihmo.
The Wrong Trousers is quite simply one of the best pieces of animation I have ever seen.
Another impressive bit is "Next", from the Aardman Shorts collection, by Barry Purves. Simply incredible.
I second Calvin's (of Calvin and Hobbes) opinion, "the surest sign that there IS intelligent life out there is that they haven't tried to contact us."
I prefer projects with a higher probability to make an actual differene to how people live, like the (already named) Folding@Home, Genome@Home, or FightAIDSatHome. The last one may not appeal to many here as Entropia, the distributed computing network behind it, apparantly insists in throwing in some commercial work packets to the clients. Finding a cure for AIDS sounds like a splendid idea, otoh.
My personal favorite is GIMPS, the Great Internet Mersenne Prime Search, discoverers of the four largest explicitly known prime numbers. I like them because you actually have a chance to understand what the program is doing (if number theory is for you, that is). IMHO better than looking at some blinking lights of a screen saver that looks for ET.
Slashdot Mirror
Many comments here assume that the time to factor a composite integer N is proprotional to N, which is, happily, quite incorrect. Even by trial division, you only have to test prime divisors <=sqrt(N), and there are many far more efficient factoring methods.
RSA Security Inc. has quite informative FAQs on this subject, for example The RSA Factoring Challenge FAQ or What are the best factoring methods in use today?
A good paper, "A Survey of Modern Integer Factorization Algorithms" by P.L.Montgomery, can be found at Crypto World. It is slightly math-inclined but definitvely a worthwhile read for anyone interested in the topic.
Now for the bad news: 2048 bits can't be done today. Even GNFS, the best algo in town, has only managed to factor a 512 bits RSA key (and a 158 decimal digit number, with a 576 bits RSA coming soon, though) but 2048 bits will be million times harder. Right now there's no way to factor that, if Microsoft has chosen the primes for the key even remotely securely. I'm sorry to say that but with present technology, this project is a waste of time.
Alex
Yeah, the cipher was pretty weak. Interested people might like to read the paper A Known Plaintext Attack on the PKZIP Stream Cipher by Biham and Kocher. Esentially, a string of 13 known bytes and a few hours on a good PC will decrypt the rest of the file.
But what's even worse, imho, is the horribly bad implementation. They encrypted only the file contents; file name, size and (what were they thinking?) the CRC were all in the clear. If you were using encryption to hide the fact that you possess a file you're not meant to, Pkzip will do you in real nice.
All in all an excellent example of how crypto works not.
Alex
SuSE, which participates in UnitedLinux, has something similar, called YOU (Yast Online Update).
Compares the packages you have installed with a list of available patch/update packages on the server and applies all the relevant ones.
I'm sure something similar will find it's way into UL.
Alex
Man, I hate to think of the spam we are going to get. YUCK!
Wife (enters room): "Uuargh - What the hell are you doing?"
Husband: "I got in in the mail, I swear!"
Alex
I'd *love* to switch from SETI to the cancer research program, but I'm definitely not switching to Windows to do it!
Not sure what OS you are using, but if it's Linux or MacOS, folding is a go for you. See the
client download page. Studying protein folding is maybe not as directly aimed at curing diseases as Cure Cancer@Home, but odds are that if we understand folding better, a good antibody or two (or more efficient means of looking for them) will spring off.
Alex
It's really a shame SuSE wouldn't wait for this release before shipping their product a couple weeks before.
As others have noted, there are too many major projects with unsynced release schedules that waiting to include all the great updates will imply waiting forever.
SuSE usually makes update packages available when a new version of KDE is released, check out LinuKS: SuSE Linux KDE Service (this is the german page). You should have no problems installing KDE 3.1 from there once it is released.
Alex
>PUH-LEASE!
>How do you think they made little baby Puritans?
This I'd like to know as well. It might be the answer to all of our geek problems.
Alex
the world's first advent calendar.
Remember: don't open that last door before the 24th.
Alex
kroupware(*)
:) ]
[* is anyone suprised by the name?
I'm only surprised they didn't name it Krautware.
Oh, btw, I'm German.
Alex
In a nutshell, you start with a composite number, write down the prime factors in decimal in ascending order of size and so get a new number, which may either be prime or composite. If prime, then this is the Home Prime of the number you started with. If composite, repeat.
All the numbers below 100 reach their Home Primes rather quickly - except for 49 (and thus, 77). This one is expanded to 95 steps by now and has grown into a 194 digit number which is becoming increasingly difficult to factor. The last 15 steps of this sequence were done by Paul Leyland of Microsoft Research, Cambridge, and myself. The 95th step is factored down to a 153 digit composite which we are struggling with right now. See Patrick De Geest's page for the current status of this problem.
A difference between Home Primes and the 196 problem is that Home Primes can be shown to exist for every number - the probability that no Home Prime is found in as the number of expansion steps goes to infinity converges to zero. It is, however, quite possible that the number gets too large to factor with today's resources before the Home Prime is found. (That seems to be happening in the 49 case right now.) AFAIK no guarantee of a terminating sequence exists for the Palindrome problem, it is possible (and likely) that the 196 sequence spins off into infinity without ever becoming palindromic.
As far as I can tell, there is no practical use for either Palindromic numbers of Home Primes. It's just recreational - a way to spend spare time no better or worse than board games or sports on the TV. Except it involves massive amounts of cpu time and pretty advanced algorithms (i.e. ECM and GNFS) - the study of which I find extremely intriguing. It's probably one of the geekiest ways to spent your time (not that I were proud of that, I merely can't help it).
Alex
>I can see it now... www.LeanerSpotting.com
If you pull it off nicely, you might ask the leaner to borrow the phone to take a picture of her and use the email function to submit it.
Alex
Just put a keyphrase in the filenames to identify complete copies, such as "Hilary Rosen sucks ass".
I don't suppose they would spoof that.
Alex
>And RSAP reduces to factoring. They are computationally equivalent.
Are you sure about that? Decrypting an RSA message is taking a cubic root or 65537-th root (or whatevery your encryption exponent is) in a finite group modulo N, your public modulus.
Taking roots is easy if you know the cardinality of the group and you get the cardinality of the multiplicative group (mod N) easily if you know the factorization of N by Euler's totient function \phi(N).
If you know \phi(N) and N, getting the factorization of N is also easy, so these two are equivalent.
But, afaik, it has not been proven that you need \phi(N) to do discrete roots (mod N). If you have different information, please post it. That'd be interesting news (to me, anyways).
Alex
>in your head that a given number is prime? For that matter,
>can you prove using a computer that a given large number
>(if you go for any) is prime? For some reason, I don't think so...
It depends on how much time you are willing to afford. A trivial algorithm is to try every (prime) number sqrt(N) to see if it divides N, if there is none, N is prime. But in practice this is too slow to let you get much beyond N ~20 digits.
Elliptic Curve Primality Proving is state of the art for general primality proofs today, try Primo which has been used to prove a 5020 digit number prime.
Integer factoring is much harder than proving primality, the current record for a GNFS factorization is a 158 digit composite, see here.
Alex
> condoms are free at colleges. I recommend a vibrator. Like a Hello Kitty Vibrator
Didn't you read the article heading? It says "from the tools-for-use-outside-of-the-box dept."
Alex
>Rob buddy, you'd just better pray that Kathleen didn't read this one.
Read the quote at the bottom of the page:
"It is better to have loved and lost -- much better."
Alex
(does the better refer to just the lost, or both?)
after "IJ and the Temple of Doom", the new title is obviously, "IJ and the Ascent to Quake 3 Arena".
Alex
Nope, sock disappear due to quantum mechanical effects in the confined space of the washer/dryer. Please check Laundry: A Quantum Mechanical Approach by Dr. Brian J. Reardon for the many surprising details.
Alex
The Wrong Trousers don't just hypothetically work well without dialogue, there hardly *is* any dialogue. The only character that talks is Wallace, and he talks only rubbish. "But.. this is the wrong trousers! Grooooomiiiiiiiiit....!"
*Everything* is going on with subtle expressions, hints in the scenery, skillful editing.. which makes The Wrong Trousers, compared to Final Fantasy, the more skillfully crafted movie, ihmo.
The Wrong Trousers is quite simply one of the best pieces of animation I have ever seen.
Another impressive bit is "Next", from the Aardman Shorts collection, by Barry Purves. Simply incredible.
Alex
I prefer projects with a higher probability to make an actual differene to how people live, like the (already named) Folding@Home, Genome@Home, or FightAIDSatHome. The last one may not appeal to many here as Entropia, the distributed computing network behind it, apparantly insists in throwing in some commercial work packets to the clients. Finding a cure for AIDS sounds like a splendid idea, otoh.
My personal favorite is GIMPS, the Great Internet Mersenne Prime Search, discoverers of the four largest explicitly known prime numbers. I like them because you actually have a chance to understand what the program is doing (if number theory is for you, that is). IMHO better than looking at some blinking lights of a screen saver that looks for ET.
Alex