Post
Topic
Board Archival
Re: delete
by
TheFascistMind
on 03/10/2014, 08:46:58 UTC
You also didn't see the point of complexity theory.

For some 20 years of my life I thought of myself as a theoretical computer scientist.  I plead guilty of having told many students the things you are trying to tell me now: that complexity theory is extremely relevant to computer programming, that O(n log n) is better than O(n^2), that NP is probably more difficult than P, that polynomial is more efficient than exponential, etc. 

But all of that is false; and, moreover, it is trivially false, it follows directly from the definitions.

I stand by what I wrote: neither complexity analysis (P, NP, and all that) nor big-O analysis have anything to say about the hardness of SHA-256.  Those concepts apply only to problems where the input size n is unbounded, they only tell you what happens as n goes to infnity -- and that has no relation to what happens for any specific finite n.

I could go on, but I need some sleep.  Will continue tomorrow.  But, anyway, I stress that this issue has no impact whatsoever on your work, on the security of SHA256, or any actual application.  It just takes away one argument that some people may have thought they had.  Fortunately the robustness of SHA256 was not proved with theory, but with many years of experimental tests. 

You are conflating the hardness of discovering a lower complexity class with the categorization of the a priori known complexity class.

I stated to you upthread that for finite n = 1000, the difference between O(nk) and O(n log n) was molasses and zippy for the objects window of a million times downloaded application which I created.