# Circuit complexity class of polynomial factoring and Hensel lifting in Zassenhaus' algorithm?

Given a primitive polynomial (gcd of coefficients is $1$) in $\Bbb Z[x]$ we have a polynomial time factoring algorithm for this that runs in time polynomial in degree $d$ and number of bits in coefficients. This is the Lenstra-Lenstra-Lovasz algorithm.

$1$. Arrange members of $\Bbb Z[x]$ with some bound on coefficients in some order. If I ask if the $t$th factor has $j$th bit in $i$th coefficient a $1$ is this algorithm known to give an $ACC^0$ circuit?

$2$. What is the smallest complexity class for the same query as $1$ if I say I only need at least in a randomized sense and for an algorithm that factors only a constant fraction of primitive polynomials?

$3$. Consider the overall Hensel lifting step in Zassenhaus' algorithm. If I ask is the $i$th digit has $j$th bit $1$ when lifting to $p^t$ can we have an $ACC^0$ circuit? Hensel lifting is just reading $p$-adic digits and may be this step is in $ACC^0$? If so Zassenhaus' algorithm would give $ACC^0$ circuit for thus answering $2$. There is a linear system interpretation here in section 8.1.2 https://www.nada.kth.se/~johanh/algnotes.pdf which might put the decision version in here to be in $ACC^0$.

Refer algorithm 10 and theorem 2 here http://www.mmrc.iss.ac.cn/~lzhi/Course/mchapter15.ps.

Please also check corollary $1.79$ here http://compalg.inf.elte.hu/~tony/KedvencKonyvek/InfoKonyvtar/03-Algorithms%20of%20Informatics%201,%202,%203/AlgofInfVol1Oct24.pdf for a log depth implementation of Hensel Lifting. Can it be reduced to constant depth?

• What do you mean by an "arithmetic analog of ACC^0"? What's supposed to be the arithmetic analogue of modular counting gates? – Emil Jeřábek supports Monica Jan 1 '17 at 13:37
• @EmilJeřábek sorry this is what I mean. I just want $O(\log^i n)$ depth and polynomial size of circuit with ring operations as gates for the arithmetic analog of $ACC^i$. – T.... Jan 1 '17 at 13:45
• So it's actually an analogue of AC^i, not ACC^i. – Emil Jeřábek supports Monica Jan 1 '17 at 14:03
• What's with all the "is this algorithm in ACC0?" questions? Maybe it would help to give some sense about what you are getting at with all of them. – Sasho Nikolov Jan 1 '17 at 21:16
• NB: For poly-size circuits consisting only of ring operations (more traditionally known as "arithmetic circuits" or "algebraic circuits"), they can always be reduced to $O(\log^2 n)$ depth while maintaining poly-size. Also, your new edits to the question conflict with your earlier comment to Emil, since your (updated) question really is asking about bit complexity, not algebraic complexity. – Joshua Grochow Jan 2 '17 at 7:05