Wikipedia:Reference desk/Archives/Mathematics/2007 September 1

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 1

Why do we trust our hash functions?

How do we know that cryptographic hash functions such as SHA-512 are good (i.e., that it's difficult to invert them or find collisions)? Are there any proofs, or at least motivations? —Bromskloss 11:57, 1 September 2007 (UTC)

There are no proofs; any such proof would imply P≠NP. As scary as it may sound, the main reason people trust these hash functions is that no one has managed to break them yet. Of course, new hashes aren't designed in a vacuum; the designers look at what worked (i.e. resisted attack) in previous designs, and reuse those ideas. But that's the best assurance you get. -- BenRG 14:12, 1 September 2007 (UTC)

The search space is finite, so finding a message producing a given digest has complexity O(1). It would seem hard to prove that that is difficult, perhaps even more difficult than proving P≠NP. :)  --Lambiam 16:49, 1 September 2007 (UTC)

O(1)? The longer the length of the answer to the hash function, the harder it is to decode. For a given hash function, what you say is correct, perhaps, but when computers get good enough to beat a certain hash function, it is easy to increase the complexity of the function. That's like saying, it takes O(1) time to factor a specific 1000-digit number -- true, but that's not what we're measuring; we want to figure out a method for factoring all numbers, based on their size. Gscshoyru 17:08, 1 September 2007 (UTC)

I'm assuming a hash function h is broken if it is feasible, given a digest d, to find a message m such that h(m) = d. The search space is about as large as the output space. The argument that we will move on to SHA-1024, ..., SHA-1048576, ..., as necessary, is not particularly reassuring to people using SHA-512 now. "Trust our hash function, because we're working to replace it by something better." Even assuming the availability of a generic n-length hash function whose inversion has been shown to be NP-hard (which is not the case for SHA-512), the argument cannot possibly work unless the lengths of the digests keep being increased, as well as the lengths of the messages, since the message size also limits the search space. On the other hand, it is theoretically conceivable that someome shows that the complexity of inverting an n-byte digest is Ω(n⁶⁴), which does not settle P≠NP but still means practical unbreakability with conventional computers.  --Lambiam 19:27, 1 September 2007 (UTC)

Being NP-complete is surely a motivation I can accept (I suspected this was the case). Do all cryptographic hash functions rely on this? Even in the case of a polynomial time (even O(1)), I imagine that one could perhaps establish a lower bound on the time it would take to crack it. —Bromskloss 18:00, 1 September 2007 (UTC)

Being NP-complete doesn't mean that solving it takes longer than polynomial time -- that is yet to be proven, as it is that P=NP problem. NP-complete means that all problems in NP can be "simplified" to that problem in polynomial time, and a correct answer can be checked in polynomial time. And I'm not even sure that solving hash functions is NP-complete, but I am sure that it is in NP. And yes, the "unbreakability" of hash functions is based on the assumption that anything in NP takes a "long time" to solve. Gscshoyru 18:17, 1 September 2007 (UTC)

Careful there. P is contained in NP, so it is certainly not assumed that "anything in NP [is hard]". What may be assumed is that anything NP-complete is hard. -- Meni Rosenfeld (talk) 18:50, 1 September 2007 (UTC)

Ok, right. The sentence should say "anything in NP, that is most likely not in P takes a "long time" to solve. And I'm saying it that way because I don't know if they are NP-complete or not, and there are problems that are in NP, that we don't know if they are NP-complete, and that are still hard because they are probably not in P. And do you know if they are NP-complete or not, by the way? Gscshoyru 19:06, 1 September 2007 (UTC)

Unfortunately, I do not know too much about Hashes. -- Meni Rosenfeld (talk) 19:09, 1 September 2007 (UTC)

"As scary as it may sound, the main reason people trust these hash functions is that no one has managed to break them yet. " ... and decided, what the hey, to tell the world at large. ... for free. 81.182.100.100 23:54, 5 September 2007 (UTC)

A Very Peculiar Practice

If any mathematicians remember this series, the room-mate of Peter Davison's character was a mathematician who often used to burst into his room to continue writing equations on the blackboards around Davison's room after running out of space elsewhere in the flat. The question is was the things he was writing genuine mathematical equations or just complete nonsense - a bunch of mathematical symbols being randomly scrawled? Exxolon 17:11, 1 September 2007 (UTC)

Do you have screenshots? —Bromskloss 18:01, 1 September 2007 (UTC)

Infinitesimals

I've never studied these (or any other extension of the real numbers), but I've been wondering - is there an "infinitesimal" number x, such that for a closed interal [a,b] (with a and b both real), the interval [a,(b-x)] is equivalent to [a,b)? Given the (wooly) definition of infinitesimals I've encountered (being non-zero, but less than any finite number, right?), it seems like only an infinitesimal could bring about this equivalence. If not, does there exist a non-zero x such that this is true, or is it just not possible? Thanks, Icthyos 17:59, 1 September 2007 (UTC)

I don't know what you mean by 'is equivalent to'. In the surreal numbers, with x = omega^(-1) or something, [a, (b-x)] contains exactly the same reals as [a, b), but they're not the same set: the second doesn't contain b-x/2, for example. Algebraist 18:12, 1 September 2007 (UTC)

I was afraid my language might not be technical enough - I wasn't sure how to word the question, without any knowledge of the surreal numbers. I was really wondering if the two sets were equal (and should have said so!), but I see they're not now. I've been pondering this for a while now, and the "b-x/2" problem came up in my own enquiry - that's why I was asking about number systems I might not have heard of. I suppose any x for which (b-x/2) could be ignored wouldn't be particularly helpful, or consistent. I'll just have to settle for the two sets containing the same reals as each other! Thanks very much, Icthyos 18:30, 1 September 2007 (UTC)

So what you're asking, is, does there exist an x such that [a, b) = [a, (b-x)], right? I don't understand infinitesimals well enough to tell you whether or not x being an infinitesimal would work in this instance, but there is no normal non-zero x for which that is true. Gscshoyru 18:37, 1 September 2007 (UTC)

I think part of the problem here is discerning the meaning of [a,b). You see to get infinitesimals you need to supplement the real field to get hyperreals or surreal numbers. Either way you are now dealing with a different fields of numbers and interpreting [a,b) changes in that case. If by [a,b) you want the set of real numbers under the standard use of [a,b) then yes, an infinitesimal x will provide [a,(b-x)] having all the reals contained in [a,b), but of course what does [a,(b-x)] mean? the value (b-x) will only exist in the extended hyperreals or surreals, and thus your closed interval notation must necessarily be referring to that, which makes the whole thing a little bit of "apples and oranges". Your other option is to try the infinitesimals of smooth infinitesimal analysis which don't require augmenting the reals, but instead ask you to drop the law of excluded middle. In that case the notations are all refering to the same thing, but you can't draw the result you want since you can't actually pinpoint the required infinitesimal (indeed, to actually claim that there did exist a nilsquare infinitesimal would result in a contradiction, strangely enough). -- Leland McInnes 19:49, 1 September 2007 (UTC)

Your link is to "surreal numbers" the the type of thing you seem to be describing is a limit specifically the limit (of the function or whatever) as x tends to/becomes zero; such as found in calculus - perhaps I am over simplifying what you ask?83.100.249.228 20:14, 1 September 2007 (UTC)

Further on you seem to be asking is there a case when fn(b) = fn (b-x) and of course the answer is in general no, the things are equivalent only when x=0 - you described a case where x is non zero.. However you mention "x is less than any finite number" - this number is of course zero.. Again maybe I'm oversimplyfying your question.83.100.249.228 20:18, 1 September 2007 (UTC)

I'm not sure what 83.100 is trying to say, but I'll skip that and go back to the text of the question: "Given the (wooly) definition of infinitesimals I've encountered (being non-zero, but less than any finite number, right?)" The definition, if phrased right, is not wooly at all. The Archimedean property puts it on a somewhat firmer foundation. Take the natural numbers as the most basic of the finite numbers: the numbers you get by adding 1 to itself any finite number of times. Now, to define infinite positive numbers, we define numbers greater than any natural number. To define infinitecimal positive numbers, we define numbers greater than zero such that any natural number multiple of them is less than 1. In the rational numbers and the real numbers there's no such thing, so to get it we'd have to extend the field a bit. That's what the "less than any finite number" thing is trying to say, a bit clumsily - that it would have to be less than any number that shows up in an Archimedean field, if it's reasonable to make that comparison. Black Carrot 21:49, 3 September 2007 (UTC)

Age Problem

Yes, this is homework, but I only need a push in the right direction: In 1988, Sue was the sum of the digits of her birth year. When was she born?

I have come up with an equation, y=39 - 11/2 x, where x is the tens digit of her birth year, and y is the ones digit. Unfortunately, to find a system and solve the problem, I need another equation, so for now, I'm stuck. What should I try? BTW, guess and check is not an option. Thanks for your help. -- Sturgeonman 18:13, 1 September 2007 (UTC)

You don't need another equation to solve this equation - you only need to use the fact that x and y are integers from 0 to 9. Does this help? -- Meni Rosenfeld (talk) 18:43, 1 September 2007 (UTC)

I had the two ranges, but this probably counts as guess and check. Using that method however, the answer is 1966; it's just an issue of backsolving. -- Sturgeonman 18:49, 1 September 2007 (UTC)

I've got it! I made a table of values for the 10 possible integer values of x, and the only answer that results in an integer value of y is x=6. Its not guess and check- it's just expressing the data in a different manner, a table. Thanks, meni, for the idea. -- Sturgeonman 18:59, 1 September 2007 (UTC)

You don't even need a table. Because 11x = 2(39 − y), you can see that x is even (odd × odd = odd). Using 0 ≤ y ≤ 9, and x = 2(39 − y)/11, you have that 60/11 ≤ x ≤ 78/11. The only even integer in that range is 6. So x = 6, and y = 39 − (11/2)×6 = 6.  --Lambiam 19:04, 1 September 2007 (UTC)

[Edit conflict] Here's how I would solve it. We have ${\frac {11}{2}}x=39-y$, which is an integer, so ${\frac {11}{2}}x$ is an integer. This means that x must be divisble by 2, so $x=2m$. We can then write $11m=39-y$. Since $0\leq y\leq 9$ we have $30\leq 11m\leq 39$, so $2{\frac {8}{11}}\leq m\leq 3{\frac {6}{11}}$. Since m is an integer we have m = 3, so x = 6 and y = 6. This spares the need for a table, a "guess and check" or whatever. -- Meni Rosenfeld (talk) 19:06, 1 September 2007 (UTC)

I'm curious as to where you obtained your original equation "y=39 - 11/2 x". Sue is somewhere between 10 and 28 years old (1+9+x+y : 1+9+0+0 to 1+9+9+9) The 'simple' way to solve this is to try all years from 1988-28=1960 thru 1988-10=1978. There are only 18 to do. -- SGBailey 07:59, 2 September 2007 (UTC)

$10x+y+(1+9+x+y)=88\Rightarrow 11x+2y=78\Rightarrow y=39-{\frac {11x}{2}}$

Gandalf61 09:48, 2 September 2007 (UTC)