将文本文件读入数组-C语言实现

要求:使用 C 语言将文本文件的每一行读入为数组的一个元素,返回一个 char ** 指针。

由于行长度和文本文件行数均未知,相当于二维 char 数组的两维长度都未定义。由于 getline 函数可以自动扩充 char 数组长度,我最初的想法是使用 getline 得到每行,然后每次对 char ** 进行 realloc,直到读完整个文件。

但是这种做法并不好,首先 getline 是 glibc 的扩展,而不是 C 语言的标准函数,使用除 gcc 以外的编译器是不一定能编译通过的;其次,每次对 char ** 指针进行 realloc 显得代码很 ugly。可以使用 fgets 替代 getline,但是就要自己来控制一维 char 数组的长度。

后来想想,换了一种思路,首先将整个文件读入内存,然后根据 '\n' 的个数来计算文件的行数,作为二维数组的长度,然后将所有的 '\n' 替换成 '\0',并将每一行的指针赋给二维 char 数组,代码如下:

char ** text_2_array(const char *filename)
{
  char *p, **array;
  int lines;
  if(filename == NULL) return NULL;

  FILE *fp = fopen(filename, "r");
  if(fp == NULL) return NULL;

  /* Get file size. */
  fseek(fp, 0L, SEEK_END);
  long int f_size = ftell(fp);
  fseek(fp, 0L, SEEK_SET);

  /* Allocate space for file content. */
  char *buf = (char *) calloc(f_size, sizeof(char));
  if(buf == NULL) return NULL;

  fread(buf, sizeof(char), f_size, fp);
  fclose(fp);

  /* Get number of lines. */
  for(p=strchr(buf, '\n'), lines=1; p!=NULL; p=strchr(p, '\n'), lines++) {
    if(*p == '\n') p++;
  }

  /* Allocate space for array; split file buffer to lines by change '\n' to
     '\0'. */
  array = (char **) calloc(lines+1, sizeof(char*));
  array[0] = buf;
  for(p=strchr(buf, '\n'), lines=1; p!=NULL; p=strchr(p, '\n')) {
    if(*p == '\n') *p++ = '\0';
    if(p != NULL) array[lines++] = p;
  }
  /* Add a terminate NULL pointer. */
  array[lines] = NULL;
  return array;
}

其实读文本文件入数组这个功能在很多语言中是很简单的操作,比如 PHP 的 file 函数,或者 Bash 的 (`cat filename`),都可以直接实现这个功能。但是对 C 这种更低级的语言来说,貌似就没那么简单了。我想要了解的是,除了我上面提到的两种思路,有没有更简单或者直接的方法来解决这个问题?比如一些我不熟悉的函数,或者一些 trick。

统计二进制中 1 的个数

这是一道《编程之美-微软技术面试心得》中的题目,问题描述如下:

对于一个字节(8bit)的变量,求其二进制表示中“1”的个数,要求算法的执行效率尽可能地高。

《编程之美》中给出了五种解法,但是实际上从 Wikipedia 上我们可以找到更优的算法

这道题的本质相当于求二进制数的 Hamming 权重,或者说是该二进制数与 0 的 Hamming 距离,这两个概念在信息论和编码理论中是相当有名的。在二进制的情况下,它们也经常被叫做 population count 或者 popcount 问题,比如 gcc 中就提供了一个内建函数:

int __builtin_popcount (unsigned int x)

输出整型数二进制中 1 的个数。但是 GCC 的 __builtin_popcount 的实现主要是基于查表法做的,跟编程之美中解法 5 是一样的。Wikipedia 上的解法是基于分治法来做的,构造非常巧妙,通过有限次简单地算术运算就能求得结果,特别适合那些受存储空间限制的算法中使用:

/* ===========================================================================
* Problem:
*   The fastest way to count how many 1s in a 32-bits integer.
*
* Algorithm:
*   The problem equals to calculate the Hamming weight of a 32-bits integer,
*   or the Hamming distance between a 32-bits integer and 0. In binary cases,
*   it is also called the population count, or popcount.[1]
*
*   The best solution known are based on adding counts in a tree pattern
*   (divide and conquer). Due to space limit, here is an example for a
*   8-bits binary number A=01101100:[1]
* | Expression            | Binary   | Decimal | Comment                    |
* | A                     | 01101100 |         | the original number        |
* | B = A & 01010101      | 01000100 | 1,0,1,0 | every other bit from A     |
* | C = (A>>1) & 01010101 | 00010100 | 0,1,1,0 | remaining bits from A      |
* | D = B + C             | 01011000 | 1,1,2,0 | # of 1s in each 2-bit of A |
* | E = D & 00110011      | 00010000 | 1,0     | every other count from D   |
* | F = (D>>2) & 00110011 | 00010010 | 1,2     | remaining counts from D    |
* | G = E + F             | 00100010 | 2,2     | # of 1s in each 4-bit of A |
* | H = G & 00001111      | 00000010 | 2       | every other count from G   |
* | I = (G>>4) & 00001111 | 00000010 | 2       | remaining counts from G    |
* | J = H + I             | 00000100 | 4       | No. of 1s in A             |
* Hence A have 4 1s.
*
* [1] http://en.wikipedia.org/wiki/Hamming_weight
*
* ===========================================================================
*/
#include <stdio.h>

typedef unsigned int UINT32;
const UINT32 m1  = 0x55555555// 01010101010101010101010101010101
const UINT32 m2  = 0x33333333// 00110011001100110011001100110011
const UINT32 m4  = 0x0f0f0f0f// 00001111000011110000111100001111
const UINT32 m8  = 0x00ff00ff// 00000000111111110000000011111111
const UINT32 m16 = 0x0000ffff// 00000000000000001111111111111111
const UINT32 h01 = 0x01010101// the sum of 256 to the power of 0, 1, 2, 3

/* This is a naive implementation, shown for comparison, and to help in
* understanding the better functions. It uses 20 arithmetic operations
* (shift, add, and). */
int popcount_1(UINT32 x)
{
  x = (x & m1) + ((x >> 1) & m1);
  x = (x & m2) + ((x >> 2) & m2);
  x = (x & m4) + ((x >> 4) & m4);
  x = (x & m8) + ((x >> 8) & m8);
  x = (x & m16) + ((x >> 16) & m16);
  return x;
}

/* This uses fewer arithmetic operations than any other known implementation
* on machines with slow multiplication. It uses 15 arithmetic operations. */
int popcount_2(UINT32 x)
{
  x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
  x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
  x += x >> 8;           //put count of each 16 bits into their lowest 8 bits
  x += x >> 16;          //put count of each 32 bits into their lowest 8 bits
  return x & 0x1f;
}

/* This uses fewer arithmetic operations than any other known implementation
* on machines with fast multiplication. It uses 12 arithmetic operations,
* one of which is a multiply. */
int popcount_3(UINT32 x)
{
  x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
  x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
  return (x * h01) >> 24// left 8 bits of x + (x<<8) + (x<<16) + (x<<24)
}

int main()
{
  int i = 0x1ff12ee2;
  printf("i = %d = 0x%xn", i, i);
  printf("popcount_1(%d) = %dn", i, popcount_1(i));
  printf("popcount_2(%d) = %dn", i, popcount_2(i));
  printf("popcount_3(%d) = %dn", i, popcount_3(i));
  /* If compiled with other compiler than gcc, comment the line bellow. */
  printf("GCC's  __builtin_popcount(%d) = %dn", i,  __builtin_popcount(i));
  return 0;
}

从一个数列中取具有最小和的子序列

问题描述:给定一个含有 n 个元素的数列,元素有正有负,找出和最小的一组相邻的数。即给定 a[n],求 i,j 使得 a[i] + a[i+1] + ...+ a[j] 的和最小。

这个问题1并不难,但是我在想这个问题时经历了比较有趣的思考过程,写下来给大家分享一下。

其实这道题主要考察的是问题转换(或者说是抽象?)的能力,即如何将一个看似复杂的问题转换成一个简单的问题。直接求一个连续子列的和看起来很麻烦,我们要考虑 i 和 j 的取值,然后把子列中的元素加起来。但是换一个角度,一个连续子列的和可以看成是两个前缀和相减,比如:a[i] + a[i+1] + ...+ a[j] 实际上就等于 s[j] - s[i-1],其中 s[k] = a[0] + a[1] + ... + a[k]。这在高等数学中也是会被经常用到的方法。

所以我们要做的就是

计算出前缀和序列 s[n],并找出最小的 s[j] - s[i],其中 j>i,且 j,i 属于 {0,1,...,n}。

如果不要求 j>i,那么答案很简单,s[n] 中最小值减去最大值就是结果。但既然要求了 j>i,就不能这样做了,因为最小值的位置未必在最大值后面。最显而易见的方法就是遍历了:

J = 1; I = 0;
for (i=0; i<n; i++) {
  for (j=i+1; j<n; j++) {
    if (s[j] - s[i] < s[J] - s[I]) {
      I = i; J = j;
    }
  }
}

但是这个算法很耗时,两层嵌套,等差数列求和,复杂度肯定是 O(n2)。观察一下数列的规律我们可以发现,如果 s[i] < s[I] 的话,我们就没有必要计算 s[j] - s[i],因为结果肯定比 s[j] - s[I] 大嘛,同理可以用于 s[j] > s[J] 的情况,这样呢,我们可以稍微优化一点儿:

J = 1; I = 0;
for (i=0; i<n; i++) {
  if (s[i] < s[I]) continue;
  for (j=i+1; j<n; j++) {
    if (s[j] > s[J]) continue;
    if (s[j] - s[i] < s[J] - s[I]) {
      I = i; J = j;
    }
  }
}

但是这个优化作用到底有多大?我没有仔细计算,是比第一种情况快了一点儿,但最显著的速度提升还是在于第一层循环中,那样就能减少 n-i+1 次计算,在最坏的情况下仍然是 O(n2)。所以我觉得仍然不够,不就求一个最小值嘛,为什么那么慢呢,肯定是因为我笨。于是我就在 BBS 求助了一下别人,果然有人给出更快的算法:

J = 1; I = 0; max = 0;
for (i=1; i<n; i++) {
  if (s[i]-s[max] < s[J]-s[I]) {
    I = max;  J = i;
  }
  max = s[i] > s[I] ? i : max;
}

这个算法的思想是: s[I] 肯定是 s[J] 之前最大的数,s[J] 也是 s[I] 之后最小的数,那么保留到目前为止最大的数 s[max],用当前数 s[i] 去减它(肯定是小于 s[i] - s[I] 的),看它是否小于 s[J] - s[I],如果是的话,那么 s[i] -s[max] 就是到 i 为止最小的差值对。扫描一遍 s[n] 就能得到结果,O(n)!

后来我发现在 Jon Bentley 的《编程珠玑》第二版第8章讨论了这个问题1(只不过是讨论的最大值),在该章最后提出的算法4中,仅仅使用了与上面算法相同的扫描方法,而没有使用累加操作。虽然上面算法复杂度与算法 4 相同,但算法 4 复杂度中 n 的系数要小一些,下面是算法 4 的 C 语言实现:

int i = 0, I = 0, J = 0, I_end = 0;
int max_end = 0, max_sofar = 0;
for (i=0; i<len; i++) {
  max_end += a[i];
  if (max_end > 0) {
    max_end = 0; I_end = i;
  }
  if (max_sofar > max_end) {
    max_sofar = max_end;
    I = I_end; J = i;
  }
}

[1] 2008年1月15日注:这个问题出现在《Programming Pearls》第二版的 Column 8,Jon Bentley 对该问题的起源和算法发展做了非常详致的分析。

用两个非门和任意的与、或门构造三个非门

计算机科学中有很多有趣的 puzzle,他们可能出现在那些自命清高的企业的笔试题中,也可能来源于在网路上不经意的一瞥。后者比如我在无意中访问到的 Jamie Zawinski 的个人主页:http://www.jwz.org/,他即是在著名的 Teach Yourself Programming in Ten Years 一文中,Peter Norvig 提到的那位:

One of the best programmers I ever hired had only a High School degree; he's produced a lot of great software, has his own news group, and made enough in stock options to buy his own nightclub.

Jamie Zawinski 的个人主页看起来就像是 hexdump 的结果,而且以某种规律变化着,比较奇怪的是其中埋藏的一些超级链接并不发生变化。Jamie Zawinski 在网页的源代码中这样写道:

<!-- mail me if you find the secret -->
<!--   (no, you can't have a hint)  -->

我徒劳无功地搜索了一下,没有找到任何明确的解答。如果您通过我这篇文章了解到这个 puzzle,并且解答了它的话,非常希望您也 mail 给我一份解答。

说了那么多,其实本文的主题 puzzle 却是来源于前者。这个问题更详细的阐述是:

假设有一个逻辑黑盒,三个布尔型变量 x, y, z 作为输入,输出三个布尔变量 X, Y, Z,其中:
X = ~x; Y = ~y; Z = ~z;
注意,~ 符号代表一个非门。请用两个非门和任意多个与、或门实现这个黑盒。

这个问题大概是在计算机硬件设计中提出来的,所以看起来貌似很“电子”,但是其基础却是计算机科学中的布尔代数运算。下面代码的注释中已经包含详细的算法和分析,这里我就不再解释了。(当然,这个问题的答案不是我想出来的,我只是实现并分析了一下,作为我算法学习的笔记记录在此。)

/* ===========================================================================

* Problem:
*   Construct 3 NOT gates from only 2 NOT gates(and *no* XOR gates).
*
*   Assume that a logical blackbox has three Boolean inputs x, y, z and
*   three Boolean outputs X, Y, Z where the outputs are defined as:
*     X = ~x
*     Y = ~y
*     Z = ~z
*   Note that ~ stands for a NOT gate. Please realize this blackbox using
*   only two NOT gates, and as many as possible AND and OR gates.
*
* Algorithm I:
*   Internal Nodes:
*   r = (x & y) | (x & z) | (y & z);
*   R = ~r;
*   s = (R & (x | y | z)) | (x & y & z);
*   S = ~s;
*
*   Equations for Outputs:
*   X = (R & S) | (R & s & (y | z)) | (r & S & (y & z));
*   Y = (R & S) | (R & s & (x | z)) | (r & S & (x & z));
*   Z = (R & S) | (R & s & (x | y)) | (r & S & (x & y));
*
* Analysis I:
*   We create 4 internal signals first: r, R, s and S. What equations above
*   say is that signal `r' will be 1 if two or three of the inputs are 1.
*   Meanwhile, signal `s' will be 1 if only one input is 1 or if all three
*   inputs are 1. The end result is that the two-bit word formed from `r'
*   and `s' tells us how many 1's we have[1]:
*   | r s | Means  |    | x y z | r s |    | x y z | r s |
*   |++++++++++++++|    |+++++++++++++|    |+++++++++++++|
*   | 0 0 | 0 Ones |    | 0 0 0 | 0 0 |    | 1 0 0 | 0 1 |
*   | 0 1 | 1 One  |    | 0 0 1 | 0 1 |    | 1 0 1 | 1 0 |
*   | 1 0 | 2 Ones |    | 0 1 0 | 0 1 |    | 1 1 0 | 1 0 |
*   | 1 1 | 3 Ones |    | 0 1 1 | 1 0 |    | 1 1 1 | 1 1 |
*
*   Thus now that we have the signals r and s (and their inverse
*   counterparts R and S), it's easy to construct any Boolean function of
*   x, y, and z, using only AND and OR gates:
*     X = (R & S) | (R & s & (y | z)) | (r & S & (y & z))
*   Proof:
*    1> x, y, z are all 0s, (R & S) = ~(r | s) = 1, obviously X=Y=Z=1, X = ~x;
*    2> (x, y, z) has at least one 1, R & S = 0, will be ignored, hence we
*       have:
*         X = (R & s & (y | z)) | (r & S & (y & z))
*    2.1> (x, y, z) has two or three 1s, R = ~r = 0, (R & s & (y | z)) = 0,
*         will be ignored, then we get:
*           X = S & (y & z)
*    2.1.1> (x, y, z) has three 1s, S = ~s = 0, obviously X=Y=Z=0, X = ~x;
*    2.1.2> (x, y, z) has two 1s, S = ~s = 1, will be ignored, hence we have:
*             X = y & z
*    2.1.2.1> (y, z) has one 1, x = 1, X = y & z = 1 & 0 = 0, X = ~x;
*    2.1.2.2> (y, z) has two 1s, x = 0, X = y & z = 1 & 1 = 1, X = ~x;
*    2.2> (x, y, z) has one 1, r = 0, (r & S & (y & z)) = 0, will be ignored,
*         we have:
*           X = y | z
*    2.2.1> (y, z) has one 1, x = 0, X = y | z = 1 | 0 = 1, X = ~x;
*    2.2.2> (y, z) has no 1s, x = 1, X = y | z = 0 | 0 = 0, X = ~x.
*    In conclusion, X = ~x for all cases.
*   QED.
*
* Algorithm II:
*   Internal Nodes:
*   _2or3_1s = ((x & y) | (x & z) | (y & z));
*   _0or1_1s = !(_2or3_1s);
*   _1_1     = _0or1_1s & (x | y | z);
*   _1or3_1s = _1_1 | (x & y & z);
*   _0or2_1s = !(_1or3_1s);
*   _0_1s    = _0or2_1s & _0or1_1s;
*   _2_1s    = _0or2_1s & _2or3_1s;
*
*   Equations for Outputs:
*   X = _0_1s | (_1_1 & (y | z)) | (_2_1s & (y & z));
*   Y = _0_1s | (_1_1 & (x | z)) | (_2_1s & (x & z));
*   Z = _0_1s | (_1_1 & (x | y)) | (_2_1s & (x & y));
*
* Analysis II:
*   Almost the same as Analysis I.
*
* [1] http://www.edadesignline.com/howto/191600992
* ===========================================================================
*/

#include <stdio.h>

typedef unsigned int BOOL;

int main()
{
  int i, fail;
  BOOL x, y, z, X, Y, Z;
  BOOL r, R, s, S;
  BOOL _2or3_1s, _0or1_1s, _1_1,  _1or3_1s, _0or2_1s, _0_1s, _2_1s;

  /* ==================== Algorithm I ==================== */
  printf("Algorithm I:n");
  fail = 0;
  for (i=0; i<8; i++) {
    /* Init x, y, z. */
    x = i & 1;
    y = (i>>1) & 1;
    z = (i>>2) & 1;
    /* Internal nodes. */
    r = (x & y) | (x & z) | (y & z);
    //R = !r;                               /* #1 NOT gate. */
    R = ~r & 1;                             /* #1 NOT gate. */
    s = (R & (x | y | z)) | (x & y & z);
    //S = !s;                               /* #2 NOT gate. */
    S = ~s & 1;                             /* #2 NOT gate. */
    /* Output. */
    X = (R & S) | (R & s & (y | z)) | (r & S & (y & z));
    Y = (R & S) | (R & s & (x | z)) | (r & S & (x & z));
    Z = (R & S) | (R & s & (x | y)) | (r & S & (x & y));

    if ((x == X) | (y == Y) | (z == Z)){
      fail ++;
      printf("FAIL: ");
    } else {
      printf("PASS: ");
    }
    printf("xyz = %u%u%u, XYZ = %u%u%un", x, y, z, X, Y, Z);
  }
  if (fail != 0) {
    printf("%d TEST FAILED!n", fail);
  } else if (!fail) {
    printf("ALL TEST PASSED!n");
  }

  /* ==================== Algorithm II ==================== */
  printf("Algorithm II:n");
  fail = 0;
  for (i=0; i<8; i++) {
    /* Init x, y, z. */
    x = i & 1;
    y = (i>>1) & 1;
    z = (i>>2) & 1;
    /* Internal nodes. */
    _2or3_1s = ((x & y) | (x & z) | (y & z));
    //_0or1_1s = !(_2or3_1s);               /* #1 NOT gate. */
    _0or1_1s = ~(_2or3_1s) & 1;             /* #1 NOT gate. */
    _1_1     = _0or1_1s & (x | y | z);
    _1or3_1s = _1_1 | (x & y & z);
    //_0or2_1s = !(_1or3_1s);               /* #2 NOT gate. */
    _0or2_1s = ~(_1or3_1s) & 1;             /* #2 NOT gate. */
    _0_1s    = _0or2_1s & _0or1_1s;
    _2_1s    = _0or2_1s & _2or3_1s;
    /* Output. */
    X = _0_1s | (_1_1 & (y | z)) | (_2_1s & (y & z));
    Y = _0_1s | (_1_1 & (x | z)) | (_2_1s & (x & z));
    Z = _0_1s | (_1_1 & (x | y)) | (_2_1s & (x & y));

    if ((x == X) | (y == Y) | (z == Z)){
      fail ++;
      printf("FAIL: ");
    } else {
      printf("PASS: ");
    }
    printf("xyz = %u%u%u, XYZ = %u%u%un", x, y, z, X, Y, Z);
  }
  if (fail != 0) {
    printf("%d TEST FAILED!n", fail);
  } else if (!fail) {
    printf("ALL TEST PASSED!n");
  }
  return 0;
}

Math in CS: 数论和公钥密码学

1940年,英国数学家哈代在他的一本小书《一个数学家的辩白》(A Mathematician's Apology)中说:“如果有用的知识是这样的知识(我们暂时同意这样说):它大概会在现在或相对不远的未来,为人类在物质上的享受方面作出贡献,因而,它是否在单纯的智力上满足人们乃是无关紧要的,那么,大量更高级的数学就是无用的。现代几何和代数、数论、集合论和函数论、相对论、量子力学——没有一种比其它的更经得住这种检验,也没有真正的数学家的生涯可以在这个基础上被证明是有价值的。”但是我们会看到,哈代这个断定在当时“不远的未来”几乎被一一证明是错误的,数论就是其中一个。

在 1970 年代以前,人们所知道的密码学都是对称密码学,就是在加密和解密过程中需要使用同一个密钥。在那个时代,一些密码算法已经能保证足够的安全性,比如数据加密标准 DES。但是人类的需求是很难完全得到满足的,他们为每次密钥交换的复杂度而苦恼,比如在战时如果密码本被敌方获得,就必须重新向无线电收发员分发密码本,这个工作量和代价是相当大的;还有一个需求就是数字签名,能不能用加密实现对数字文件的签名,像手写的签名一样,确保该文件出自谁人之手?

上述问题,就是 Whitfield Diffie 和 Martin Hellman 1976 年在他们那篇划时代的论文《密码学的新方向》(New Directions in Cryptography)中提出的,他们也给出了其中一个问题的解决办法,那就是 Deffie-Hellman 密钥交换算法(后来被改为 Deffie-Hellman-Merkle 密钥交换算法,里面还有一段小故事。)。但是 DH 没做完的功课,仅仅在一年后就被 RSA 解决了,那就是 Ron Rivest, Adi Shamir, 和 Leonard Adleman 的 "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"。RSA 的加密和解密使用的是不同的密钥,即公钥和私钥,你可以将你的公钥扔到世界上任何一个位置,我用你的公钥加密一段信息,除了你用自己的私钥解密,没有别的人能从中得到原始消息。就相当于你把打开了的箱子扔的满世界都是,但箱子一旦锁上,就只有你能再打开。

RSA 算法自其诞生之日起就成为被广泛接受且被实现的通用公钥算法,但是 RSA 算法还带来一个另外的意义,那就是:数论知识从未像现在这样被广泛地使用着。RSA 程序的普及率要远远大于 Windows,因为每台 Windows 上都装配着 RSA 算法程序,但 RSA 并不仅仅装配 Windows。每当你登录邮箱、网上银行、聊天软件、安全终端,你都在使用着数论带来的好处。而且相比之前密码学的字母替换和置换,混淆和扩散,DH 和 RSA 使用的东西更有资格说自己是数学。

大概也是由于其基于数学的简洁性,RSA 和 DH 算法描述要比 DES, AES 简练许多,我在这篇小文中都能写完。

RSA

RSA 用到了数论中的三个基本定理:费马小定理、欧拉定理和中国剩余定理(几乎处处都在),和一个古典难题:大整数分解问题。如果你是数学系的学生,对这些概念一定不会陌生。

费马小定理:若 p 是素数,a 是正整数且不能被 p 整除,则: ap-1 = 1(mod p)。或者另一种形式:ap=a(mod p),这种形式不要求 a 与 p 互素。

欧拉定理:对任意互素的 a 和 n,有 aΦ(n) = 1(mod n)。其中,Φ(n)是欧拉函数,即小于 n 且与 n 互素的正整数的个数。

大整数分解问题:将两个整数乘起来是简单的,但是将一个整数分解为几个整数的乘积是困难的,尤其是当这个数比较大的时候。迄今为止没有有效的算法来解决这个问题,甚至我们连这个问题的计算复杂度量级是多少都不知道。

那么 RSA 算法是什么样的呢?

密钥的产生:
1. 选择两个素数 p 和 q.
2. 计算 n = p*q.
3. 计算 Φ(n) = (p-1)(q-1) (这是欧拉函数的性质)
4. 选择 e<Φ(n) 并使得其与 Φ(n) 互素。
5. 确定 d<Φ(n) 并使得 d*e = 1(mod Φ(n))。
6. 这时候,私钥就是{d, n},公钥就是{e, n}。
加密算法:
假设 M 是明文(M<n),那么密文就是 C = Memod n。(为什么明文是数字?在计算机科学里任何数据最终表示都是数字。)
解密算法:
假设 C 是密文,那么明文就是 M = Cd mod n。

我们来证明一下算法是否正确,由于 Cd = Me*d = Mk*Φ(n)+1 (mod n)。

如果 M 和 n 是互素的,显然直接由欧拉定理我们就能得到:
Cd = Mk*Φ(n)*M1 = M (mod n) = M
说明算法是正确的;
如果 M 和 n 不互素,由于 n 是两个素数 p 和 q 的乘积且 M<n,那么 M 要么是 p 的倍数,要么是 q 的倍数,由 e*d = 1(mod Φ(n)) = 1(mod (p-1)(q-1)) 我们可得:
e*d = 1(mod (p-1)) 且 e*d = 1(mod (q-1))
则 e*d 可以写成: e*d = k*(p-1)+1, e*d = h*(p-1)+1
由费马小定理,我们有:Me*d = Mk*(p-1)+1 = M(mod p) 和 Me*d = Mh*(q-1)+1 = M(mod q)。
由于 p 和 q 均为素数,且 p, q 均整除 Me*d-M,所以我们有:
Cd = Me*d = M (mod p*q) = M (mod n) = M

从上面我们可以看到 RSA 算法实现了加密和解密使用不同密钥,而且证明了这个算法的正确性。但 RSA 算法要想实用,光有正确性还不够,最重要的一点是安全性,即从公钥{e, n}无法推导出私钥{d, n}。在 RSA 算法中我们可以看到,关键要知道 Φ(n),知道了 Φ(n),使用欧几里德算法就能求出 e 的逆元,就得到了用户的私钥{d, n}。要求出 Φ(n),就必须知道 p,q,但 p,q 是不公开的,仅仅知道 p,q 的乘积 n 去求 p,q,根据大整数分解古典难题,当 n 比较大时其分解在计算上是不可行的。这就保证了 RSA 算法的安全性。

而且 RSA 算法是可逆的,所以它就有能力同时实现加密和签名的功能。由于公钥是公开的,每个人都可以用你的公钥加密一段信息发给我,而私钥是保密的,所以只有你能看到别人用你的公钥加密的消息;而也因为可逆性,如果你用私钥解密一段明文(实际是加密),所有人都可以用你的公钥加密它来得到明文(实际是解密),因为私钥只有你一个人知道,这个消息只有可能是你发出的,就相当于你对这段明文做了一个签名。

DH 密钥交换算法

DH 密钥交换算法较 RSA 算法更为简单,它也是基于数论中的一个古典难题:离散对数问题。

离散对数问题:若 p 是素数,p 已知,考虑方程 y = gx mod p,给定 g,x 求 y 是简单的,但给定 y,g 求 x,即求 x = logg,py mod p,在计算上是不可行的。

DH 密钥交换算法的描述如下:
已知公开的素数 p 和 p 的本原根 α
1. 用户 A 选择秘密的 Xa<p,计算 Ya = αXa mod p,将其发送给 B。
2. 用户 B 选择秘密的 Xb<p,计算 Yb = αXb mod p,将其发送给 A。
3. A 和 B 分别计算 Ka = (Yb)Xa mod p 和 Kb = (Ya)Xb mod p,就同时得到了共享的密钥 K=Ka=Kb,然后就可以用 K 进行加密传输了。

DH 密钥交换算法的优点在于:双方在通信前不需要知道任何共享的密钥,而是通过公开的 p 和 α 协商出一个密钥来进行加密通信。

先看一下算法的正确性,Ka = Kb 是否成立:
Ka = (Yb)Xa = (αXb)Xa = αXa*Xb (mod p)
Kb = (Ya)Xb = (αXa)Xb = αXa*Xb (mod p)
Bingo! Ka 和 Kb 是相同的。

再来看一下算法的安全性,就是能否从公开的信息推导出 K 来:
由于密钥是 K = αXa*Xb,那么攻击者必须知道 Xa 和 Xb 才能得到共享的密钥 K,而公开的信息只有 Ya 和 Yb,由离散对数问题,从 Ya,Yb 求出 Xa,Xb 在计算上是不可行的,就保证了算法的安全性。

从上面两个算法我们可以看出,数论在公钥密码学中的重要地位,恐怕哈代当时怎么也想不到三十多年后人人都在使用他所认为在实际生活中毫无用处的数论吧!

薄弱的算法基础

这几日复习累时,翻出来 MIT 的《算法导论》课程录像来看,发现一个非常沮丧的事实:我对算法知道的真少。

仅仅看了 3 节课,就听到了几个我不懂的东西。比如计算递归算法复杂度的 master method,计算 Fibonacci 数列的复杂度为 θ(lg(n)) 的算法,计算矩阵相乘的复杂度为 θ(nlog2(7)) 的 Strassen 算法。这些东西我以前都没听说过,真是孤陋寡闻啊!

那本《算法导论》大概在我的书架上已经摆了两年了,两年我仅仅看了六七十页。我太懒是最主要的原因,但还有一个原因是从头开始看激发不了兴趣,前面讲的一些算法都是数据结构书上看过的东西,不是很有吸引力,看着看着就觉得索然无味,扔一边了。

不过我也从来没自诩过算法好,逛 BBS 时我主要在电脑技术版转,在其它的版都敢指手画脚一番,唯有在算法版老老实实潜水。计算机科学就是这样,知识层次不如别人,那就根本插不上话。这也是我极少在 pongba 兄的 TopLanguage 讨论组发言的一个原因,因为里面我感兴趣的话题主要是算法相关,而算法问题我又插不上嘴,只好默默潜水。

我的算法知识,大概仅限于我现在都不知道扔哪儿的一本《数据结构》书了。不是科班出身,也没正儿八经听过算法课,所以现在就有系统地学习算法知识的打算了,把存在电脑里好久的算法导论视频翻了出来。Charles Leiserson 讲的很不错,单就趣味性来说,《算法导论》的课程录像可比书要有意思多了。我想在最近的这段时间里,我应该至少能把录像看完。

另外,我在博客分类里添加了 Algorithm 一项,我将看看,在过一段日子后,我对算法的使用和理解能力能否有一些提高。