GNU Info

(slib.info)Modular Arithmetic

---

Next: Prime Numbers Prev: Bit-Twiddling Up: Mathematical Packages

---

Enter node , (file) or (file)node

Modular Arithmetic
==================

  `(require 'modular)'

 - Function: extended-euclid n1 n2
     Returns a list of 3 integers `(d x y)' such that d = gcd(N1, N2) =
     N1 * x + N2 * y.

 - Function: symmetric:modulus n
     Returns `(quotient (+ -1 n) -2)' for positive odd integer N.

 - Function: modulus->integer modulus
     Returns the non-negative integer characteristic of the ring formed
     when MODULUS is used with `modular:' procedures.

 - Function: modular:normalize modulus n
     Returns the integer `(modulo N (modulus->integer MODULUS))' in the
     representation specified by MODULUS.

The rest of these functions assume normalized arguments; That is, the
arguments are constrained by the following table:

For all of these functions, if the first argument (MODULUS) is:
`positive?'
     Work as before.  The result is between 0 and MODULUS.

`zero?'
     The arguments are treated as integers.  An integer is returned.

`negative?'
     The arguments and result are treated as members of the integers
     modulo `(+ 1 (* -2 MODULUS))', but with "symmetric"
     representation; i.e. `(<= (- MODULUS) N MODULUS)'.

If all the arguments are fixnums the computation will use only fixnums.

 - Function: modular:invertable? modulus k
     Returns `#t' if there exists an integer n such that K * n == 1 mod
     MODULUS, and `#f' otherwise.

 - Function: modular:invert modulus k2
     Returns an integer n such that 1 = (n * K2) mod MODULUS.  If K2
     has no inverse mod MODULUS an error is signaled.

 - Function: modular:negate modulus k2
     Returns (-K2) mod MODULUS.

 - Function: modular:+ modulus k2 k3
     Returns (K2 + K3) mod MODULUS.

 - Function: modular:- modulus k2 k3
     Returns (K2 - K3) mod MODULUS.

 - Function: modular:* modulus k2 k3
     Returns (K2 * K3) mod MODULUS.

     The Scheme code for `modular:*' with negative MODULUS is not
     completed for fixnum-only implementations.

 - Function: modular:expt modulus k2 k3
     Returns (K2 ^ K3) mod MODULUS.