密码学系列Chapter 1 Exercise 21-30

admin 2022年4月1日22:07:34CTF专场评论25 views1804字阅读6分0秒阅读模式

‍‍

        下面是第一章练习题第二十一到三十题的参考答案,部分是笔者自证,所以读者若是发现有纰漏之处,还望指正(可私信公众号)。

Exercise 21-30

1.21

证明如果  为素数,当且仅当 ,其中  是欧拉函数。
首先我们设  为素数,设  是 1 和  之间任意整数,再设 
所以有 ,但因为  是一个素数,所以  or 
与此同时呢又因为 ,而  ,所以 ,所以 
所以我们这里证明了 对于任意  都满足 ,所以 
接下来我们设 
这意味着每一个整数,都满足 
现在我们假设 ,那么因为,所以
但是根据  这一事实我们知道 ,所以 
所以这证明了唯一整除  的只有 ,所以  是一个素数。

1.22

设 
a) 如果  是一个奇数,那么在 1 和 m - 1 之间,哪个数与  同余。
因为  是一个奇数,所以  肯定是一个整数,且显然 
b) 更一般的,假设 ,那么在 1 和 m - 1 之间,哪个数与  同余
根据  的假设, 是一个整数,所以我们有 ,这和我们想要的已经很接近了,两边同时乘以 ,我们有 
但是  是一个负数,所以我们可以给他加一点 的倍数而不影响其在模下的剩余的值,即有整数 , 所以我们有 ,所以 

1.23

设整数 ,奇数 ,证明  不可能为一个 perfect square【就是开2次根不是整数】 (提示:如果这个数是一个perfect square,那么他在模4下的剩余是多少)
我们知道任何一个数的平方模 4 都是余 0 或者 1 的【奇偶分类讨论一下就好】

密码学系列Chapter 1 Exercise 21-30

所以  模 4 余 2 或者 3,所以肯定不会是一个perfect square。

1.24

a) 找到整数  同时满足同余式  (提示,第一个同余式的解都可以表示为 ,然后把这个式子代入第二个同余式解出 y,然后计算出 x)
b) 找到整数  同时满足同余式 
c) 找到整数  同时满足同余式 
d) 证明,如果 ,那么同余式对 ,对于任意的  都有解。并给出例子说明条件  是必须的。
我们知道第一个同余式的解可以表示为  为任意整数。
把他带入到第二个同余式我们有 
所以问题转化为我们想找大一个值  满足 
也就是说我们需要找到  满足 
由于题目已经给出 ,所以我们可以找到  满足 
两边同时乘以  有 
所以我们有 。即
To Summarize,我们首先解决 ,然后我们有 
两种表达式揭示了 
这个题目其实是第二章会提到的中国剩余定理的特殊形式。

1.25

设正整数 ,(N 不必是素数)下述算法是1.3.2一节中介绍的 “square-and-Multiply” 算法的“low-storage”的变体,返回 。(第四步中的符号是对x向下取整)
密码学系列Chapter 1 Exercise 21-30

1.26

用1.3.2一节中介绍的 “square-and-Multiply” 算法或者上述更效率的版本,计算下面的幂次数
a) 
参考答案:
b) 
参考答案:
c) 
参考答案:

1.27

考虑同余式 
a) 证明这个同余式有解当且仅当 
若同余式有解,
即等式  成立, 为某一整数,即可以表达为 
设 
因为 
所以 
可以知道, 整除所有形如  的数,所以如果 ,那么原方程也无解。
b) 证明如果该同余式有解,那么就有  个不同的解
(提示,使用拓展欧几里得算法 定理 1.11)
设 
若  是满足这个等式的解,那么所有解的形式可以表示为 (练习 1.11 d)
所以模  下共有  个不同的解 ()

1.28

设  是素数,且 
证明 N 可以被某个不在上面序列的素数给分解。利用该事实可以推出一定存在无穷多个素数(该证明在欧几里得的 Elements 中提到)
我们设  为某个可以整除  的素数,(因为 ,我们知道它肯定会被某个素数整除)
如果  等于某个  ,那么我们就会有 ,因为 同时整除  和 
但这个同余式显然不成立,所以  不等于任何一个 
然后我们假设仅存在有限个素数,那意味着我们可以把他们全部记下来,写为
但是根据前一部分的证明,我们可以创造一个新的素数  而不在这个列表中,这和我们基于的假设相矛盾,因此素数有无限多个。

1.29

不基于每个整数都可以被唯一分解为素数 这一事实,证明如果 ,并且  ,那么有,(提示,根据我们可以找到  的解的事实)
根据拓展欧几里得算我们可以解决 
两边同时乘以  我们有 
已知 ,所以存在一个整数  满足 
替换一下前一个式子我们有 
因此 
所以

1.30

计算下列 
需要回顾一下定义
密码学系列Chapter 1 Exercise 21-30
a)
参考答案:8【
b) 
参考答案:5【
c)  
参考答案:0,3,1,0 【

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年4月1日22:07:34
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  密码学系列Chapter 1 Exercise 21-30 http://cn-sec.com/archives/861779.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: