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:53 PST Path: nntp.stanford.edu!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsxfer.eecs.umich.edu!news.bu.edu!inmet!not-for-mail From: Tucker Taft Newsgroups: comp.lang.ada Subject: Re: Modular type (Re: Large numbers) Date: Thu, 15 Mar 2001 11:24:40 -0500 Organization: AverStar (formerly Intermetrics) Burlington, MA USA Message-ID: <3AB0ECC8.3680464C@averstar.com> References: <3AA95244.94BAD60D@averstar.com> <87itlbnvrh.fsf@deneb.enyo.de> NNTP-Posting-Host: nebula.burl.averstar.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: inmet2.burl.averstar.com 984673481 14158 141.199.8.77 (15 Mar 2001 16:24:41 GMT) X-Complaints-To: usenet@inmet2.burl.averstar.com NNTP-Posting-Date: 15 Mar 2001 16:24:41 GMT X-Mailer: Mozilla 4.75 [en] (X11; U; SunOS 5.7 sun4u) X-Accept-Language: en Xref: nntp.stanford.edu comp.lang.ada:91484 Date: 2001-03-15T16:24:41+00:00 List-Id: Hans Georg Schaathun wrote: > > On 15 Mar 2001 11:58:58 +0100, Florian Weimer > 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)