Re: Modular type (Re: Large numbers)

[Tucker Taft <stt@averstar.com>]

Hans Georg Schaathun wrote:
> 
> On 15 Mar 2001 11:58:58 +0100, Florian Weimer
>   <fw@deneb.enyo.de> wrote:
> : 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.
> 
> Ooops, sure.  Sorry, I should have thought of that by myself.  Thx.
> 
> :                                (To calculate $\phi(n)$, you need the
> : factorization of $n$, which is quite expensive, but needed only once).
> 
> Usually rather simple for prime numbers though, and I only want
> prime moduli :-)
> 
> : > 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).
> 
> I wonder why this is necessary.  Is there an efficiency gain from using
> built-in modular type compared to defining ones own modular type
> with a run-time parameter as modulus?  (Assuming prime modulus.)

If you want to deal with a dynamic modulus, you could use mod 2**32 types
and the explicit "mod" operator (for moduli < 2**16).  If your compiler
supports mod 2**64 types, then you could handle dynamic moduli up to
2**32, of course.

In retrospect, it does seem that the language could have allowed
a run-time modulus.  I suppose we were reluctant to define a new
kind of scalar type whose base range was not static.  The base range
is static for all others.

As far as division, it is clearly not the normal modular division,
but that is not particularly well defined for non-prime moduli,
so it wasn't really an option.

> :-- Hans Georg
> --
> Signature en panne.

-- 
-Tucker Taft   stt@avercom.net   http://www.averstar.com/~stt/
Chief Technology Officer, AverCom Corporation (A Titan Company) 
Burlington, MA  USA (AverCom was formerly the Commercial Division of AverStar:
http://www.averstar.com/services/ebusiness_applications.html)