82 lines
5.2 KiB
Clojure
82 lines
5.2 KiB
Clojure
(ns test-p.core
|
||
(:require [clojure.math.numeric-tower :as math]))
|
||
|
||
(def WITNESSLOOP "witness")
|
||
(def COMPOSITE "composite")
|
||
|
||
(defn m* [p q m]
|
||
" Computes (p*q) mod m "
|
||
(mod (*' p q) m))
|
||
|
||
(defn power
|
||
"modular exponentiation (i.e. b^e mod m"
|
||
[b e m]
|
||
(loop [b b, e e, x 1]
|
||
(if (zero? e)
|
||
x
|
||
(if (even? e) (recur (m* b b m) (quot e 2) x)
|
||
(recur (m* b b m) (quot e 2) (m* b x m))))))
|
||
|
||
(defn find-d-s [n]
|
||
" write n − 1 as 2s·d with d odd "
|
||
(loop [d (dec n), s 0]
|
||
(if (odd? d)
|
||
[d s]
|
||
(recur (quot d 2) (inc s)))))
|
||
|
||
;; Deterministic Test
|
||
(defn individual-deterministic-test [a d n s]
|
||
" Deterministic Primality Test "
|
||
(let [z (power a d n)]
|
||
(if (= z 1)
|
||
WITNESSLOOP
|
||
(loop [x z, r s]
|
||
(cond
|
||
(= x (dec n)) WITNESSLOOP
|
||
(zero? r) COMPOSITE
|
||
:else (recur (power x 2 n) (dec r)))))))
|
||
|
||
(defn deterministic-test [n]
|
||
" Sequence of Primality Tests "
|
||
(cond
|
||
(some #{n} [0 1 4]) false
|
||
(some #{n} [2 3]) true
|
||
(even? n) false
|
||
:else (let [[d s] (find-d-s n)]
|
||
(cond
|
||
(< n 2047) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 ])
|
||
(< n 1373653) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3])
|
||
(< n 9090191) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [31 73])
|
||
(< n 25326001) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3 5])
|
||
(< n 3215031751) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3 5 7])
|
||
(< n 1122004669633) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 13 23 1662803])
|
||
(< n 2152302898747) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3 5 7 11])
|
||
(< n 2152302898747) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3 5 7 11])
|
||
(< n 3474749660383) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3 5 7 11 13])
|
||
(< n 341550071728321) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3 5 7 11 13 17])
|
||
(< n 3825123056546,413,051) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3 5 7 11 13 17 19 23])
|
||
(< n (math/expt 2 64) ) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3 5 7 11 13 17 19 23 29 31 37])
|
||
(< n 318665857834031151167461) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3 5 7 11 13 17 19 23 29 31 37])
|
||
(< n 3317044064679887385961981) (not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) [2 3 5 7 11 13 17 19 23 29 31 37 41])
|
||
:else (let [k (min (dec n) (int (math/expt (Math/log n) 2)))]
|
||
(not-any? #(= COMPOSITE (individual-deterministic-test % d n s)) (range 2 (inc k))))))))
|
||
|
||
|
||
;; Testing
|
||
(println "Primes beteen 900-1000:")
|
||
(doseq [q (range 900 1000)
|
||
:when (deterministic-test q)]
|
||
(print " " q))
|
||
(println)
|
||
(println "Is Prime?" 4547337172376300111955330758342147474062293202868155909489 (deterministic-test 4547337172376300111955330758342147474062293202868155909489))
|
||
(println "Is Prime?" 4547337172376300111955330758342147474062293202868155909393 (deterministic-test 4547337172376300111955330758342147474062293202868155909393))
|
||
println "Is Prime?" 643808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153
|
||
(deterministic-test 643808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153))
|
||
|
||
(println "Is Prime?" 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153
|
||
(deterministic-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153))
|
||
(println "Is Prime?" 643808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153
|
||
(deterministic-test 643808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153))
|
||
|
||
(println "Is Prime?" 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153
|
||
(deterministic-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153))
|