New mpn_divexact code

[Paul Zimmermann]

> I've put improved mpn_divexact code on the the tidbits page
> (http://swox.com/gmp/development.html).

Great! The new timings are very impressive!

> Determining the optimal inverse size is a tricky problem.  It
> depends on underlying algorithms such as FFT multiplication and
> how the inverse is computed.

> Determining the cutoff point between basecase divexact and the
> sub-quadratic code is another difficult problem.  It is actually
> not a cutoff point, but a cutoff line, as both the dividend size
> and the divisor size comes into play.  (Currently it is suboptimally
> implemented as a point.)

When the quotient size (qn) is smaller than the divisor size (dn),
it suffices to consider dn limbs of the dividend and divisor (either
low or high bits, or dn/2 low bits and dn/2 high bits), thus a cutoff
point is enough.

The only real problem is when qn > dn.

> The next thing to do is implementing Jebelean's bidirectional
> modular inversion algorithm.  That should save a good deal of the
> inversion time.

The tricky thing here is to glue the high and low parts of the quotient,
and ensure the middle bits are correct.

By the way, I was at the ANTS VII conference last week in Berlin.
There were interesting talks about pseudosquares by Sorenson and
Wooding/Williams. This enables to write a rigorous primality test
up to a given bound (currently about 30 digits), with the same cost
of O(log(n)) modular exponentiations for a n-digit number. This might
be something to consider for future revisions of primality testing
functions.

Paul