06CS/《算法概论》

  • 更新时间：2020-09-20 05:11
  • 创建时间：2020-09-20 05:11

算法概论

序言

Fibonacci 数列

多项式时间算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var fib_arr = [0, 1];
function fib(n){
  if(n == 0){
    return 0;
  }else if(n == 1){
    return 1;
  }
  for (var i = 0; i < n-2; i++) {
    fib_arr[n+2] = fib_arr[n+1] + fib_arr[n]
  }
  return fib_arr[n]
}
var start = new Date().getTime();
console.log(fib(30));
var end = new Date().getTime();
console.log('运行时间：'+(end-start));
// 运行时间：24

指数时间算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function fib(n){
  if(n == 0){
    return 0;
  }else if(n == 1){
    return 1;
  }else{
    return fib(n-1) + fib(n-2);
  }
}
var start = new Date().getTime();
console.log(fib(30));
var end = new Date().getTime();
console.log('运行时间：'+(end-start));
// 运行时间：50

渐进

  • 上界：Ο
  • 下界：Ω
  • 紧确界：Θ

数字的算法

基础算数

基数和对数

  • b 为基数的 k 位数字最大为 b^k-1
  • b 为基数表示 N 需要 ⌈log(b)(N+1)⌉ 位

乘法（Al Khwarizmi 乘法规则）

1
2
3
4
5
6
7
8
9
10
// 类似使用二进制进行乘法（当y>=0时可用）
function multiply(x, y){
  if(0 == y){
    return 0;
  }
  var z = multiply(x, Math.floor(y/2))
  // z为偶数，z为奇数加到x上
  return y%2 == 0 ? 2*z : x + 2*z;
}
console.log(multiply(11, 13));

除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 类似使用二进制进行除法（当y>=1时可用，q：quotient，r：remainder）
function divide(x, y){
  if(0 == x){
    return [0, 0];
  }
  var z = divide(Math.floor(x/2), y);
  var q = 2 * z[0];
  var r = 2 * z[1];
  if (x%2 == 1) {
    // 被除数为奇数除二余数为1
    r++;
  }
  if (r >= y) {
    // 余数大于除数，余数变为余数减去除数，商+1
    r -= y;
    q++;
  }
  return [q, r];
}
console.log(divide(11, 13));

模运算

  • x 模 N 等于 y 等价于 N 可以整除 x-y，且 0<=y<N
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 求模的指数运算
function modexp(x, y, N){
  if(0 == y){
    return 1;
  }
  var z = modexp(x, Math.floor(y/2), N);
  if (y%2 == 0) {
    return (z * z) % N;
  }else{
    return (x * z * z) % N;
  }
}
console.log(modexp(11, 11, 2));//1
console.log(modexp(10, 11, 2));//0
console.log(modexp(10, 3, 13));//(10^3)%13 = 12

// 求模的除法运算
// 太难，先留着

最大公因数算法

  • Euclid 规则：如果 x，y 是正整数，且有 x>=y，那么 gcd(x, y) = gcd(x mod y, y)
1
2
3
4
5
6
7
8
// Euclid求最大公约数方法（a>=b>=0）
function euclid(a, b){
    if(0 == b) return a;
    return euclid(b, a % b);
}
console.log(euclid(11, 11));//11
console.log(euclid(33, 22));//11
console.log(euclid(97, 79));//1

素性测试

  • 费马小定理：p 为素数，任意对于任意 1<=a<p 有 a^(p-1) 模 p=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 素数测试算法（对于合数N，a的大多数无法通过测试）
function primality(N){
  var a = Math.floor(2 + Math.random() * (N-3));
  if (modexp(a, N - 1, N) == 1) {
    return true;
  }else{
    return false;
  }
}

// 求模的指数运算（y>=1），前面的算法
function modexp(x, y, N){
  if(0 == y){
    return 1;
  }
  var z = modexp(x, Math.floor(y/2), N);
  if (y%2 == 0) {
    return (z * z) % N;
  }else{
    return (x * z * z) % N;
  }
}
console.log(primality(11027));
console.log(primality(11026));

// 素数测试算法（对于合数N，a的大多数无法通过测试）
function primality(N){
  // 降低出错概率到(2^-100)
  for (var i = 0; i < 100; i++) {
    var a = Math.floor(2 + Math.random() * (N-3));
    if (modexp(a, N - 1, N) != 1) {
      return false;
    }
  }
  return true;
}

// 求模的指数运算（y>=1），前面的算法
function modexp(x, y, N){
  if(0 == y){
    return 1;
  }
  var z = modexp(x, Math.floor(y/2), N);
  if (y%2 == 0) {
    return (z * z) % N;
  }else{
    return (x * z * z) % N;
  }
}
console.log(primality(11027));
console.log(primality(11026));

密码学

一次一密乱码本（one-time pad）和 AES

使用密钥 r 进行异或加密解密

  • 加密：er(x) = x ⊕ r
  • 解密：er(er(x)) =(x ⊕ r) ⊕ r = x ⊕ (r ⊕ r) = x

一次一密乱码本

r 与发送信息长度一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const r = "101011100";

function encrypt(x){
  return (parseInt(x, 2) ^ parseInt(r, 2)).toString(2);
}

function unencrypt(x){
  return (parseInt(x, 2) ^ parseInt(r, 2)).toString(2);
}

// test
var msg = "111110000";
var encrypted = encrypt(msg);
console.log(`encrypted: ${encrypted}`);
var unencrypted = unencrypt(encrypted);
console.log(`unencrypted: ${unencrypted}`);

AES

  1. r 通常定为 128 位（也有定为 192 位或 256 位的情况）
  2. 定义一种双向映射机制 er
  3. 信息分成片段，每个片段用 er 加密

RAS

生成密钥：

  1. 找大整数 p,q（素数测试算法）
  2. 根据 N=pq，求 N（乘法）
  3. 找任意与 (p-1)(q-1) 互素的数 e（Euclid 算法）
  4. 根据 ed≡(1 mod (p-1)(q-1))，求 d（拓展 Euclid 算法）

此时公钥为 (N,e)，私钥为 (N,d)

加密解密

  1. 加密：y=x^e mod N
  2. 解密：x=y^d mod N