1@code{(require 'modular)} 2@ftindex modular 3 4 5@defun extended-euclid n1 n2 6 7Returns a list of 3 integers @code{(d x y)} such that d = gcd(@var{n1}, 8@var{n2}) = @var{n1} * x + @var{n2} * y. 9@end defun 10 11 12@defun symmetric:modulus m 13 14For odd positive integer @var{m}, returns an object suitable for passing 15as the first argument to @code{modular:} procedures, directing them 16to return a symmetric modular number, ie. an @var{n} such that 17@example 18(<= (quotient @var{m} -2) @var{n} (quotient @var{m} 2) 19@end example 20@end defun 21 22 23@defun modular:characteristic modulus 24 25Returns the non-negative integer characteristic of the ring formed when 26@var{modulus} is used with @code{modular:} procedures. 27@end defun 28 29 30@defun modular:normalize modulus n 31 32Returns the integer @code{(modulo @var{n} (modular:characteristic 33@var{modulus}))} in the representation specified by @var{modulus}. 34@end defun 35 36@noindent 37The rest of these functions assume normalized arguments; That is, the 38arguments are constrained by the following table: 39 40@noindent 41For all of these functions, if the first argument (@var{modulus}) is: 42@table @code 43@item positive? 44Integers mod @var{modulus}. The result is between 0 and 45@var{modulus}. 46 47@item zero? 48The arguments are treated as integers. An integer is returned. 49@end table 50 51@noindent 52Otherwise, if @var{modulus} is a value returned by 53@code{(symmetric:modulus @var{radix})}, then the arguments and 54result are treated as members of the integers modulo @var{radix}, 55but with @dfn{symmetric} representation; i.e. 56@cindex symmetric 57@example 58(<= (quotient @var{radix} 2) @var{n} (quotient (- -1 @var{radix}) 2) 59@end example 60 61@noindent 62If all the arguments are fixnums the computation will use only fixnums. 63 64 65@defun modular:invertable? modulus k 66 67Returns @code{#t} if there exists an integer n such that @var{k} * n 68@equiv{} 1 mod @var{modulus}, and @code{#f} otherwise. 69@end defun 70 71 72@defun modular:invert modulus n2 73 74Returns an integer n such that 1 = (n * @var{n2}) mod @var{modulus}. If 75@var{n2} has no inverse mod @var{modulus} an error is signaled. 76@end defun 77 78 79@defun modular:negate modulus n2 80 81Returns (@minus{}@var{n2}) mod @var{modulus}. 82@end defun 83 84 85@defun modular:+ modulus n2 n3 86 87Returns (@var{n2} + @var{n3}) mod @var{modulus}. 88@end defun 89 90 91@defun modular:- modulus n2 n3 92 93Returns (@var{n2} @minus{} @var{n3}) mod @var{modulus}. 94@end defun 95 96 97@defun modular:* modulus n2 n3 98 99Returns (@var{n2} * @var{n3}) mod @var{modulus}. 100 101The Scheme code for @code{modular:*} with negative @var{modulus} is 102not completed for fixnum-only implementations. 103@end defun 104 105 106@defun modular:expt modulus n2 n3 107 108Returns (@var{n2} ^ @var{n3}) mod @var{modulus}. 109@end defun 110 111