We study a variant of the Miller-Rabin primality test, which only looks at the last (z+1) powers of the base. This test is between Miller-Rabin and Fermat in terms of strength. For (z=1) the test can be thought of as a variant of the Solovay-Strassen test. We show that for every (z ≥ 0) this test has infinitely many "Carmichael" numbers. We also give empirical results on the rate of growth of the test's "Carmichael" numbers, noting that the growth rate decreases geometrically with increasing (z). We provide some heuristic evidence for this pattern. We also extend our existence result to some generalizations of Miller-Rabin that use (b)-th powers instead of squares.

We study discrete logarithms in the setting of group actions. Suppose that G is a group that acts on a set S. When r and s are elements of S, a solution g to rg = s can be thought of as a kind of logarithm. In this paper, we study the case where G = Sn, and develop analogs to the Shanks baby-step / giant-step procedure for ordinary discrete logarithms. Specifically, we compute two subsets A and B of Sn, such that every permutation in Sn can be written as a product ab of elements from A and B. Our deterministic procedure is close to optimal, in the sense that A and B can be computed efficiently and |A| and |B| are not too far from sqrt(n!) in size. We also analyze randomized "collision" algorithms for the same problem.

IPSs determine whether incoming traffic matches a database of vulnerability signatures defined as regular expressions. DFA representations are popular, but suffer from the state-explosion problem. We introduce a new matching structure: a tree of DFAs where the DFA associated with a node over-approximates those at its children, and the DFAs at the leaves represent the signature set. Matching works top-down, starting at the root of the tree and stopping at the first node whose DFA does not match. In the common case (benign traffic) matching does not reach the leaves. DFA-trees are built using Compact Overapproximate DFAs (CODFAs). A CODFA D' for D over-approximates the language accepted by D, has a smaller number of states than D, and has a low false-match rate. Although built from approximate DFAs, DFA-trees perform exact matching faster than a commonly used method, have a low memory overhead and a guaranteed good worst case performance.

An integer n is (y,z)-semismooth if n=pm where m is an integer with all prime divisors ≥ y and p is 1 or a prime ≥ z. Large quantities of semismooth integers are utilized in modern integer factoring algorithms, such as the number field sieve, that incorporate the so-called large prime variant. Thus, it is useful for factoring practitioners to be able to estimate the value of Ψ(x,y,z), the number of (y,z)-semismooth integers up to x, so that they can better set algorithm parameters and minimize running times, which could be weeks or months on a cluster supercomputer. In this paper, we explore several algorithms to approximate Ψ(x,y,z) using a generalization of Buchstab's identity with numeric integration.

A random multivariate polynomial system with more equations than variables is likely to be unsolvable. On the other hand, if there are more variables than equations, the system has at least one solution with high probability. In this paper we study in detail the phase transition between these two regimes, which occurs when the number of equations equals the number of variables. In particular, the limiting probability for no solution is 1/e at the phase transition, over a prime field. We also study the probability of having exactly s solutions, with s ≥ 1. In particular, the probability of a unique solution is asymptotically 1/e if the number of equations equals the number of variables. The probability decreases very rapidly if the number of equations increases or decreases. Our motivation is that many cryptographic systems can be expressed as large multivariate polynomial systems (usually quadratic) over a finite field. Since decoding is unique, the solution of the system must also be unique. Knowing the probability of having exactly one solution may help us to understand more about these cryptographic systems. For example, whether attacks should be evaluated by trying them against random systems depends very much on the likelihood of a unique solution.

A Boolean function is called correlation immune if every input is independent of the output when the inputs are chosen from a uniform distribution. We show how an asymptotic formula of Denisov, which approximately counts the n-variable correlation immune functions, can be improved so as to be accurate even for fairly small n. We also provide error estimates for our approximations, which Denisov did not do, and show a connection to the behavior of random walks. Such information is useful to designers of machine learning algorithms and stream ciphers.

We define and analyze quantum computational variants of \nrandom walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random \nwalk, which we call the Hadamard walk. Several striking \ndifferences between the quantum and classical cases are ob- served. For example, when unrestricted in either direction, \nthe Hadamard walk has position that is nearly uniformly \ndistributed in the range [-t/√2, t/√2] after t steps, which \nis in sharp contrast to the classical random walk, which has \ndistance O(√t) from the origin with high probability. With \nan absorbing boundary immediately to the left of the starting position, the probability that the walk exits to the left is 2/π, and with an additional absorbing boundary at location n, the probability that the walk exits to the left actually increases, approaching 1/√2 in the limit. In the classical case both values are 1.

In this article it is shown how Gauss' (1981) famous cyclotomic sum formula can be used for extracting square-roots modulo N.

We show that the random number generator of Marsaglia and Zaman (1991) produces the successive digits of a rational b-adic number. (The b-adic number system generalizes p-adic numbers to an arbitrary integer base b.) Using continued fractions, we derive an efficient prediction algorithm for this generator.

A goal of research on DNA computing is to solve problems that are beyond the capabilities of the fastest silicon-based supercomputers. Adleman and Lipton present exhaustive search algorithms for 3Sat and 3-Coloring, which can only be run on small instances and hence are not practical. In this paper, we show how improved algorithms can be developed for the 3-Coloring and Independent Set problems. Our algorithms use only the DNA operations proposed by Adleman and Lipton, but combine them in more powerful ways, and use polynomial preprocessing on a standard computer to tailor them to the specific instance to be solved. The main contribution of this paper is a more general model of DNA algorithms than that proposed by Lipton. We show that DNA computation for NP-complete problems can do more than just exhaustive search. Further research in this direction will help determine whether or not DNA computing is viable for NP-hard problems. A second contribution is the first analysis of errors that arise in generating the solution space for DNA computation.

We examine a very simple asynchronous model of parallel computation that assumes the time to compute a task is random, following some probability distribution. The goal of this model is to capture the effects of unpredictable delays on processors, due to communication delays or cache misses, for example. Using techniques from queueing theory and occupancy problems, we use this model to analyze two parallel dynamic programming algorithms. We show that this model is simple to analyze and correctly predicts which algorithm will perform better in practice. The algorithms we consider are a pipeline algorithm, where each processor i computes in order the entries of rows i, i+p, and so on, where p is the number of processors; and a diagonal algorithm, where entries along each diagonal extending from the left to the top of the table are computed in turn. It is likely that the techniques used here can be useful in the analysis of other algorithms that use barriers or pipelining techniques.

We examine a very simple asynchronous model of parallel computation that assumes the time to compute a task is random, following some probability distribution. The goal of this model is to capture the effects of unexpected delays on processors.

No abstract

This paper presents an efficient method for generating a random integer with known factorization. When given a positive integer N, the algorithm produces the prime factorization of an integer x drawn uniformly from ${N / 2} < x \leqq N$. The expected running time is that required for $O(\log N)$ prime tests on integers less than or equal to N. If there is a fast deterministic algorithm for primality testing, this is a polynomial-time process. The algorithm can also be implemented with randomized primality testing; in this case, the distribution of correctly factored outputs is uniform, and the possibility of an incorrectly factored output can in practice be disregarded.

Many problems such as primality testing can be solved efficiently using a source of independent, identically distributed random numbers. It is therefore customary in the theory of algorithms to assume the availability of such a source. However, probabilistic algorithms often work well in practice with pseudo-random numbers; the point of this paper is to offer a justification for this fact.

Let N be a positive integer, and let $\sigma (N)$ denote the sum of the divisors of N (e.g. $\sigma (6) = 1 + 2 + 3 + 6 = 12$). We show computing $\sigma (N)$ is equivalent to factoring N in the following sense: there is a random polynomial time algorithm that, given $\sigma (N)$, produces the prime factorization of N, and $\sigma (N)$ can be computed in polynomial time given the factorization of N. We show that the same result holds for $\sigma _k (N)$, the sum of the kth powers of divisors of N We give three new examples of problems that are in Gill’s complexity class BPP: perfect numbers, multiply perfect numbers, and amicable pairs. These are the first “natural” sets in BPP that are not obviously in RP.

This paper discusses some new integer factoring methods involving cyclotomic polynomials. There are several polynomials f(X) known to have the following property: given a multiple of f(p), we can quickly split any composite number that has p as a prime divisor. For example -- taking f(X) to be X- 1 -- a multiple of p - 1 will suffice to easily factor any multiple of p, using an algorithm of Pollard. Other methods (due to Guy, Williams, and Judd) make use of X + 1, X2 + 1, and X2 ± X + 1. We show that one may take f to be Φk, the k-th cyclotomic polynomial. In constrast to the ad hoc methods used previously, we give a universal construction based on algebraic number theory that subsumes all the above results. Assuming generalized Riemann hypotheses, the expected time to factor N (given a multiple E of Φk(p)) is bounded by a polynomial in k, logE, and logN.

Let N be a positive integer, and let σ(N) denote the sum of the positive integral divisors of N. We show computing σ(N) is equivalent to factoring N in the following sense: there is a random polynomial time algorithm that, given σ(N), produces the prime factorization of N, and σ(N) can be easily computed given the factorization of N.

Recent work in public-key cryptography has led to the need to generate large random numbers with known factorization.

Several results in theoretical computer science use the following theorem: