Next: , Previous: , Up: Mathematical Packages   [Contents][Index]

### 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.

Next: , Previous: , Up: Mathematical Packages   [Contents][Index]