Next: , Previous: Bit-Twiddling, Up: Mathematical Packages

5.2 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 m

For odd positive integer m, returns an object suitable for passing as the first argument to modular: procedures, directing them to return a symmetric modular number, ie. an n such that

          (<= (quotient m -2) n (quotient m 2)
— Function: modular:characteristic 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 (modular:characteristic 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:

Integers mod modulus. The result is between 0 and modulus.
The arguments are treated as integers. An integer is returned.

Otherwise, if modulus is a value returned by (symmetric:modulus radix), then the arguments and result are treated as members of the integers modulo radix, but with symmetric representation; i.e.

     (<= (quotient radix 2) n (quotient (- -1 radix) 2)

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 n2

Returns an integer n such that 1 = (n * n2) mod modulus. If n2 has no inverse mod modulus an error is signaled.

— Function: modular:negate modulus n2

Returns (−n2) mod modulus.

— Function: modular:+ modulus n2 n3

Returns (n2 + n3) mod modulus.

— Function: modular:- modulus n2 n3

Returns (n2n3) mod modulus.

— Function: modular:* modulus n2 n3

Returns (n2 * n3) mod modulus.

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

— Function: modular:expt modulus n2 n3

Returns (n2 ^ n3) mod modulus.