lists.openwall.net  lists / announce owlusers owldev johnusers johndev passwdqcusers yescrypt popa3dusers / osssecurity kernelhardening musl sabotage tlsify passwords / cryptdev xvendor / Bugtraq FullDisclosure linuxkernel linuxnetdev linuxext4 linuxhardening PHC  
Open Source and information security mailing list archives
 

Date: Tue, 11 Feb 2014 12:31:27 0800 From: "Dennis E. Hamilton" <dennis.hamilton@....org> To: <discussions@...swordhashing.net> Subject: RE: [PHC] multiplyhardening (Re: NoelKDF ready for submission) Bill Cox says "It is in volume 2." Right you are. The Art of Computer Programming volume 2 section 4.6.3 (pp.461485!) is all about Evaluation of Powers. This devolves into an extensive treatment about addition chains, which have certain applications to optimization of arithmetic, including some interesting material about x^n mod w). Some of this material seems relevant to folks concerned about speedups that overcome workfactorincreasing devices. The use of multiplications and divisions for powers is a case of additionsubtraction chains and the only mention I spotted is in exercise 4.6.330. There are times when the additionsubtraction chains are shorter than the addition chain and the solution mentions some heavyduty analysis (i.e., by Paul Erdos) and also ties to other material where additionsubtraction chains are workable (although having 1/x available as part of it strikes me as a stretch for integer work, but maybe not for modular arithmetic). These matter when n is a known constant. Otherwise the socalled binary method is what works best. I couldn't find more in any of the Knuth Collected Works papers that I have, and the early paper might be in the Discrete Mathematics volume. I did find this in the ACM Digital Library: Knuth, Donald E. Evaluation of Polynomials by Computer. Communications of the ACM 5, 12 (December 1962), 595599, <http://dl.acm.org/citation.cfm?doid=355580.369074>. The special case of y^n introduces the factor method, which sometimes requires fewer multiplications than the binary method. The Tree method is also introduced. The end of the paper has an editor's note (from Robert W. Bemer) that shows y^31 by binary method (8 multiplications), factor method (7 multiplications), and addsubtract method (6 operations: 5 squarings and one division). I don't know if this is what I saw about this or whether there was a letter from Knuth expanding on the note from Bemer. Tangentially, that Knuth paper received a followup from S. H. Eisman, in July, 1963, about some additional optimization (but not for the special case of y^n). Oddly, I had met all three of the folks involved, though I have only worked directly with Knuth and Bemer. (I have not the skills of either.) BOTTOM LINE: The TAoCP section 4.6.3 is more recent and more definitive. Erdos showed that y^31 is the smallest n for which multiplydivide takes fewer operations. Bemer was commenting on the opportunity for floatingpoint arithmetic. The modulararithmetic case is also meaningful if y^1 mod w is handy. Hmm.  Dennis Original Message From: Bill Cox [mailto:waywardgeek@...il.com] Sent: Tuesday, February 11, 2014 04:54 To: discussions@...swordhashing.net Subject: Re: [PHC] multiplyhardening (Re: NoelKDF ready for submission) On Tue, Feb 11, 2014 at 2:44 AM, Dennis E. Hamilton <dennis.hamilton@....org> wrote: > Many, many years ago, Knuth published a paper about exponentiation by integers. The speedup he got beyond the standard version (working on bits of the exponent and squarings of the base) was in places where divisions were used instead of multiplications into the growing product for the result. > > I would be surprised if this wasn't in volume 2 of The Art of Computer Programming, probably in one or more of the problems. It is in volume 2. I got the full set as a birthday present while in college, and it's one of the few deadtree books I still keep. That's why we knew Knuth would know about the problem. I only remember my own lame contribution to the mathematical work on the problem while we were hacking it for days: the 2X possible speedup and proving that some values of n approach it. That's probably like 30 minutes of work for a decent mathematician. The other geeks went off and practically invented a branch of mathematics based on the problem, with mind boggling theorems I can no longer recall. > I published a Pascal version (without the division speedups) for arbitrary integer exponents in Dr. Dobbs too many years ago. While I was developing it, Knuth and I had a minor disagreement over what 0 to the power 0 should be. (He voted for 1, I resolved it by returning 0/0 (by identity with 0 to the power 11) and letting the arithmetic of the given compiler and platform decide how to handle it.) > > If you like, I'll see if I can track the Knuth paper and/or the TAoCP location. > >  Dennis That would be awesome, but don't go to too much trouble. Bill
Powered by blists  more mailing lists