A method of constructing specific polynomial representations $f(x)$ over the finite field $\mathbb{F}_p$ of the square roots function modulo a prime $p = 2^kn + 1$, $n$ odd, is presented. The formulas for the cases $k = 2$, $3$ and $4$ are given.

We obtain randomized algorithms for factoring degree n univariate polynomials over $\mathbb{F}_q$ requiring $O(n^{1.5 + o(1)}\,{\rm log}^{1+o(1)} q+ n^{1 + o(1)}\,{\rm log}^{2+o(1)} q)$ bit operations. When ${\rm log}\, q < n$, this is asymptotically faster than the best previous algorithms [J. von zur Gathen and V. Shoup, Comput. Complexity, 2 (1992), pp. 187–224; E. Kaltofen and V. Shoup, Math. Comp., 67 (1998), pp. 1179–1197]; for ${\rm log}\, q \ge n$, it matches the asymptotic running time of the best known algorithms. The improvements come from new algorithms for modular composition of degree n univariate polynomials, which is the asymptotic bottleneck in fast algorithms for factoring polynomials over finite fields. The best previous algorithms for modular composition use $O(n^{(\omega + 1)/2})$ field operations, where $\omega$ is the exponent of matrix multiplication [R. P. Brent and H. T. Kung, J. Assoc. Comput. Mach., 25 (1978), pp. 581–595], with a slight improvement in the exponent achieved by employing fast rectangular matrix multiplication [X. Huang and V. Y. Pan, J. Complexity, 14 (1998), pp. 257–299]. We show that modular composition and multipoint evaluation of multivariate polynomials are essentially equivalent, in the sense that an algorithm for one achieving exponent $\alpha$ implies an algorithm for the other with exponent $\alpha + o(1)$, and vice versa. We then give two new algorithms that solve the problem near-optimally: an algebraic algorithm for fields of characteristic at most $n^{o(1)}$, and a nonalgebraic algorithm that works in arbitrary characteristic. The latter algorithm works by lifting to characteristic 0, applying a small number of rounds of multimodular reduction, and finishing with a small number of multidimensional FFTs. The final evaluations are reconstructed using the Chinese remainder theorem. As a bonus, this algorithm produces a very efficient data structure supporting polynomial evaluation queries, which is of independent interest. Our algorithms use techniques that are commonly employed in practice, in contrast to all previous subquadratic algorithms for these problems, which relied on fast matrix multiplication.

A k-query locally decodable code (LDC) encodes an n-bit message x as an N-bit codeword $C(x)$, such that one can probabilistically recover any bit $x_i$ of the message by querying only k bits of the codeword $C(x)$, even after some constant fraction of codeword bits has been corrupted. The major goal of LDC related research is to establish the optimal trade-off between length and query complexity of such codes. Recently vast improvements in upper bounds for the length of LDCs were achieved via constructions that rely on existence of certain special (“nice”) subsets of finite fields. In this work we extend the constructions of LDCs from “nice” subsets. We argue that further progress on upper bounds for LDCs via these methods is tied to progress on an old number theory question regarding the size of the largest prime factors of Mersenne numbers. Specifically, we show that every Mersenne number $m=2^t-1$ that has a prime factor $p>m^\gamma$ yields a family of $k(\gamma)$-query LDCs of length $\exp(n^{1/t})$. Conversely, if for some fixed k and all $\epsilon>0$ one can use the “nice” subsets technique to obtain a family of k-query LDCs of length $\exp(n^\epsilon)$, then infinitely many Mersenne numbers have prime factors larger than currently known.

We give an algorithm for modular composition of degree n univariate polynomials over a finite field Fqrequiring n1+o(1)log1+o(1)q bit operations; this had earlier been achieved in characteristic no(1)by Umans (2008). As an application, we obtain a randomized algorithm for factoring degree n polynomials over Fqrequiring (n1.5+o(1)+ n1+o(1)log q) log1+o(1)q bit operations, improving upon the methods of von zur Gathen & Shoup (1992) and Kaltofen & Shoup (1998). Our results also imply algorithms for irreducibility testing and computing minimal polynomials whose running times are best-possible, up to lower order terms.As in Umans (2008), we reduce modular composition to certain instances of multipoint evaluation of multivariate polynomials. We then give an algorithm that solves this problem optimally (up to lower order terms), in arbitrary characteristic. The main idea is to lift to characteristic 0, apply a small number of rounds of multimodular reduction, and finish with a small number of multidimensional FFTs. The final evaluations are then reconstructed using the Chinese Remainder Theorem. As a bonus, we obtain a very efficient data structure supporting polynomial evaluation queries, which is of independent interest. Our algorithm uses techniques which are commonly employed in practice, so it may be competitive for real problem sizes. This contrasts with previous asymptotically fast methods relying on fast matrix multiplication.