Re: Modular type (Re: Large numbers)

[Florian Weimer <fw@deneb.enyo.de>]

georg@ii.uib.no (Hans Georg Schaathun) writes:

> If I remember correctly, that is NP-hard; though that does not really
> matter since our numbers are bounded to 32 bits.  I was rather disappointed
> to see that Ada does division completely wrong (it would be better not to
> do it at all).  What is the best way to do division?  A linear search for
> the inverse requires 2*10^9 multiplications, which is about as many as
> required for all the rest of the problem.  Is this really the preferred
> algorithm?

If you want to calculate the inverse of $x \in (\Z/n\Z)^\times$,
you  can use that $x^{\phi(n)}$ equals $1$, so you need only
$O(\log \phi (n))$ operations.  (To calculate $\phi(n)$, you need the
factorization of $n$, which is quite expensive, but needed only once).

IMHO, the Ada way of division is a bit strange, especially for prime
moduli.  OTOH, at least in the binary modulus case, dividing by zero
divisors (e.g. powers of two) is very common, so the Z/nZ approach
fails in this area.  This confusion could have been avoid only if
non-binary moduli were not in included in the language.

> 2) Dynamic modulus.
> Is it in any way possible to choose the modulus for a modular type 
> runtime, e.g. by parameter to the program?

No, there isn't.  The modulus has to be a static expression (which is
a stronger requirement then a compile-time constant).