From: Wei Dai <weidai@eskimo.com>
Date: Thu, 7 Sep 95 16:47:38 PDT
To: Ray Cromwell <rjc@clark.net>
Subject: Re: fast modular reduction
In-Reply-To: <199509070811.EAA07559@clark.net>
Message-ID: <Pine.SUN.3.91.950907131638.6760C-100000@eskimo.com>
MIME-Version: 1.0
Content-Type: text/plain


>  Anyway, I played around with the algorithm a little, and it's neat
> and easy to implement, but the speed increase is not worth
> the patent hassle (assuming there is a speed increase, I saw none)
> 
>   The algorithm is still basically O(n^2) if used in a modexp
> routine. It requires n^2 multiplications and additions. Whereas,
> a typical Karatsuba multiplication using a high precision
> reciprocal will only use 2*n^1.5 multiplications and 5*n^1.5/8
> additions. (for n=64 which is a 2048-bit number being reduced, 
> it's about 1/5 the multiplications, but 5 times the additions)

I agree with you that the patent hassle is probably not worth the speed 
increase.  If I came up with the algorithm by myself and on my own time, 
I certainly would not have filed a patent for it, but that wasn't the 
case.  I also agree that the patent system should be abolished, but there 
is nothing I can do about that either.

The speed increase does exist over Montgomery's modular reduction 
because it uses n*n multiplications and 1 division compared to n*(n+1) 
multiplications, and the pre- and post-calculations are much simpler.

Division using Karatsuba multiplication does seem to have a better 
asymptote, but is probably slower for most practical lengths.  Both 
Lenstra's LIP and Lacy's CryptLib use Montgomery for modular reduction.

The numbers you give are a bit off.  Assuming a 32-bit machine,
n=64 implies a 2048-bit modulus, and a 4096-bit number to be reduced. 
Also, Karatsuba should use 1/3 (2*64^1.58 / 64^2) the multiplications
rather than 1/5. 

Wei Dai