< Algorithm

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

Where does the new cryptographic algorithm that is supposed to be unbreakable and was developed by a faculty member at M.I.T., I believe, belong here. It works by keys picked up from some random source, like a satellite, that are processed in the encryption but never stored anywhere. The inventor has proved that it is unbreakable with current computational power, and no one contests this apparently. Do you know what I am referring to? RoseParks

Yes, but it isn't really an encryption algorithm itself so much as a novel means of key exchange. Most modern cryptography techniques are like that: everyone has known about one-time pads for a long time, and that they are unbreakable. Modern techniques like RSA and Diffie-Helmann are just ways to safely exchange keys, which can then be used as one-time pads. RSA and DH key exchange protocols can themselves be broken, while professor Rabin's method theoretically cannot be, but it is not yet practical for other reasons.

Thank you. You may remove or do what you want with this. Perhaps other people have read about it and could use your explanation on these pages...maybe a page itself, or somewhere on these pages. RoseParks

Most of the discussion above is pretty confused. Rabin's method isn't theoretically unbreakable, RSA and Diffie-Hellman are essentially never used to exchange one-time pad keys, RSA is not normally thought of as a key-exchange protocol, properly applied RSA may in fact be impossible to break, etc. But I don't have the time to write a section on cryptography just yet. --Kragen

I think it would be a great idea if we came to some sort of standard on writing pseudocode. I've used a sort of hybrid procedural style for the algorithms in Linear search and Binary search but I'm wondering if there's a better standard out there. Can we borrow a style from a textbook like Intro to Algorithms? (is this copyrighted or is style a public domain thing like an idea?). Only a fairly small set of control structures is needed -- something to define functions, if-statements, loops, list access, mathematical operators and probably a few more. Comments? Mark Jeays

I do think we should try to do standard pseudocode. I have no idea what that pseudocode should be however. CLR's style is usually clear, but sometimes I find it confusing (often because I do not parse the A <- B assignment syntax properly). I don't think things like pseudocode style are copyrightable... We should make a pseudocode article that defines whatever we use (in addition to explaning what pseudocode is in general), then link to that from every pseudocode example. In addition, we could include examples in other languages (see bubble sort for example) by putting them in subpages like bubble sort/C++. --BlckKnght

We definitely need code samples for all the algorithms; I think there should be one language (pseudocode or otherwise) on the main page, and implementations in other languages on subpages, as BlckKnght suggested above.

I think some executable language would be far preferable to pseudocode, for the following reasons:

  • it's possible to test executable implementations of algorithms to see if they're buggy
  • executable languages tend to be more rigorous than pseudocode; people writing in pseudocode tend to gloss over relevant details (like whether the range n..m includes n, m, both, or neither --- this is a huge difficulty with, for example, binary search)

My current favorite languages for this are Scheme, C, and Python.

Python is the most readable of the three; it reads like pseudocode itself. It's also the least standardized of the three, the most rapidly changing, and the one with the most "hidden" stuff going on behind the scenes. (arr.append(item) in Python may allocate new space for the array if the space it's in isn't big enough; that really screws with algorithmic complexity analysis.)

C is the most widely-used of the three, probably the one with the most complex and irregular syntax, the most standardized of the three, the least rapidly changing, and the one with the least "hidden" stuff going on behind the scenes. It's also the most verbose and the least readable for people who aren't familiar with the language or one derived from it. (Although, since it is so widely used, almost anyone who knows how to program is familiar with the language or one derived from it.)

Scheme is intermediate between C and Python, in my opinion, except that it is the least widely used.

For now, I'm going to add implementations in Python to the algorithm pages, and when I have time, I'll add implementations in C and Scheme on subpages.

-- Kragen

Kragen, have a look at the pseudocode page, we thrashed out a "standard pseudocode" for Wikipedia a while ago (though feel free to make suggestions/improvements). The trouble with providing actual implementations of algorithms in real languages is that the trees start to get in the way of the forest. This is less of a problem in Python and Scheme, of course. --Robert Merkel