Source author record

Eric Bach

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NT quant-ph Data Structures and Algorithms math.GR physics.soc-ph Symbolic Computation

Catalog footprint

Research overview

10works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Algorithms to Uniformly Generate Random Factored Smooth Integers

Let $x\ge y>0$ be integers. A positive integer is $y$ -smooth if all its prime divisors are at most $y$ . Let $Ψ(x,y)$ count the number of $y$ -smooth integers up to $x$ . We present several algorithms that will generate an integer $n\le x$ at random, with known prime factorization, such that $n$ is $y$ -smooth. We begin by describing algorithms to compute $Ψ(x,y)$ exactly and to enumerate $y$ -smooth integers up to $x$ in lexicographic order by prime divisor. Both of these are based on Buchstab's identity, and were likely known before. Then we present an algorithm that accepts as input a parameter $r$ , $0\le r<1$ , and returns the integer $n$ that is at position $\lfloor rΨ(x,y)\rfloor$ in the lexicographic ordering of all $y$ -smooth integers up to $x$ . Here position 0 is the first position. Thus, $n$ is generated uniformly so long as $r$ is chosen uniformly. This algorithm has a running time of $O(Ψ(x,y)\log\log y)$ arithmetic operations. We then explore the tradeoff between speed and rigor. By relaxing the uniformity of the output and allowing for multiple heuristics in our runtime analysis, we improve the running time to $O\left( \frac{ (\log x)^3 }{\log\log x} \right)$ arithmetic operations. We conclude with a sample run by generating a $10000$ -smooth integer $\le 10^{100}$ .

preprint2016arXiv

Baby-Step Giant-Step Algorithms for the Symmetric Group

We study discrete logarithms in the setting of group actions. Suppose that $G$ is a group that acts on a set $S$ . When $r,s \in S$ , a solution $g \in G$ to $r^g = s$ can be thought of as a kind of logarithm. In this paper, we study the case where $G = S_n$ , and develop analogs to the Shanks baby-step / giant-step procedure for ordinary discrete logarithms. Specifically, we compute two sets $A, B \subseteq S_n$ such that every permutation of $S_n$ can be written as a product $ab$ of elements $a \in A$ and $b \in B$ . Our deterministic procedure is optimal up to constant factors, in the sense that $A$ and $B$ can be computed in optimal asymptotic complexity, and $|A|$ and $|B|$ are a small constant from $\sqrt{n!}$ in size. We also analyze randomized "collision" algorithms for the same problem.

preprint2015arXiv

Infinitely Many Carmichael Numbers for a Modified Miller-Rabin Prime Test

We define a variant of the Miller-Rabin primality test, which is in between Miller-Rabin and Fermat in terms of strength. We show that this test has infinitely many "Carmichael" numbers. We show that the test can also be thought of as a variant of the Solovay-Strassen test. We explore the growth of the test's "Carmichael" numbers, giving some empirical results and a discussion of one particularly strong pattern which appears in the results.

preprint2013arXiv

Counting composites with two strong liars

The strong probable primality test is an important practical tool for discovering prime numbers. Its effectiveness derives from the following fact: for any odd composite number $n$ , if a base $a$ is chosen at random, the algorithm is unlikely to claim that $n$ is prime. If this does happen we call $a$ a liar. In 1986, Erdős and Pomerance computed the normal and average number of liars, over all $n \leq x$ . We continue this theme and use a variety of techniques to count $n \leq x$ with exactly two strong liars, those being the $n$ for which the strong test is maximally effective. We evaluate this count asymptotically and give an improved algorithm to determine it exactly. We also provide asymptotic counts for the restricted case in which $n$ has two prime factors, and for the $n$ with exactly two Euler liars.

preprint2013arXiv

On the Number of Distinct Functional Graphs of Affine-Linear Transformations over Finite Fields

We study the number of non-isomorphic functional graphs of affine-linear transformations from (\F_q)^n to itself, and we prove upper and lower bounds on this quantity for n large. As a corollary to our result, we prove bounds on the number of conjugacy classes in the symmetric group S_{q^n} that intersect AGL_n(q).

preprint2012arXiv

Comparing algorithms for graph isomorphism using discrete- and continuous-time quantum random walks

Berry and Wang [Phys. Rev. A {\bf 83}, 042317 (2011)] show numerically that a discrete-time quantum random walk of two noninteracting particles is able to distinguish some non-isomorphic strongly regular graphs from the same family. Here we analytically demonstrate how it is possible for these walks to distinguish such graphs, while continuous-time quantum walks of two noninteracting particles cannot. We show analytically and numerically that even single-particle discrete-time quantum random walks can distinguish some strongly regular graphs, though not as many as two-particle noninteracting discrete-time walks. Additionally, we demonstrate how, given the same quantum random walk, subtle differences in the graph certificate construction algorithm can nontrivially impact the walk's distinguishing power. We also show that no continuous-time walk of a fixed number of particles can distinguish all strongly regular graphs when used in conjunction with any of the graph certificates we consider. We extend this constraint to discrete-time walks of fixed numbers of noninteracting particles for one kind of graph certificate; it remains an open question as to whether or not this constraint applies to the other graph certificates we consider.

preprint2012arXiv

Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs

We investigate the quantum dynamics of particles on graphs ("quantum random walks"), with the aim of developing quantum algorithms for determining if two graphs are isomorphic (related to each other by a relabeling of vertices). We focus on quantum random walks of multiple non-interacting particles on strongly regular graphs (SRGs), a class of graphs with high symmetry that is known to have pairs of graphs that are hard to distinguish. Previous work has already demonstrated analytically that two-particle non-interacting quantum walks cannot distinguish non-isomorphic SRGs of the same family. Here, we demonstrate numerically that three-particle non-interacting quantum walks have significant, but not universal, distinguishing power for pairs of SRGs, proving a fundamental difference between the distinguishing power of two-particle and three-particle non-interacting walks. We analytically show why this distinguishing power is possible, whereas it is forbidden for two-particle non-interacting walks. Based on sampling of SRGs with up to 64 vertices, we find no difference in the distinguishing power of bosonic and fermionic walks. In addition, we find that the four-fermion non-interacting walk has greater distinguishing power than the three-particle walks on SRGs, showing that increasing particle number increases distinguishing power. However, we also analytically show that no non-interacting walk with a fixed number of particles can distinguish all SRGs, thus demonstrating a potential fundamental difference between the distinguishing power of interacting and noninteracting walks.

preprint2012arXiv

Power law scaling for the adiabatic algorithm for search engine ranking

An important method for search engine result ranking works by finding the principal eigenvector of the "Google matrix." Recently, a quantum algorithm for preparing this eigenvector and evidence of an exponential speedup for some scale-free networks were presented. Here, we show that the run-time depends on features of the graphs other than the degree distribution, and can be altered sufficiently to rule out a general exponential speedup. For a sample of graphs with degree distributions that more closely resemble the Web than in previous work, the proposed algorithm for eigenvector preparation does not appear to run exponentially faster than the classical case.

preprint2010arXiv

Threshold rules for online sample selection

We consider the following sample selection problem. We observe in an online fashion a sequence of samples, each endowed by a quality. Our goal is to either select or reject each sample, so as to maximize the aggregate quality of the subsample selected so far. There is a natural trade-off here between the rate of selection and the aggregate quality of the subsample. We show that for a number of such problems extremely simple and oblivious "threshold rules" for selection achieve optimal tradeoffs between rate of selection and aggregate quality in a probabilistic sense. In some cases we show that the same threshold rule is optimal for a large class of quality distributions and is thus oblivious in a strong sense.

preprint2009arXiv

Absorption Probabilities for the Two-Barrier Quantum Walk

Let p_j^(n) be the probability that a Hadamard quantum walk, started at site j on the integer lattice {0,...,n}, is absorbed at 0. We give an explicit formula for p_j^(n). Our formula proves a conjecture of John Watrous, concerning an empirically observed linear fractional recurrence relation for the numbers p_1^(n).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Eric Bach

Research overview

Is this your work?

10 publications

Algorithms to Uniformly Generate Random Factored Smooth Integers

Baby-Step Giant-Step Algorithms for the Symmetric Group

Infinitely Many Carmichael Numbers for a Modified Miller-Rabin Prime Test

Counting composites with two strong liars

On the Number of Distinct Functional Graphs of Affine-Linear Transformations over Finite Fields

Comparing algorithms for graph isomorphism using discrete- and continuous-time quantum random walks

Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs

Power law scaling for the adiabatic algorithm for search engine ranking

Threshold rules for online sample selection

Absorption Probabilities for the Two-Barrier Quantum Walk

See the researcher in context

Building this map preview