Please note: This PhD seminar will take place in DC 1304 and online.
Jesse Elliott, PhD candidate
David R. Cheriton School of Computer Science
Supervisors: Professor David Jao & Éric Schost
Modular techniques are used in algebraic algorithms to improve complexity by controlling growth of intermediate expressions. These techniques involve performing computations modulo one or several small primes thereby avoiding intermediate coefficient growth, the objective being to compute the requested output (typically, a set of polynomials, or a matrix thereof) modulo a certain large integer $M$. If $M$ is large enough, rational reconstruction can be applied coefficient-wise, in order to recover an output with rational coefficients.
One can consider working modulo a single prime $p$, solve the problem modulo $p$ and lift the solution to $\mathbb{Z}/M \mathbb{Z}$, for $M=p^k$ large enough, by means of Newton / Hensel techniques, if applicable. The obvious alternative is to compute modulo sufficiently many "small" primes $(p_i)_{1\le i \le \eta}$ and use the Chinese remainder theorem to obtain a solution modulo $M=p_1 \cdots p_\eta$.
For most problems of interest, there exist primes $p$ for which the procedure modulo $p$ is not well-defined, or returns a result that differs from the modulo $p$ reduction of the rational output; we will call these primes {\em unlucky}, and {\em lucky} otherwise. In the problems we have in mind, such as solving systems of polynomial equations, testing whether a prime is lucky may be prohibitively expensive. However, it is often possible to bound the number of unlucky primes: this is usually done by proving the existence of a nonzero $U \in \mathbb{Z}$ such that all unlucky primes divide $U$, and bounding the height of $U$.
Using $p$-adic lifting techniques, we need to ensure that the initial prime $p$ is lucky; knowing the upper bound on $U$, we can determine what interval to pick $p$ from in order to guarantee a high probability of success, say at least $1-\varepsilon$ for a given tolerance $\varepsilon$. For Chinese remaindering algorithms, though, the direct approach requires that all primes are lucky, where providing a guarantee with probability $1-\varepsilon$ usually requires us to use larger primes.
We report on work-in-progress that uses error correction techniques, where we tolerate a few primes to return wrong results (or no results at all). Our hope is then to be able to guarantee high probability of success, while using primes of moderate size.
While techniques involving CRT and error correction are well-established, the consequences we derive, to our knowledge, despite being relatively straightforward, are new. We provide a quantitative analysis which gives explicit sufficient conditions on the number of primes and their size to guarantee an arbitrary probability of success, in a model where we assume we can pick primes uniformly at random in a given interval. We also describe a number of applications.
To attend this seminar, please head to DC 1304. You can also attend it virtually through Zoom.