next up previous
Next: Performances Up: Commands Previous: Advanced algebraic operations on

Modular arithmetic on unlimited precision integers

ALG48 provides six commands specifically to perform modular arithmetic on unlimited precision integers. These commands take three arguments (two operands A and B, and a modulus N), except MODINV which takes only two arguments (A and N). Here again the arguments can be given as (integer) real numbers, binary integers, or strings.

If A and N are relatively prime numbers (with A<N), the inverse modulo N of A is the (unique) number C that satisfies

displaymath1896

If no such inverse exists, i.e., if A and N are not relatively prime, then MODINV returns #0h. Similarly, MOD/ returns #0h if its second and third arguments are not relatively prime.


Claude-Nicolas Fiechter (fiechter@cs.pitt.edu), 12 May 1998