Shannon Entropy

Codes from: http://rosettacode.org/wiki/Entropy

(function(shannon) {
  // Create a dictionary of character frequencies and iterate over it.
  function process(s, evaluator) {
    var h = Object.create(null), k;
    s.split('').forEach(function(c) {
      h[c] && h[c]++ || (h[c] = 1); });
    if (evaluator) for (k in h) evaluator(k, h[k]);
    return h;
  };
  // Measure the entropy of a string in bits per symbol.
  shannon.entropy = function(s) {
    var sum = 0,len = s.length;
    process(s, function(k, f) {
      var p = f/len;
      sum -= p * Math.log(p) / Math.log(2);
    });
    return sum;
  };
})(window.shannon = window.shannon || {});

// Log the Shannon entropy of a string.
function logEntropy(s) {
  console.log('Entropy of "' + s + '" in bits per symbol:', shannon.entropy(s));
}

logEntropy('1223334444');
logEntropy('0');
logEntropy('01');
logEntropy('0123');
logEntropy('01234567');
logEntropy('0123456789abcdef');

Output:

Entropy of "1223334444" in bits per symbol: 1.8464393446710154
Entropy of "0" in bits per symbol: 0
Entropy of "01" in bits per symbol: 1
Entropy of "0123" in bits per symbol: 2
Entropy of "01234567" in bits per symbol: 3
Entropy of "0123456789abcdef" in bits per symbol: 4

Birthday attack

生日问题是指,如果一个房间里有23个或23个以上的人,那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级(30人)中,存在两人生日相同的可能性更高。对于60或者更多的人,这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论,从这个数学事实与一般直觉相抵触的意义上,它才称得上是一个悖论。大多数人会认为,23人中有2人生日相同的概率应该远远小于50%。计算与此相关的概率被称为生日问题,在这个问题之后的数学理论已被用于设计著名的密码攻击方法:生日攻击。

Euler Theorem

$$$\gcd(a, n) = 1$$$

$$$a^{\phi(n)} ≡ 1 (\bmod n)$$$

$$$p$$$为质数时(费马小定理):

$$$\phi(p) = p - 1$$$

所以

$$$a^{p-1} ≡ 1 (\bmod p)$$$

Euler Totient Function

任意给定正整数$$$n$$$,小于等于$$$n$$$的正整数之中,有多少个与$$$n$$$构成互质关系,计算这个值的方法就叫做欧拉函数,以$$$\phi(n)$$$表示。在1到8之中,与8形成互质关系的是1、3、5、7,所以 $$$\phi(8) = 4$$$

一、$$$n=1$$$
如果$$$n=1$$$,则 $$$\phi(1) = 1$$$ 。因为1与任何数(包括自身)都构成互质关系。

二、$$$n$$$是质数
如果n是质数,则 $$$\phi(n)=n-1$$$ 。因为质数与小于它的每一个数,都构成互质关系。比如5与1、2、3、4都构成互质关系。

三、$$$n$$$是质数的某一个次方,即$$$n = p^k$$$ ($$$p$$$为质数,$$$k$$$为大于等于1的整数)
$$$\phi(p^{k}) = p^{k} - p^{(k-1)}$$$

比如 $$$\phi(8) = \phi(2^{3}) =2^{3} - 2^{2} = 8 - 4 = 4$$$

$$$\phi(p^{k}) = p^{k} - p^{(k-1)} = p^{k} * (1 - \frac{1}{p})$$$

四、$$$n$$$可以分解成两个互质的整数之积,即$$$n = p_{1} \times{} p_{2}$$$
$$$\phi(n) = \phi(p_{1}\times{}p_{2}) = \phi(p_{1})\times{}\phi(p_{2})$$$

比如 $$$\phi(56)=\phi(8\times{}7)=\phi(8)\times{}\phi(7)=4\times{}6=24$$$

五、任意一个大于1的正整数,都可以写成一系列质数的积
$$$n = p_{1}^{k_{1}} \times{} p_{2}^{k_{2}} \times{} \cdot\cdot\cdot \times{} p_{n}^{k_{n}}$$$

$$$\phi(n) = \phi(p_{1}^{k_{1}}) \times{} \phi(p_{2}^{k_{2}}) \times{} \cdot\cdot\cdot \times{} \phi(p_{n}^{k_{n}})$$$

$$$\phi(n) = p_{1}^{k_{1}} \times{} p_{2}^{k_{2}} \times{} \cdot\cdot\cdot \times{} p_{n}^{k_{n}} \times{} (1 - \frac{1}{p_{1}}) \times{} (1 - \frac{1}{p_{2}}) \times{} \cdot\cdot\cdot \times{} (1 - \frac{1}{p_{n}})$$$

$$$\phi(n) = n \times{} (1 - \frac{1}{p_{1}}) \times{} (1 - \frac{1}{p_{2}}) \times{} \cdot\cdot\cdot \times{} (1 - \frac{1}{p_{n}})$$$

$$$\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)$$$

比如 $$$\phi(1323) = \phi(3^{2} \times 7^{2}) = 1323 \times (1 - \frac{1}{3}) \times (1 - \frac{1}{7}) = 756$$$

public static BigInteger euler(BigInteger x) {
    BigInteger res = x;
    for (BigInteger i = BigInteger.valueOf(2); i.compareTo(x.divide(i)) <= 0; i = i.add(BigInteger.ONE)) {
        if (x.mod(i).equals(BigInteger.ZERO)) {
            res = res.divide(i).multiply(i.subtract(BigInteger.ONE));
            while (x.mod(i).equals(BigInteger.ZERO)) {
                x = x.divide(i);
            }
        }
    }
    if (x.compareTo(BigInteger.ONE) > 0) {
        res = res.divide(x).multiply(x.subtract(BigInteger.ONE));
    }
    return res;
}

Greatest Common Divisor

$$$\gcd(x, y) = \gcd(x \bmod y, y)$$$

Modular Multiplicative Inverse

$$$\gcd(a, n) = 1$$$

$$$a\times{}b \equiv 1 (\bmod n)$$$

$$$a^{-1} \equiv b (\bmod n)$$$

$$$a^{-1} \equiv 1 \times{} a^{-1} \equiv a^{\phi(n)} \times{} a^{-1} \equiv a^{\phi(n) - 1} (\bmod n)$$$

Prime

质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个因数的数)。大于1的自然数若不是素数,则称之为合数。

public static boolean isPrime(BigInteger n) {
    BigInteger TWO = BigInteger.valueOf(2);
    BigInteger n_div_2 = n.divide(TWO);
    for (BigInteger i = TWO; i.compareTo(n_div_2) <= 0; i = i.add(BigInteger.ONE)) {
        if (n.mod(i).equals(BigInteger.ZERO)) {
            return false;
        }
    }
    return true;
}