From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,69bb03cc695b330a
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2001-03-17 01:38:52 PST
Path: 
 nntp.stanford.edu!newsfeed.stanford.edu!news.tele.dk!212.43.194.69!fr.clara.net!heighliner.fr.clara.net!newsfeed.hanau.net!newsfeed01.sul.t-online.de!t-online.de!newsfeed.easynews.net!newsfeed2.easynews.net!easynews.net!news.cid.net!news.enyo.de!news1.enyo.de!not-for-mail
From: Florian Weimer <fw@deneb.enyo.de>
Newsgroups: comp.lang.ada
Subject: Re: Modular type (Re: Large numbers)
Date: 15 Mar 2001 11:58:58 +0100
Organization: Enyo's not your organization
Message-ID: <87itlbnvrh.fsf@deneb.enyo.de>
References: <slrn9ai9uk.iv9.georg@apal.ii.uib.no>
 <3AA95244.94BAD60D@averstar.com> <slrn9b0vik.243.georg@apal.ii.uib.no>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Xref: nntp.stanford.edu comp.lang.ada:91474
Date: 2001-03-15T11:58:58+01:00
List-Id: <comp.lang.ada>

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