Timeline for What is special about $2^{32}/\phi$ in cryptography?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 22, 2011 at 10:04 | comment | added | Sadeq Dousti | @Steven: I wrote a very simple computer program to find the n for various C's, including $C_{\sqrt{3}}$. The program is in C#. You can download it from here: ifile.it/8yiqd5j. Note that $C_{\sqrt 3}$ is not relatively prime to $2^{32}$, but $C_{3}$ is! | |
| Apr 22, 2011 at 10:03 | comment | added | Sadeq Dousti | I was (and am) quite interested in this answer, so I continued investigating it. For $C_{\sqrt 5} = \lfloor {2^{32}/\sqrt 5}\rfloor = 1920767766$, the smallest n for which $|(nC_{\sqrt 5})\mod {2^{32}}| \leq 2^{16}$ is 39603, which is quite larger than that of $C_\varphi$. The corresponding n's for $C_{\sqrt 2}$ and $C_{\sqrt 3}$ are 19601 and 18817, which are quite large (yet not as large as that of $C_\varphi$). Even worse: For $C_3 = \lfloor {2^{32}/ 3} \rfloor = 1431655765$, such an n does not exist! | |
| Apr 22, 2011 at 10:02 | comment | added | Sadeq Dousti | Below, I rewrite one of my comments above which had several typos. I deleted the original comment to reduce confusion... | |
| Apr 22, 2011 at 7:40 | comment | added | user4772 | @Steven: I find your claim that "those of the golden ratio approach that even distribution faster than any other number" very interesting. What is this phenomenon called? Where can I find a proof? | |
| Apr 22, 2011 at 2:34 | comment | added | Steven Stadnicki | Sadeq: the result about $C_{\sqrt{5}}$ doesn't surprise me much; the statements about $\varphi$ essentially hold true for all of its 'cousins' $a+b\sqrt{5}$ since the terminal portion of their continued fraction is the same. Are you sure about your result for $C_{\sqrt{3}}$? Since that's relatively prime to $2^{32}$, there should be some $n$ for which $nC_{\sqrt{3}}$ is even congruent to $1\mod 2^{32}$! | |
| Apr 21, 2011 at 22:00 | comment | added | Steven Stadnicki | Unfortunately, I don't; - the only thing that comes to mind is that they may be chosen for approximate linear independence, since the functions $\sin(nx)$ are linearly independent over $x$ - but I don't know any reason to believe that this particular set of values should lead to relatively large values for $a_i$ in any linear relation $\Sigma a_i k[i] = 0$. | |
| Apr 21, 2011 at 21:33 | comment | added | Sadeq Dousti |
Thanks for great description. It was really great! Do you have any comments on k[i], as defined in MD5? (See my answer above.)
|
|
| Apr 21, 2011 at 21:00 | comment | added | Suresh Venkat | that's a very neat property of the golden ratio | |
| Apr 21, 2011 at 20:54 | history | edited | Steven Stadnicki | CC BY-SA 3.0 |
added 845 characters in body
|
| Apr 21, 2011 at 20:10 | comment | added | Steven Stadnicki | $\pi$'s close approximation by 355/113, for instance, means that $113\pi$ will be much closer to an integer than it 'should be' and this shows up as a clustering of the fractional parts of its values; $\{(n+113)\pi\}$ will be exceptionally close to $\{n\pi\}$. The golden ratio has no such good approximations, though; all of its approximations are 'maximally far' from it. ( en.wikipedia.org/wiki/… covers this) | |
| Apr 21, 2011 at 20:03 | comment | added | Steven Stadnicki | Sadeq: 'mod 1' refers to the fractional part of the multiples - in this case these would be [.62, .24, .85, .47, .09, .71, .33, .94, .56, .18]. Equidistribution in the limit means that any subinterval [a, b] of [0, 1] contains the expected proportion (b-a) of these values; while it turns out that the fractional parts of the multiples of any irrational number are evenly distributed on [0, 1], those of the golden ratio approach that even distribution faster than any other number; they don't 'clump' on the unit interval. | |
| Apr 21, 2011 at 19:44 | comment | added | Sadeq Dousti | Interesting! I just didn't understand the last sentence quite well: What do you mean by "uniformly distributed mod 1"? For instance, the first 10 terms of {nφ} are [1.62, 3.24, 4.85, 6.47, 8.09, 9.71, 11.33, 12.94, 14.56, 16.18] (rounded to 2 decimal place). | |
| Apr 21, 2011 at 19:12 | history | edited | Steven Stadnicki | CC BY-SA 3.0 |
added 43 characters in body
|
| Apr 21, 2011 at 19:02 | history | answered | Steven Stadnicki | CC BY-SA 3.0 |