zjffun blog

《算法概论》

更新于 写于

算法概论

序言

Fibonacci 数列

多项式时间算法:

js
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

指数时间算法:

js
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 乘法规则)

js
// 类似使用二进制进行乘法(当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));

除法

js
// 类似使用二进制进行除法(当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
js
// 求模的指数运算
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)
js
// 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<pa^(p-1) 模 p=1
js
// 素数测试算法(对于合数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 与发送信息长度一样

js
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