> <\body>

This document describes the use and implementation of the modulars within the package. Moduli are implemented in |numerix/modulus.hpp>. An object of type |mmx::modulus> is declared as follows: <\cpp-code> modulus\C,V\ p; is an implementation variant. The default variant, named |mmx::modulus_naive>, is implemented in |numerix/modulus_naive.hpp> and supports a type with an Euclidean division. More variants are described below. Modulars are implemented in |numerix/modular.hpp>. An object of type |mmx::modular> can be used as follows: <\cpp-code> modular\modulus\C, V\, W\ x, y, z; modular\modulus\C, V\, W\::set_modulus (p); x = y * z; The variant is used to define the storage of the modulus. Default storage is |mmx::modular_local> that allows the current modulus to be changed at any time. The default modulus is . For the |mmx::integer> type the default variant is set to |mmx::modulus_integer_naive>, so that modular integers can be used as follows: <\cpp-code> #include\numerix/integer.hpp\ #include\numerix/modular.hpp\ #include\numerix/modulus_integer_naive.hpp\ \; typedef modulus\integer\ M; M p (9973); modular\M\::set_modulus (p); modular\M\ a (1), b (3); c = a * b; cout \\ c \\ "\\n"; If the modulus is known to be fixed at compilation time then the following declaration is preferable for the sake of efficiency: <\cpp-code> fixed_value \int, 3\ w; modulus\integer\ p (w); If the modulus is not intended to be changed and known at compilation time then the variant |mmx::modular_fixed> can be used. \ From now on and represent the quotient and the remainder in the long division of by respectively. Throughout this section denotes a genuine integer C type. We write for the bit-size of , and for a modulus that fits in . The default variant, m\>|mmx::modulus_int_naive>, is defined in |numerix/modular_int.hpp>. Each modular product performs one product and one integer division. The parameter is the maximum bit-size of the modulus allowed by the variant. This parameter can be set to . Best performances are obtained with >. Note that we necessarily have n-1>> if is a signed integer type. By convention the modulus actually means >. In the variant \m\|mmx::modulus_int_preinverse> a suitable inverse of the modulus is pre-computed and stored as an element of type , this yields faster computations when doing several operations with the same modulus. The behavior of the parameter is as in the preceding naive variant. The best performances are attained for when \ n-2>>. Within the implementation of this variant the following auxiliary quantities are needed: <\itemize-dot> a non-negative integer is defined by \ p \ 2>, an integer such that s\r-1>, an integer such that r> and \n>, an integer div p>, that represents the numerical inverse of to precision . By convention we let if is zero. Note that 2>, hence fits in . Let be an integer such that a\p>. The remainder can be obtained as follows: <\enumerate-numeric> Decompose into > and > such that 2+a>, with \2>, and compute q div 2>. From p> it follows that q \ p q / 2\p2>. So q> has size at most , and we have p>.\ Compute . From the definition of we have: <\center> |p> - q \ 1 \0\ a- aq p/2 \ ap/2+a>. It follows that c\p+ap/2+a>. Let /2 + 2/2>. From \2> we deduce that p/2+a\h p>. It thus suffices to substract at most times to obtain . In general we can always take and , so that . For when n>, it is better to take and so that 2>. Finally, for when n> one can take and so that 1>. These settings are summarized in the following table: |n>>|n>>|n>>>|>|>|>|>>|>|>|>|>>|>|>|>|>>>>>> In these three cases remark that the integer q> has size at most . It is clear that the case n> leads to the fastest algorithm since step 3 reduces to one substraction/comparison that can be implemented as min> within type alone. A special attention must be drawn to when , that corresponds to : we must suppose that is indeed computed within an unsigned int type, hence is sufficiently large to ensure =0> and , hence the correctness of the algorithm. Let us now turn to the computation of the numerical inverse of . The strategy presented here consists in performing one long division in followed by one Newton iteration. Let /p> be the numerical inverse of , normalized so that w\1> holds. Let > denote the initial approximation, and > be its Newton iterate =2x-p x/2>. If w-x\2>> for some positive integer > then it is classical that w-x\2>> with =2s-1>. Under the assumption that \n/2>, we can compute a suitable > as the floor part of >w> by the only use of operations within base type . In other words we calculate =2+r-1> div p= 2>x> as follows: <\enumerate-numeric> If s> then > is obtained by means of one division in . Otherwise s>. We decompose into 2>+p>, with \2>>. Note that -1>\p\2>>. Within perform the long division -1>=a p + b>. By multiplying both side of the latter equality by >> we obtain that +r-1>= a p -a p+b2>>. From and , we easily deduce > since >\p> and \2-1>2>/2-1>=2>. The computation of =2+r-1> div p>, that is the floor part of >w>, then continues as follows: <\enumerate-numeric> From the definition of >, one can write: 2>=q2>-p q/2>. We thus compute 2>> and the ceil part of /2> in order to deduce the floor part of 2>>. Note that fits . From the above inequalities it follows that 2>w-c\2>. We thus obtain =2+r-1>-c p> \ 2p. If p> then return =c+1> else return =c>. Finally, is deduced in this way: <\enumerate-numeric> Set > as |)> div 2>, and compute =2+r-1> div p> as just described. Note that s+t--s\2>. If >+1=> then +r> div p> otherwise+r+1> div p>. Let be a modulo integer that is to be involved in several modular products. Then one can compute = 2b div p \ 2> just once and obtain a speed-up within the products by means of the follows algorithm: <\enumerate-numeric> Compute = a\ div 2>. It follows that a b - \ p \ 2p>. Compute p>. If p> then . Return .\ The computation of > can be done as follows from : <\enumerate-numeric> Compute =q b div 2\2>. Note that b/p-2b/2-1\\\2b/p>. Since 2b -\p\g p>, with if n> and otherwise, deduce b div p> from >. interpreter> Modular integers are glued to the interpreter. The usual arithmetic operations are available. <\session|mathemagix|default> <\input> <|input> use "numerix"; <\input> <|input> type_mode? := true; <\unfolded-io> <|unfolded-io> p: Modulus Integer == 7 <|unfolded-io> : > <\unfolded-io> <|unfolded-io> a == 11 mod p <|unfolded-io> : > <\unfolded-io> <|unfolded-io> a ^ 101 <|unfolded-io> : > <\unfolded-io> <|unfolded-io> q == modulus (7 :\ Int) <|unfolded-io> : > <\unfolded-io> <|unfolded-io> (11 mod q) ^ 100 <|unfolded-io> : > <\itemize-dot> On some processor architectures code to manipulate can be larger and slower than corresponding code which deals with . This is particularly true on the Intel x86 processors executing 32 bit code. Every instruction which references a in such code is one byte larger and usually takes extra processor time to execute. Do not use but or for the sake of portability.