Re: Modular type (Re: Large numbers)

[georg@ii.uib.no (Hans Georg Schaathun)]

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.)

:-- Hans Georg
-- 
Signature en panne.