文档章节

【SICP练习】22 练习1.28

NoMasp
 NoMasp
发布于 2015/09/08 21:50
字数 448
阅读 0
收藏 0


练习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

本文转载自:http://blog.csdn.net/nomasp/article/details/43601417

NoMasp
粉丝 7
博文 334
码字总数 0
作品 0
镇江
程序员
私信 提问
dSploitzANTI渗透教程之启动zANTI工具

dSploitzANTI渗透教程之启动zANTI工具 启动zANTI工具 【示例1-2】下面将介绍启动zANTI工具的方法。具体操作步骤如下所示: (1)在Android设备的应用程序界面,选择并启动zANTI程序。启动后,...

大学霸
2015/08/04
917
0
java在linux上调用ffmpeg命令行组合图片为视频时无法加入音频!

在window上本地测试时,音频时可以加入视频中的;当上载到Linux上后,居然加不进音频;用putty直接执行又没问题,不知何故?运行时代码: 命令行: ffmpeg/bin/ffmpeg -y -r 1.28 -f image2...

e国阳光
2016/10/15
836
3
关东升的《从零开始学Swift》第2版已经出版

关东升的《从零开始学Swift》第2版已经出版 大家好: 苹果2015WWDC大会发布了Swift2.0,它较之前的版本Swift1.x有很大的变化,所以我即将出版《从零开始学Swift》 《从零开始学Swift》将在《...

tony关东升
2016/02/24
0
0
关于顺序表逆置的编程题,代码出现一些错误,求完整解答。

请看这段程序代码,为什么不能成功编译? 求指点更改,谢谢。求详解过程。 题目: 1. 将顺序表逆置,要求用最少的附加空间。 以下为代码: #include #include #include #define LIST_INIT_S...

好树叶
2014/04/12
784
1
关东升的《从零开始学Swift》3月9日已经上架

大家一直期盼的《从零开始学Swift》于3月9日已经上架,它是关东升老师历时8个月的呕心沥血所编著,全书600多页,此本书基于Swift 2.x,通过大量案例全面介绍苹果平台的应用开发。全书共分5 部...

智捷课堂
2016/03/11
43
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
今天
5
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
今天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
今天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
今天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部