密码学系列Chapter 1 Exercise 21-30

‍‍

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

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 的【奇偶分类讨论一下就好】

而

所以  模 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向下取整）

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

计算下列 

需要回顾一下定义

a)

参考答案：8【】

b) 

参考答案：5【】

c)  

参考答案：0，3，1，0 【】

‍

‍