Book Review: Kolmogorov complexity and algorithmic randomness
Book Review: Kolmogorov complexity and algorithmic randomness
复制标题
书评：柯尔莫哥洛夫复杂性和算法随机性
DOI：
10.1090/bull/1676
复制
发表时间：
2020
影响因子：
1.3
通讯作者：
Rojas, J. Maurice
中科院分区：
文献类型：
--
作者：
Rojas, J. Maurice
2.1.来自离散对数问题的伪随机比特流。考虑一下Blum和Micali[BM84]对一族(假定)不可预测的比特序列的著名构造。在下文中，n是正整数，p∈{2n−1+1，...，2n−1}是奇素数(因此p在其二进制展开中正好有n个位)，g是非零整数mod p的乘法群F∗p的生成器，而x0∈{0，...，p−2}被称为比特流的种子。设MP：{1，...，p−1}−→{0，1}表示满足MP(A)=1的函数当且仅当a≥(p−1)/2(因此MP(A)类似于a的最高有效位)，然后通过递归xj+1：=gxj mod p定义一个序列(x0，x1，...，xN)，比方说N：=n10，对所有j≥0有效。2我们的伪随机比特序列-Blum-Micali伪随机产生器(PRG)的一个实例-然后是
2.1. Pseudorandom bit streams from the Discrete Logarithm Problem. Consider the following famous construction, by Blum and Micali [BM84], of a family of (putatively) unpredictable sequences of bits. In what follows, n is a positive integer, p∈{2n− 1+ 1,..., 2n− 1} is an odd prime (so p has exactly n bits in its binary expansion), g is a generator for the multiplicative group F∗ p of nonzero integers mod p, and x0∈{0,..., p− 2} is called the seed for our bit stream. Letting Mp:{1,..., p− 1}−→{0, 1} denote the function satisfying Mp (a)= 1 if and only if a≥(p− 1)/2 (so Mp (a) is akin to the most significant bit of a), we then define a sequence (x0, x1,..., xN) with, say, N:= n10, via the recurrence xj+ 1:= gxj mod p, valid for all j≥ 0. 2 Our pseudorandom sequence of bits—an instance of the Blum–Micali pseudorandom generator (PRG)—is then