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:

positive?

Integers mod modulus. The result is between 0 and modulus.

zero?

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 (n2 - n3) 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.