Skip to content

Latest commit

 

History

History
206 lines (135 loc) · 4.66 KB

算法概论.md

File metadata and controls

206 lines (135 loc) · 4.66 KB

算法：求解问题的步骤

  • 确定的（无歧义）
  • 可行的
  • 有限的（可终止）
  • 有输出
  • 通常有输入

算法设计中的一个重要思想

时间与空间的权衡

选择算法要素

  • 时间复杂度（主导要素）
  • 空间需求
  • 实现的难度

乘法

function multiply(x,y)
--------------------
Input: Two n-bit integers x and y, where y>=0
Outpt: Their product

if y=0: return 0
z= multiply(x,y/2)
if y is even:
  return 2*z
else:
  return x+2*z

除法

function devide(x,y)
--------------------
Input: Two n-bit integers x and y, where y>=1
Outpt: The quotient and remainder of x divided by y

if x=0: return (q,r)=(0,0)
(q,r)=devide(x/2,y)
q=2*q, r=2*r
if x is odd: r=r+1
if r>=y: r=r-y, q=q+1
return (q,r)

模幂运算

function modxp(x,y,N)
--------------------
Input: Two n-bit integers x and N, an integer exponent y
Outpt: x^y mod N

if y=0: return 1
z= modexp(x,y/2,N)
if y is even:
  return z^2 mod N
else:
  return x*z^2 mod N

计算机中基本操作的复杂度

n 表示数的二进制位数

  • 加法：O（n）

  • 减法：O（n）

  • 乘法：O（n^2），还可以更快？

  • 幂运算：O（n^3）

  • 除法：O（n^2）

  • 模加法：O（n）

  • 模减法：O（n）

  • 模乘法：O（n^2）

  • 模幂运算：O（n^3）

  • 模除法：O（n^3），比较复杂

  • 加法器？ 1位半加器由一个异或门（当前位的结果）和一个与门（是否进位）组成； 由2个1位半加器组合为1位全加器； 由N个1位全加器组合成N位全加器； 通过增加门电路优化门延迟；

  • 乘法器？ 简单的由一个加法器和一个移位电路即可组成； 可以将加法器电路展开，并行计算，减少门延迟；

  • 除法？

欧几里得算法

function Euclid(a,b)
--------------------
Input: Two integers a and b with a>= b>= 0
Outpt: gcd(a,b)

if b=0 : return a
return Euclid(b,a mod b)

扩展欧几里得算法

function extended-Euclid(a,b)
--------------------
Input: Two positive integers a and b with a>= b>= 0
Outpt: Integers x,y,d such that d=gcd(a,b) and ax+by=d

if b=0 : return (1,0,a)
(x,y,d) = extended-Euclid(b,a mod b)
return (y,x-a/b*y,d)

注意：这样的 x 与 y 不止一对

模倒数

定义：对于 ax ≡ 1 mod N，则 x 的模倒数为 a

注意：模倒数不存在的充要条件是 a 与 N 的最大公因子大于 1

可使用扩展欧几里得算法可求模倒数（d=1，b=N，左右两边 mod N ）

费马小定理

如果 p 是素数，对于 1<=a<p，满足 a^(p-1) mod p = 1，也可表示为：a^(p-1) ≡ 1 mod p

注意：这不是素数的必要条件

威尔逊定理

当且仅当 p 为素数时：(p-1)! ≡ -1 mod p

注意：这是素数的充要条件

欧拉定理

若 n，a 为正整数，且 n，a 互质，则：a^φ(n)≡1 mod n

φ(n) 表示与 n 互质的所有 x < n 的个数

注意：费马小定理是欧拉定理的一个特例

素数的判断

如果 N 是素数，则 a^(N-1) ≡ 1 mod N 对于所有的 a<N 成立；

如果 N 是合数，则 a^(N-1) ≡ 1 mod N 对于至多一半的 a<N 成立。

卡米克尔数

p 是合数，对于与 p 互质的所有 a < p，均满足费马小定理。

意味着，卡米克尔数是素数判断的一颗“暗雷”。

素数定理

一个长度位 n 位的随机数为素数的概率至少为 1.44/n

素数的选择

（1）随机产生一个 n 位 的数 N

（2）对于该数进行素性测试

（3）如果素性测试通过，输出 N。否则，重复该过程

该算法平均循环 n 次即可找到 1.44 个素数。

随机算法

拉斯维加斯算法：保证计算结果的正确性，但不保证算法的时间效率（大部分情况下的效率都令人满意）

蒙特卡罗算法：保证算法的时间效率，但不保证计算结果的正确性（大部分情况下的正确性都令人满意）

RSA 原理

公钥（e,N），对外广播；

私钥（d,N），不对任何人泄露；

原文 x 加密： y = x^e mod N

密文 y 解密： x = y^d mod N

RSA 过程

（1）选取 n 位的两个素数 p 与 q ，可用素数的选择算法

（2）N = p*q，e 是一个 2n 位的与 (p-1)(q-1)乘积 互质的一个数

（3）计算 d，使得 d*e ≡ 1 mod (p-1)(q-1)，可用扩展欧几里得算法得到

因式分解的时间复杂度

可能你不相信，这是指数级别的时间复杂度！

正是如此，非对称加密的公钥协议才能保证安全。

全域散列？