In this article we state and prove a corrected version of Theorem 3.5 in [SIAM J. Comput., 18 (1989), pp. 859--881].

A distribution on n-bit strings is called $(\varepsilon ,e)$-locally random, if for every choice of $e \leqslant n$ positions the induced distribution on e-bit strings is in the $L_1 $-norm at most $\varepsilon $ away from the uniform distribution on e-bit strings. Local randomness in polynomial random number generators (RNG) that are candidate one-way functions is established. Let N be a squarefree integer and let $f_1 , \ldots ,f_\ell $ be polynomials with coefficients in $\mathbb{Z}_N = {\mathbb{Z} / {N\mathbb{Z}}}$. The RNG that stretches a random $x \in \mathbb{Z}_N $ into the sequence of least significant bits of $f_1 (x), \ldots ,f_\ell (x)$ is studied. It is shown that this RNG provides local randomness if for every prime divisor p of N the polynomials $f_1 , \ldots ,f_\ell $ are linearly independent modulo the subspace of polynomials of degree $ \leqslant 1$ in $\mathbb{Z}_p [x]$. Also established is local randomness in polynomial random function generators. This yields candidates for cryptographic hash functions. The concept of local randomness in families of functions extends the concept of universal families of hash functions by Carter and Wegman [J. Comput. System Sci., 18 (1979) pp. 143–154]. The proofs of the results rely on upper bounds for exponential sums.

This paper considers variants and generalizations of the following computational problem. Given a real input ${\bf x} \in \mathbb{R}^n $, find a small integer relation ${\bf m}$ for x that is a nonzero vector $m \in \mathbb{Z}^n $ orthogonal to ${\bf x}$, or prove that no integer relation ${\bf m}$ exists with $\|{\bf m}\| \leqq 2^\lambda $. An algorithm is presented that solves this problem in $O(n^3 (k + n))$ arithmetic operations over real numbers. The algorithm is a variation of the multidimensional Euclidean algorithm proposed by Ferguson and Forcade [Bull. Amer. Math. Soc., 1(1979), pp. 912–914] and Bergman [Notes on Ferguson and Forcade’s Generalized Euclidean Algorithm, University of California, Berkeley, CA, 1980]. A connection between such multidimensional Euclidean algorithms and the Lattice Basis Reduction Algorithm of Lenstra, Lenstra Jr., and Lovász [Math. Ann., 21 (1982), pp. 515–534] is shown. Polynomial time solutions are also established for finding linearly independent sets of small integer relations and for finding small simultaneous integer relations for several real vectors, using real input vectors and counting arithmetic operations over real numbers at unit cost. For integer input vectors ${\bf x}$ a different algorithm is given for finding integer relations (that always exist) that uses at most $O(n^3 \log \|x\|)$ arithmetic operations on $O(n + \log \|{\bf x}\|)$ bit integers.

The RSA and Rabin encryption functions $E_N ( \cdot )$ are respectively defined by raising $x \in Z_N $ to the power e (where e is relatively prime to $\varphi (N)$) and squaring modulo N (i.e., $E_N (x) = x^e (\bmod N)$, $E_N (x) = x^2 (\bmod N)$, respectively). We prove that for both functions, the following problems are computationally equivalent (each is probabilistic polynomial-time reducible to the other): (1) Given $E_N (x)$, find x. (2) Given $E_N (x)$, guess the least-significant bit of x with success probability $\tfrac{1}{2} + {1 {{\operatorname{poly}}(n)}}$ (where n is the length of the modulus N). This equivalence implies that an adversary, given the RSA/Rabin ciphertext, cannot have a non-negligible advantage (over a random coin flip) in guessing the least-significant bit of the plaintext, unless he can invert RSA/factor N. The proof techniques also yield the simultaneous security of the $\log n$ least-significant bits. Our results improve the efficiency of pseudorandom number generation and probabilistic encryption schemes based on the intractability of factoring.

Let the multiplicative complexity L(f) of a boolean function f be the minimal number of ∧-gates that are sufficient to evaluate f by circuits over the basis ∧,⊕,1. We give a polynomial time algorithm which for quadratic boolean forms f=⊕i≠jaijxixj determines L(f) from the coefficients aij. Two quadratic forms f,g have the same complexity L(f) = L(g) iff they are isomorphic by a linear isomorphism. We also determine the multiplicative complexity of pairs of quadratic boolean forms. We give a geometric interpretation to the complexity L(f1,f2) of pairs of quadratic forms.

This paper describes an O ( n 3 log n ) deterministic algorithm and an O ( n 3 ) Las Vegas algorithm for testing whether two given trivalent graphs on n vertices are isomorphic. In fact, the algorithms construct the set of all isomorphisms between two such graphs, presenting, in particular, generators for the group of all automorphisms of a trivalent graph. The algorithms are based upon the original polynomial-time solution to these problems by Luks but they introduce numerous speedups. These include improved permutation-group algorithms that exploit the structure of the underlying 2-groups. A remarkable property of the Las Vegas algorithm is that it computes the set of all isomorphisms between two trivalent graphs for the cost of computing only those isomorphisms that map a specified edge to a specified edge.

We present a hierarchy of polynomial time lattice basis reduction algorithms that stretch from Lenstra, Lenstra, Lovász reduction to Korkine–Zolotareff reduction. Let λ(L) be the length of a shortest nonzero element of a lattice L. We present an algorithm which for k∈N finds a nonzero lattice vector b so that |b|2⩽(6k2)nkλ(L)2. This algorithm uses O(n2(kk+o(k))+n2)log B) arithmetic operations on O(n log B)-bit integers. This holds provided that the given basis vectors b1,…,bn∈Zn are integral and have the length bound B. This algorithm successively applies Korkine–Zolotareff reduction to blocks of length k of the lattice basis. We also improve Kannan's algorithm for Korkine-Zolotareff reduction.

The equation of the title arose in the proposed signature scheme of Ong-Schnorr-Shamir. The large integersn, kandmare given and we are asked to find any solutionx, y. It was believed that this task was of similar difficulty to that of factoring the modulusn;we show that, on the contrary, a solution can easily be found ifkandmare relatively prime ton. Under the assumption of the generalized Riemann hypothesis, a solution can be found by a probabilistic algorithm inO(\log n)^{2}|\log\log|k||)arithmetical steps onO(\log n)-bit integers. The algorithm can be extended to solve the equationX^{2} + KY^{2} = M \pmod{n}for quadratic integersK, M \in {\bf Z}[\sqrt{d}]and to solve in integers the equationx^{3} + ky_{3} + k^{2}z^{3} - 3kxyz = m \pmod{n}.

In this paper we prove a 3n upper and lower bound on the complexity of sorting on a n × n mesh connected parallel computer, and describe an exceptionally simple algorithm which sorts the array by alternately sorting its rows and columns log log n times.

We prove that RSA least significant bit is 1/2 + (1/[logcN]) secure, for any constant c (where N is the RSA modulus). This means that an adversary, given the ciphertext, cannot guess the least sigiiilicatnt bit of the plaintext with probability better than 1/2 + (1/[logcN]), unless he can break RSA.

Electronic messages, documents and checks must be authenticated by digital signatures which are not forgeable even by their recipients. The RSA system can generate and verify such signatures, but each message requires hundreds of high precision modular multiplications which can be implemented efficiently only on special purpose hardware. In this paper we propose a new signature scheme which can be easily implemented in software on microprocessors: signature generation requires one modular multiplication and one modular division, signature verification requires three modular multiplications, and the key size is comparable to that of the RSA system. The new scheme is based on the quadratic equation m = s21 + ks22 (mod n), where m is the message, s1 and s2 are the signature, and k and n are the publicly known key. While we cannot prove that the security of the scheme is equivalent to factoring, all the known methods for solving this quadratic equation for arbitrary k require the extraction of square roots modulo n or the solution of similar problems which are at least as hard as factoring. A novel property of the new scheme is that legitimate users can choose k in such a way that they can sign messages even without knowing the factorization of n, and thus everyone can use the same modulus if no one knows its factorization.

The main results of this paper are an O(n3) probabilistic algorithm and an O(n3 log n) deterministic algorithm that test whether two given trivalent graphs are isomorphic. In fact, the algorithms construct the set of all isomorphisms of the two graphs. Variants of these algorithms construct the set of all automorphisms of a trivalent graph. The algorithms make use of some new improved permutation group algorithms that exploit the fact that the groups involved are 2-groups. A remarkable property of the probabilistic algorithm is that it computes Isoe,ei(X,Y), i = 1,...,m, m = O(n) (the set of all isomorhisms φ: X → Y with φ(e)=ei) for the cost of computing the single set Isoe,el(X,Y).

With every set $P_1 , \cdots ,P_m $ of multivariate polynomials we associate in a natural way several algebraic varieties, i.e., irreducible Zariski-closed sets. The degree of each of these closed sets can be nicely bounded in terms of the number $L_{ns} (P_1 , \cdots ,P_m )$ of nonscalar operations which are necessary to evaluate $P_1 , \cdots ,P_m $. We establish lower bounds $L_{ns} (P) \geqq \Omega (k\lg n)$ for single specific polynomials P of degree n, depending on $O(k)$ variables with 0, 1-coefficients. Typical examples are $L_{ns} (\sum_{i = 1}^k {x_i^n y^i } ) \geqq \frac{1} {2}k\lg n$, $L_{ns} (\sum_{i = 1}^k {(x_1 + x_2 + \cdots + x_i )^n y_i } ) > \frac{1}{2}k\lg n$, provided $k < n^{1/2} $. By our method and evaluating the degree of closed sets one obtains lower bounds $L_{ns} (P) > \Omega (k\lg n)$ for “almost all” polynomials P of degree n depending on k variables, $k \ll n$. These lower bounds hold for any field characteristic.

We exploit the fact that the set of all polynomials Pε@@@@[x1,..,xn] of degree ≤d which can be evaluated with ≤v nonscalar steps can be embedded into a Zariski-closed affine set W(d,n,v),dim W(d,n,v)≤(v+1 +n)2 and deg W(d,n,v)≤(2vd)(v+1+n)2. As a consequence we prove that for u:= 2v(d+1)2 and s:= 6(v+1+n)2 there exist a1,..,asε [u]n = {1,2,..,u}n such that for all polynomials PεW(d,n,v):P(a1) = p(a2) =...= p(as) = O implies PΞO. This means that a1,...,as is a correct test sequence for a zero test on all polynomials in W(d,n,v). Moreover, “almost every” sequence a1,..,asε[u]n is such a correct test sequence for W(d,n,v). The existence of correct test sequences a1,..,asε [u]n is established by a counting argument without constructing a correct test sequence. We even show that it is beyond the known methods to establish (i.e. to construct and to prove correctness) of such a short correct test sequence for W(d,n,v). We prove that given such a short, correct test sequence for W(d,n,v) we can efficiently construct a multivariate polynomial Pε@@@@[x1,..,xn] with deg(P) = d and small integer coefficients such that [email protected]@@@ W(d,n,v). For v>n log d lower bounds of this type are beyond our present methods in algebraic complexity theory.

Let $F_{u,v} $ be the maximal flow from u to v in a network $\mathcal{N} = (V,E,c)$. We construct the matrix ($\min \{ F_{u,v} ,F_{v,u} \} |u,v \in V$) by solving $|V|\log 2|V|$ individual max-flow problems for $\mathcal{N}$. There is a tree network $\mathcal{N} = (V,\bar E,\bar c)$ that stores minimal cuts corresponding to min $\{ F_{u,v,} F_{v,u} \} $ for all $u,v$. $\bar{\mathcal{N}}$ can be constructed by solving $|V|\log 2|V|$ individual max flow problems for the given network which can be done within $O(|V|^4 )$ steps using the Dinic–Karzanov algorithm. We design an algorithm that computes the edge connectivity k of a directed graph within $O(k\cdot |E|\cdot |V|)$ steps.

Considered are the classes QL (quasilinear) and NQL (nondet quasllmear) of all those problems that can be solved by deterministic (nondetermlnlsttc, respectively) Turmg machines in time O(n(log n) ~) for some k Effloent algorithms have time bounds of th~s type, it is argued.Many of the "exhausUve search" type problems such as satlsflablhty and colorabdlty are complete in NQL with respect to reductions that take O(n(log n) k) steps This lmphes that QL = NQL iff satisfiabdlty is m QL

An algorithm for transitive closure is described with expected time $O(n + m^ * )$ where n is the number of nodes and $m^ * $ is the expected number of edges in the transitive closure.

Abstract We formalise the notion of those infinite binary sequences z that admit a single program P which expresses the entire algorithmical structure of z. Such a program P minimizes the information which must be used in a relative computation for z. We propose two concepts with different strength for this notion, the learnable and the super-learnable sequences. We establish three different equivalent characterizations of learnable (super-learnable, resp.) sequences. In particular, we prove that a sequence z is learnable (super-learnable, resp.) if and only if there is a computable probability measure p such that p is Schnorr (Martin-Löf, resp.) p-random. There is a recursively enumerable sequence which is not learnable. The learnable sequences are invariant with respect to all total and effective transformations of infinite binary sequences.

We propose a variant of the Kolmogorov concept of complexity which yields a common theory of finite and infinite random sequences. The process complexity does not oscillate. We establish some concepts of effective tests which are proved to be equivalent.