lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  PHC 
Open Source and information security mailing list archives
 
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 11 Feb 2014 07:53:38 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] multiply-hardening (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 speed-up 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 dead-tree 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 1-1) 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