【SICP练习】22 练习1.28

2015/09/08 21:50
阅读数 23


练习1.28

这道题主要分为三个部分:

1、非平凡平方根,并添加到expmod函数中

2、类似于fermat-test的过程

3、通过已知的素数和非素数来检验

下面我们首先来写出能够在遇到非平凡平方根的时候报错的函数,在这个函数中:当x不等于1x不等于(n-1),并且x的平方对n取余等于1,这三个条件都为真时则可以说遇到了“1取模n的非平凡平方根”。下面是该函数:

(define (not-square-root? x n)

(and (not (= x 1))

    (not (= x (- n 1)))

    (=1 (remainder (square x) n))))

然后我们要将这个函数添加到expmod中,在cond里面添加一项即可:

(define (expmod base exp m)

   (cond ((= exp 0) 1)

         ((not-square-root? base m) 0)

         ((even? exp)

            (remainder (square (expmod base (/ exp 2) m)) m))

     (else (remainder (* base (expmod base (-exp 1) m)) m))))

第一步我们已经完成了,下面来看看第二步。在fermat-test中,已经有了一个try-it函数,但这个函数在这道题里不适用,因此我们来自己写一个产生随机数的函数。这个函数用来生成大于0并且小于n的随机数。

(define (zero-to-n-random x)

      (let((r (random x)))

     (if (not (= r 0))

         r

             (zero-to-n-randomx))))

random并不会参数负数的随机数,也不能用负数作为参数来产生随机数。下面我们来继续完成miller-rabin-prime函数。

(define (miller-rabin-prime? n)

   (let((x (ceiliing (/ n 2))))

       (miller-rabin-test n x)))

(define (miller-rabin-test n x)

   (cond ((= x 0) #t)

         ((= (expmod (zero-to-n-random n) (- n 1) n) 1)

      (miller-rabin-testn (- x 1)))

         (else #f)))

最后还剩下测试的工作了:

(miller-rabin-prime? 1729)

;Value: #f

(miller-rabin-prime? 2821)

;Value: #f

(miller-rabin-prime? 31)

;Value: #t

版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部