Seeing many comments from people who hardly know anything about the underlying math, I decided to post them
Euler said: For any number m, x^{\Phi(m)} mod m == 1 where \Phi(m) is the number of n<m for which gcd(n,m) == 1 If m has the prime factors p_1,p_2...p_k, then \Phi(m) equals the product of the (factors minus one), \prod_i (p_i-1) RSA uses that property. I construct a m = p*q, where I know the prime numbers p and q. These are very hard to find out for you. I therefore know that \Phi(m) = (p-1)(q-1). I give you m and e, you give me y=x^e (mod m), I calculate d, such that (d*e) mod \Phi(m) = 1 and do y^d = x^(d*e) = x^1 = x (mod m).
That probably wasn't really for Dummies... - Alex PS Can you tell I'm doing LaTeX lately?;-)
See my reply above yours to see why the proof of that claim is trivial, yet has nothing to do with N=P*Q, where P and Q are prime. The only important property is that N isn't divisible by 2 or 3.
RSA would never use a prime number so small as 2 or 3.
That is just plain wrong. You can freely multiply your modulo with 2^n to conveniently align it for easier modulo-multiplication (E.g. w/ Barrett's algorithm). The number you need to know to decrypt is the product of all (prime factors - 1) so multiplying by two changes nothing. (Not even the space of originial data where encryption is bijective)
Diffie-Hellmann uses prime numbers[*]. It wouldn't be touched by efficient factorization, though, as it relies on the hardness of finding a discrete logarithm.
- Alex
[*] Diffie-Hellmann is a method to generate a session key while the bad guy is listening.
There is another major reason why Fortran is still good for scientific calculation: it has vectors. simple as that. C has only pointers. Write a matrix multiplication function and C will create the worst code imaginable because it is so afraid of bad aliasing.
I tuned some Finite Element code. starting at about 50 MFLOPS, I got up to 350 MFLOPS (on a 500MHz 21164) by tuning the C code. gcc went up to about 150 MFLOPS. With Fortran you don't need that tuning.
And now tell me how many scientific applications don't need some kind of vectors...
There is one part of the review which doesn't make much sense
That said, I think there is one area of theory that this book should have spent more time on: NP completeness. NP-complete problems are solvable, but are believed to be inherently hard: no efficient algorithm has been discovered to solve them. For programmers, the important thing is first to recognize that an NP-complete problem has been encountered, and that it cannot be solved exactly except in small instances.
A big part of this is simply wrong. Problems are NP-complete if it is proven that there is no algorithm which solves it in polynomial time. What he describes is NP-hard. His basic requirement, finding out if a problem is NP-hard needs some literature research. To recognize an NP-complete problem one can read about it if it is known. If no literature is found, showing that the problem is NP-complete will take skills on highly advanced levels.
RSA crypto is a good examples: It relies on factorization being NP which has not been proven. It uses so calld strong primes to avoid polynomial factorization algorithms.
I think my dozen dual Alphas that'll arrive tomorrow are far sexier:-)
Seriously, you can't distinguish yourself with yet another Wintel desktop machine. Those might be cool the day they come out, but who wants to shell out the $$ if you can buy a box with the same specs at Aldi* two weeks later. Or any other box that does your work equally well immediately.
IMHO SillyGraphics should stick to what they were good at and cater to graphics professionals
*Aldi is a German general retail chain which about twice yearly sells a shipload of el cheapo PCs in a single day.
Look at other tools that are used to break the law:
Tools to break into houses and guns. They can be developed legally and they can be sold legally (possibly with restrictions). Why should software be different?
You can hardly draw a line between software that *can* be used for illegal purposes (almost anything) and software that is built to break into others computers. Look at Back Orifice. First a crackers tool, now a remote administration toolkit. It is much easier to see that automatic guns can only be used for evil purposes (killing people), yet their development and production is normally legal.
There is a link from the newsticker page to another with the complete article here
The last paragraph is interesting:
With the Brochure "Linux in small and medium Businesses:, the BMWi also wants to promote the Open-Source-OS as an alternative to Windows and as a platform for commercial use. In the Brochure, leaders of those businesses shall be told the technological basics of Linux. The BMWi has won the Linux Distributor LinuxLand.
The Open-Source-Project GNU Privacy Guard (GPG), coordinated by the Programmer Werner Koch from Düsseldorf, will get a financial injection of DM 250k from the Federal Ministery of Economy and Technology (BMWi). More Measures and Money should follow next year. The federal government wants to open the potential of Open Source for security and hopes for a signal effect.
The second big focus is the help for Open-Source-Projects, where the BMWi hopes for more Transparency and Reliability, mainly in the area of security. According to Ulrich Sandl, responsible for "Dialogs with social groups and IT-security", the main question is how the transparency of security processes can be improved: "Mainly for medium-sized companies, it is nearly impossible to determine the value of an encryption product". (Translator's comment: value == nil if for US Export...)
A major part is the help for GPG. "With the concept of GPG, a tool could be made which is freely available as 'public domain'-software (verb.) for all kinds of users - including government, and commercial and private users." says Hubertus Soquat, IT-security expert of the BMWi. The announced monetary injection should mainly help to craft a comfortable UI for GPG and to make adaptions for different OSes and mailclients.
(Hmm, I wonder if that ministery was named after a brand of car:-)
Get an UP2000-based box for that install race. They are not only way cool machines with two of those new Alphas @ 667 MHz, but we also had two SuSE guys over, trying to figure out how to install... And look at the faces of all those bringing their Intel-only distros:-)
Slashdot Mirror
Euler said:
For any number m,
x^{\Phi(m)} mod m == 1
where \Phi(m) is the number of n<m for which gcd(n,m) == 1
If m has the prime factors p_1,p_2...p_k, then \Phi(m) equals the product of the (factors minus one), \prod_i (p_i-1)
RSA uses that property. I construct a m = p*q, where I know the prime numbers p and q. These are very hard to find out for you. I therefore know that \Phi(m) = (p-1)(q-1). I give you m and e, you give me y=x^e (mod m), I calculate d, such that (d*e) mod \Phi(m) = 1 and do
y^d = x^(d*e) = x^1 = x (mod m).
That probably wasn't really for Dummies... ;-)
- Alex
PS Can you tell I'm doing LaTeX lately?
RSA would never use a prime number so small as 2 or 3.
That is just plain wrong. You can freely multiply your modulo with 2^n to conveniently align it for easier modulo-multiplication (E.g. w/ Barrett's algorithm). The number you need to know to decrypt is the product of all (prime factors - 1) so multiplying by two changes nothing. (Not even the space of originial data where encryption is bijective)
- Alex
- Alex
[*] Diffie-Hellmann is a method to generate a session key while the bad guy is listening.
Take any number x not divisible by two or three.
x mod 6 cannot be 0 or 2 or 4 (divisible by 2) or 3. It must be 1 or 5. Regardless of how many prime numbers make up x. QED
This has of course nothing to do with RSA. You fail to show how you make the factorization of N anything less than a O(sqrt(N)) problem
- Alex
There is another major reason why Fortran is still good for scientific calculation: it has vectors. simple as that. C has only pointers. Write a matrix multiplication function and C will create the worst code imaginable because it is so afraid of bad aliasing.
I tuned some Finite Element code. starting at about 50 MFLOPS, I got up to 350 MFLOPS (on a 500MHz 21164) by tuning the C code. gcc went up to about 150 MFLOPS. With Fortran you don't need that tuning.
And now tell me how many scientific applications don't need some kind of vectors...
- Alex
There is one part of the review which doesn't make much sense
That said, I think there is one area of theory that this book should have spent more time on: NP completeness. NP-complete problems are solvable, but are believed to be inherently hard: no efficient algorithm has been discovered to solve them. For programmers, the important thing is first to recognize that an NP-complete problem has been encountered, and that it cannot be solved exactly except in small instances.
A big part of this is simply wrong. Problems are NP-complete if it is proven that there is no algorithm which solves it in polynomial time. What he describes is NP-hard. His basic requirement, finding out if a problem is NP-hard needs some literature research. To recognize an NP-complete problem one can read about it if it is known. If no literature is found, showing that the problem is NP-complete will take skills on highly advanced levels.
RSA crypto is a good examples: It relies on factorization being NP which has not been proven. It uses so calld strong primes to avoid polynomial factorization algorithms.
I think my dozen dual Alphas that'll arrive tomorrow are far sexier :-)
Seriously, you can't distinguish yourself with yet another Wintel desktop machine. Those might be cool the day they come out, but who wants to shell out the $$ if you can buy a box with the same specs at Aldi* two weeks later. Or any other box that does your work equally well immediately.
IMHO SillyGraphics should stick to what they were good at and cater to graphics professionals
*Aldi is a German general retail chain which about twice yearly sells a shipload of el cheapo PCs in a single day.
Look at other tools that are used to break the law:
Tools to break into houses and guns. They can be developed legally and they can be sold legally (possibly with restrictions). Why should software be different?
You can hardly draw a line between software that *can* be used for illegal purposes (almost anything) and software that is built to break into others computers. Look at Back Orifice. First a crackers tool, now a remote administration toolkit. It is much easier to see that automatic guns can only be used for evil purposes (killing people), yet their development and production is normally legal.
- Alex
There is a link from the newsticker page to another with the complete article here
The last paragraph is interesting:
With the Brochure "Linux in small and medium Businesses:, the BMWi also wants to promote the Open-Source-OS as an alternative to Windows and as a platform for commercial use. In the Brochure, leaders of those businesses shall be told the technological basics of Linux. The BMWi has won the Linux Distributor LinuxLand.The Open-Source-Project GNU Privacy Guard (GPG), coordinated by the Programmer Werner Koch from Düsseldorf, will get a financial injection of DM 250k from the Federal Ministery of Economy and Technology (BMWi). More Measures and Money should follow next year. The federal government wants to open the potential of Open Source for security and hopes for a signal effect.
The second big focus is the help for Open-Source-Projects, where the BMWi hopes for more Transparency and Reliability, mainly in the area of security. According to Ulrich Sandl, responsible for "Dialogs with social groups and IT-security", the main question is how the transparency of security processes can be improved: "Mainly for medium-sized companies, it is nearly impossible to determine the value of an encryption product". (Translator's comment: value == nil if for US Export...)
A major part is the help for GPG. "With the concept of GPG, a tool could be made which is freely available as 'public domain'-software (verb.) for all kinds of users - including government, and commercial and private users." says Hubertus Soquat, IT-security expert of the BMWi. The announced monetary injection should mainly help to craft a comfortable UI for GPG and to make adaptions for different OSes and mailclients.
(Hmm, I wonder if that ministery was named after a brand of car :-)
Get an UP2000-based box for that install race. They are not only way cool machines with two of those new Alphas @ 667 MHz, but we also had two SuSE guys over, trying to figure out how to install... And look at the faces of all those bringing their Intel-only distros :-)