[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Provably "Secure" Crypto (was: IPG Algorithm Broken!)
- To: [email protected]
- Subject: Provably "Secure" Crypto (was: IPG Algorithm Broken!)
- From: [email protected] (John Anonymous MacDonald)
- Date: Tue, 26 Nov 1996 09:27:40 -0800
- Comments: There is no way to determine the originator of this message.If you wish to be blocked from receiving all anonymous mail, sendyour request to the <[email protected]> mailing list.The operator of this particular remailer can be reached at<[email protected]>.
- Sender: [email protected]
At 12:28 PM 11/25/1996, Dana W. Albrecht wrote:
>For an (again, non-cryptographic) example of a proof of the second sort
>--- that is, that "any algorithm that solves a given problem requires a
>minimal running time" --- consider the proof that the "minimal" number
>of key comparisons in the worst case required to sort a random list of
>elements for which only an ordering relationship is known is O(nlog(n)).
>See Knuth, Volume 3, section 5.3. For a simpler example, a standard
>"binary" search which requires O(log(n)) comparisons to find a given
>element in the worst case is provably the optimal algorithm for this
>task.
What is the longest running provably optimal algorithm? Would it be
possible to construct a crypto system from it?
A relatively weak crypto system which is provably no weaker than it
appeared would have its uses.
>Comments, anyone?
Congratulations on your excellent post.
diGriz