Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PRIME-POWER:
Reports tagged with prime-power:
TR19-008 | 20th January 2019
Ashish Dwivedi, Rajat Mittal, Nitin Saxena

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 >>> TR19-033 | 20th February 2019 Ashish Dwivedi, Rajat Mittal, Nitin Saxena #### Counting basic-irreducible factors mod$p^k$in deterministic poly-time and$p$-adic applications Finding an irreducible factor, of a polynomial$f(x)$modulo a prime$p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of$f\bmod p$. We can ask the same question modulo prime-powers$p^k\$. The irreducible ... more >>>

ISSN 1433-8092 | Imprint