average number of calls of REDC

[pbmcl at netscape.net]

"Andreas Vetter" <AVetter at gmx.de> wrote:

>Last one: To reduce big integers, division is used. So for the division: I
>haven't read the Burnikel/Ziegler paper (but I'm going to), but I want to
>know, why you can't get a O(2M(N)) division, where M(N) is the time for NxN
>multiplication, by simply inverting the divisor "q" as in the single limb
>division, getting a expression like 
>0,00 ..(N-1 Zeros)..00THEN_N_SIGNIFICANTBITS 
>and then multiplying the significant bits with the most significant half of
>the divident? I think, with some more (neglegable) work (o.K. in O(M(N)))
>you could get a correct division.
>
>Andreas Vetter

I believe you are describing Barrett's method, which has more efficient (but more complex) variations.

[Shameless plug] A couple of years ago I publihed a paper in Mathematics of Computation which described a variation of Montgomery's method for modular multiplication which does not require bit padding and uses cyclic and negacyclic convolutions. On paper it should be significantly faster than the method you describe, but as far as I know it has never been implemented. If you are interested, contact me directly and I'll send you the pdf file.

Phil McLaughlin 


__________________________________________________________________
Switch to Netscape Internet Service.
As low as $9.95 a month -- Sign up today at http://isp.netscape.com/register

Netscape. Just the Net You Need.

New! Netscape Toolbar for Internet Explorer
Search from anywhere on the Web and block those annoying pop-ups.
Download now at http://channels.netscape.com/ns/search/install.jsp