fork(1) download

copy

(import (normal extension)) ;;for random-integer
 
(define (prime? str)
  (rabin-miller? (string->number str)))
 
;;ラビンミラーテスト
;;テスト対象のｎを n^k * q に分解する。
(define (rm1 n)
  (define (iter k q)
    (if (not (= (modulo q 2) 0))
        (list k q)
        (iter (+ k 1) (/ q 2))))
  (iter 0 (- n 1)))
 
;;ラビンミラーテスト条件１
;;合成数なら#t 素数なら#f
(define (rm2 a q n)
  (not (= (gaussmod a q n) 1)))
 
;;ラビンミラーテスト条件２
;;合成数なら#t 素数なら#f
(define (rm3 a k q n)
  (define (iter i)
    (cond ((>= i k) #t)
          ((= (gaussmod a (* (expt 2 i) q) n) -1) #f)
          (else (iter (+ i 1)))))
  (iter 0))
 
 
;;ラビンミラーテスト
;;nについて底aで条件１，２をテスト
;;合成数なら#t 素数なら#f
(define (rm4 n a)
  (let* ((ls (rm1 n))
         (k (car ls))
         (q (cadr ls)))
    (and (rm2 a q n)
         (rm3 a k q n))))
 
;;ラビンミラーテスト
;;関数本体
;;底を2～n-1まで乱数で発生させ10回試行する。
;;素数なら#t 合成数なら#f
;;擬素数である確率は 0.25^10 およそ0.000095% 
(define (rabin-miller? n)
  (define (iter t)
    (cond ((< t 1) #f)
          ((rm4 n (+ (random-integer (min (- n 2) 10000)) 1)) #t)
          (else (iter (- t 1)))))
  (if (= n 2)
      #t
      (not (iter 10))))
 
;;繰り返し二乗法によるmod計算で結果を法ｍとした場合 -m/2～m/2 で表す。
(define (gaussmod a k m)
  (let ((k1 (expmod a k m)))
    (cond ((and (> k1 0) (> k1 (/ m 2)) (< k1 m)) (- k1 m))
          ((and (< k1 0) (< k1 (- (/ m 2))) (> k1 (- m))) (+ k1 m))
          (else k1))))
 
(define (expmod a n m)
  (cond ((= 0 n) 1)
        ((even? n)
         (remainder (square (expmod a (/ n 2) m)) m))
        (else
         (remainder (* a (expmod a (- n 1) m)) m))))
 
norm> (prime? "123786712687686876213123127987987979879")
#f

Main.java:1: error: class, interface, or enum expected
(import (normal extension)) ;;for random-integer
^
Main.java:1: error: <identifier> expected
(import (normal extension)) ;;for random-integer
       ^
Main.java:1: error: ';' expected
(import (normal extension)) ;;for random-integer
               ^
Main.java:1: error: class, interface, or enum expected
(import (normal extension)) ;;for random-integer
                              ^
Main.java:6: error: class, interface, or enum expected
;;?????????
  ^
Main.java:7: error: class, interface, or enum expected
;;???????? n^k * q ??????
  ^
Main.java:7: error: illegal character: '\u3002'
;;???????? n^k * q ??????
                        ^
Main.java:15: error: class, interface, or enum expected
;;????????????
  ^
Main.java:16: error: illegal character: '#'
;;?????#t ????#f
       ^
Main.java:16: error: illegal character: '#'
;;?????#t ????#f
              ^
Main.java:20: error: class, interface, or enum expected
;;????????????
  ^
Main.java:21: error: illegal character: '#'
;;?????#t ????#f
       ^
Main.java:21: error: illegal character: '#'
;;?????#t ????#f
              ^
Main.java:24: error: illegal character: '#'
    (cond ((>= i k) #t)
                    ^
Main.java:25: error: illegal character: '#'
          ((= (gaussmod a (* (expt 2 i) q) n) -1) #f)
                                                  ^
Main.java:30: error: class, interface, or enum expected
;;?????????
  ^
Main.java:31: error: illegal character: '\uff0c'
;;n?????a??????????
             ^
Main.java:31: error: illegal character: '\uff12'
;;n?????a??????????
              ^
Main.java:32: error: illegal character: '#'
;;?????#t ????#f
       ^
Main.java:32: error: illegal character: '#'
;;?????#t ????#f
              ^
Main.java:40: error: class, interface, or enum expected
;;?????????
  ^
Main.java:41: error: class, interface, or enum expected
;;????
  ^
Main.java:42: error: illegal character: '\uff5e'
;;??2?n-1?????????10??????
     ^
Main.java:42: error: illegal character: '\u3002'
;;??2?n-1?????????10??????
                         ^
Main.java:43: error: illegal character: '#'
;;????#t ?????#f
      ^
Main.java:43: error: illegal character: '#'
;;????#t ?????#f
              ^
Main.java:44: error: class, interface, or enum expected
;;????????? 0.25^10 ???0.000095% 
  ^
Main.java:47: error: illegal character: '#'
    (cond ((< t 1) #f)
                   ^
Main.java:48: error: illegal character: '#'
          ((rm4 n (+ (random-integer (min (- n 2) 10000)) 1)) #t)
                                                              ^
Main.java:51: error: illegal character: '#'
      #t
      ^
Main.java:54: error: class, interface, or enum expected
;;??????????mod????????????? -m/2?m/2 ????
  ^
Main.java:54: error: illegal character: '\uff5e'
;;??????????mod????????????? -m/2?m/2 ????
                                 ^
Main.java:54: error: illegal character: '\u3002'
;;??????????mod????????????? -m/2?m/2 ????
                                         ^
Main.java:69: error: illegal character: '#'
#f
^
34 errors

Standard output is empty