Under the auspices of the Computational Complexity Foundation (CCF)

TR12-014 | 20th February 2012
Johannes Mittmann, Nitin Saxena, Peter Scheiblechner

#### Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

A set of multivariate polynomials, over a field of zero or large characteristic, can be tested for algebraic independence by the well-known Jacobian criterion. For fields of other characteristic \$p>0\$, there is no analogous characterization known. In this paper we give the first such criterion. Essentially, it boils down to ... more >>>

TR19-008 | 20th January 2019
Ashish Dwivedi, Rajat Mittal, Nitin Saxena

#### Efficiently factoring polynomials modulo \$p^4\$

Polynomial factoring has famous practical algorithms over fields-- finite, rational \& \$p\$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, \$x^2+p \bmod p^2\$ is irreducible, but \$x^2+px \bmod p^2\$ has exponentially many factors! We present the first randomized poly(\$\deg ... more >>>

ISSN 1433-8092 | Imprint