搜搜做题作业网算法导论上31章数论算法的证明题
来源：学生作业帮 编辑：搜搜做题作业网作业帮 分类：数学作业 时间：2024/06/01 14:22:43
算法导论上31章数论算法的证明题
31.7-2 证明：如果Alice的公开指数e等于3,并且对方获得Alice的秘密指数d,0
31.7-2 证明：如果Alice的公开指数e等于3,并且对方获得Alice的秘密指数d,0
由ed=1(mod φ(n)),可设 ed = k*φ(n)+1,k∈Z
由e = 3,0
再问： 该不是同学吧？ 这题是我这次作业，我写的方法跟你一样。算k有什么用？ 看了个开头，我还以为还有很精妙的方法。 另外手算开平方是O(d²)时间的 怎么证明？？？ 一次除法的复杂度就已经是O(d^2)了 能证明 常数次除法 可以求出结果？
再答： 只需说明： 1. φ(n)的取值只有C种（C是与n,d,e无关的常数） 2. 已知n和φ(n)，则p,q有初等解析解 3. 每种基本运算都能够在关于n的位数的多项式时间内完成 关于手算开方，就是利用 (10a+b)² - 100a² = 20ab + b² 开方的每一步中：M是上一步的余数，a是到上一步为止已求出的部分结果。 1. 在M后面添上后2位， 2. 试商：取b=0..9，计算20ab + b²，得到满足20ab + b²
由e = 3,0
再问： 该不是同学吧？ 这题是我这次作业，我写的方法跟你一样。算k有什么用？ 看了个开头，我还以为还有很精妙的方法。 另外手算开平方是O(d²)时间的 怎么证明？？？ 一次除法的复杂度就已经是O(d^2)了 能证明 常数次除法 可以求出结果？
再答： 只需说明： 1. φ(n)的取值只有C种（C是与n,d,e无关的常数） 2. 已知n和φ(n)，则p,q有初等解析解 3. 每种基本运算都能够在关于n的位数的多项式时间内完成 关于手算开方，就是利用 (10a+b)² - 100a² = 20ab + b² 开方的每一步中：M是上一步的余数，a是到上一步为止已求出的部分结果。 1. 在M后面添上后2位， 2. 试商：取b=0..9，计算20ab + b²，得到满足20ab + b²