modular-arithmetic

Check-in [088758e922]
Login

Check-in [088758e922]

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:imported v1.0.0
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk | v1.0.0
Files: files | file ages | folders
SHA3-256: 088758e92211480bb165995daf175bcd01e2315473d49eb89efd2cacc557c782
User & Date: murphy 2018-08-18 15:56:32.071
Context
2018-08-18
15:57
imported v1.0.1 check-in: 529ec5356a user: murphy tags: trunk, v1.0.1
15:56
imported v1.0.0 check-in: 088758e922 user: murphy tags: trunk, v1.0.0
15:52
initial empty check-in check-in: 4ab785d87f user: murphy tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Added modular-arithmetic.meta.


















>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
((egg "modular-arithmetic.egg")
 (files "modular-arithmetic.setup" "modular-arithmetic.meta" "modular-arithmetic.scm" "tests/run.scm")
 (needs numbers matchable)
 (test-depends test)
 (category math)
 (synopsis "Modular Arithmetic on Finite Fields")
 (author "Thomas Chust")
 (doc-from-wiki)
 (license "BSD"))
Added modular-arithmetic.scm.








































































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
(require-library
 srfi-1
 numbers matchable)

(module modular-arithmetic
  (xgcd mod+ mod- mod* mod/ modexpt with-modulus)
  (import
   (except scheme
	   + - * / = > < >= <=
	   number->string string->number
	   exp log sin cos tan asin acos atan expt sqrt
	   quotient modulo remainder numerator denominator
	   abs max min gcd lcm
	   positive? negative? odd? even? zero? exact? inexact?
	   floor ceiling truncate round
	   inexact->exact exact->inexact
	   number? complex? real? rational? integer?
	   real-part imag-part magnitude)
   (except chicken
	   add1 sub1 signum
	   bitwise-and bitwise-ior bitwise-xor bitwise-not
	   arithmetic-shift)
   srfi-1
   numbers)
  (import-for-syntax
   scheme chicken matchable)

;; Extended GCD
(define (xgcd a b)
  (let-values ([(q m) (quotient&modulo a b)])
    (if (zero? m)
	(values 0 1)
	(let-values ([(x y) (xgcd b m)])
	  (values y (- x (* y q)))))))

;; Modular addition generator
(define ((mod+ modulus) . ns)
  (fold (lambda (n a) (modulo (+ a n) modulus)) 0 ns))

;; Modular subtraction and negation generator
(define (mod- modulus)
  (case-lambda
    [(a)
     (modulo (- a) modulus)]
    [(a . ns)
     (fold (lambda (n a) (modulo (- a n) modulus)) a ns)]))

;; Modular multiplication generator
(define ((mod* modulus) . ns)
  (fold (lambda (n a) (modulo (* a n) modulus)) 1 ns))

;; Modular division and inversion generator
(define (mod/ modulus)
  (define (inverse a)
    (if (= a 1)
	1
	(let-values ([(1/a n) (xgcd a modulus)])
	  (if (zero? n)
	      (error 'mod/ "operand and modulus are not coprime" a modulus)
	      1/a))))
  (case-lambda
    [(a)
     (modulo (inverse a) modulus)]
    [(a . ns)
     (fold (lambda (n a) (modulo (* a (inverse n)) modulus)) a ns)]))

;; Modular exponentiation generator
(define (modexpt modulus)
  (let ([* (mod* modulus)]
        [/ (mod/ modulus)])
    (lambda (base exponent)
      (let loop ([a 1]
                 [base (if (negative? exponent) (/ base) base)]
                 [exponent (abs exponent)])
        (if (positive? exponent)
	    (loop (if (zero? (bitwise-and exponent 1)) a (* a base))
                  (* base base)
                  (arithmetic-shift exponent -1))
            a)))))

;; Syntax to overload +, add1, -, sub1, *, / and expt with modular versions
(define-syntax with-modulus
  (er-macro-transformer
   (lambda (stx rename id=)
     (match stx
       [(with-modulus modulus body ...)
        (let ([~let (rename 'let)]
	      [~letrec (rename 'letrec)]
	      [~modulus (rename 'modulus)])
          `(,~let ([,~modulus ,modulus])
             (,~letrec ([+ (,(rename 'mod+) ,~modulus)]
			[add1 (lambda (n) (+ n 1))]
			[- (,(rename 'mod-) ,~modulus)]
			[sub1 (lambda (n) (- n 1))]
			[* (,(rename 'mod*) ,~modulus)]
			[/ (,(rename 'mod/) ,~modulus)]
			[expt (,(rename 'modexpt) ,~modulus)])
               ,@body)))]))))

)
Added modular-arithmetic.setup.


>
1
(standard-extension 'modular-arithmetic '1.0.0)
Added tests/run.scm.






































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
(require-extension
 test modular-arithmetic)

(test-group "Modular Arithmetic"

  (test "Extended GCD"
    '(3 -2)
    (receive (xgcd 15 21)))

  (test "Addition"
    3
    (with-modulus 7
      (+ 1 2 3 4)))

  (test "Subtraction"
    2
    (with-modulus 5
      (- 4 7)))

  (test "Multiplication"
    50
    (with-modulus 66
      (* 4 8 16)))

  (test "Division"
    1
    (with-modulus #xE95E4A5F737059DC60DFC7AD95B3D8139515620F
      ((lambda (x) (/ x x)) 8977423876425786243783246)))

  (test "Exponentiation"
    8
    (with-modulus 13
      (expt 5 3)))

  )