summaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorrsiddharth <s@ricketyspace.net>2017-08-26 16:53:07 +0000
committerrsiddharth <s@ricketyspace.net>2017-08-26 16:53:07 +0000
commit43093fc92209563110cb24d7968a9af9ad96632c (patch)
tree82f11c5c21f5266866356b75e36c528cf204396b /net
parentf800c009ac81eaef87dced7ec9e35f8444a3fb7a (diff)
net: Add (net ricketyspace sicp one twentyeight).
* net/ricketyspace/sicp/one/twentyeight.scm: New file.
Diffstat (limited to 'net')
-rw-r--r--net/ricketyspace/sicp/one/twentyeight.scm34
1 files changed, 34 insertions, 0 deletions
diff --git a/net/ricketyspace/sicp/one/twentyeight.scm b/net/ricketyspace/sicp/one/twentyeight.scm
new file mode 100644
index 0000000..bad63a0
--- /dev/null
+++ b/net/ricketyspace/sicp/one/twentyeight.scm
@@ -0,0 +1,34 @@
+;;;; Under Creative Commons Attribution-ShareAlike 4.0
+;;;; International. See
+;;;; <https://creativecommons.org/licenses/by-sa/4.0/>.
+
+(define-module (net ricketyspace sicp one twentyeight)
+ #:use-module (srfi srfi-1)
+ #:export (miller-rabin-test prime?))
+
+(define (sqmod x m)
+ "Return x^2 if `x^2 mod m` is not equal to `1 mod m`
+and x != m - 1 and x != 1; 0 otherwise."
+ (let ((square (* x x)))
+ (cond ((and (= (remainder square m) 1) ; 1 mod m = 1
+ (not (= x (1- m)))
+ (not (= x 1)))
+ 0)
+ (else square))))
+
+(define (expmod base exp m)
+ (cond ((= exp 0) 1)
+ ((even? exp)
+ (remainder (sqmod (expmod base (/ exp 2) m) m)
+ m))
+ (else
+ (remainder (* base (expmod base (- exp 1) m))
+ m))))
+
+(define (miller-rabin-test n)
+ (define (pass? a)
+ (= (expmod a (1- n) n) 1))
+ (fold (lambda (a p) (and (pass? a) p)) #t (iota (1- n) 1)))
+
+(define (prime? n)
+ (if (miller-rabin-test n) #t #f))