bipartite modular multiplication

[Paul Zimmermann]

       Hi,

I have found another nice application of the bipartite modular multiplication
from Kaihara and Takagi. In the Karatsuba range, the recursive division costs
2M(n) to get quotient and remainder (or remainder only).

Using the bipartite modular multiplication, one can get the upper half quotient
in 2M(n/2), the lower half quotient in 2M(n/2), and one can use the Karatsuba
trick to compute the middle correction in M(n/2), which gives a total of
5M(n/2) = 1.666M(n) instead of 2M(n).

This can be used for example in modular exponentiation, or in Stage 1 of ECM,
where the cost of going to the half-Montgomery representation is amortized.

Paul