<p>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.</p>

<p>$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?</p>

<p>$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?</p>

<p>Link <a href="https://mathoverflow.net/questions/258467/existence-of-randomized-polynomial-time-algorithm-and-some-arithmetic-analog-of/258477?noredirect=1#comment637557_258477">https://mathoverflow.net/questions/258467/existence-of-randomized-polynomial-time-algorithm-and-some-arithmetic-analog-of/258477?noredirect=1#comment637557_258477</a>.</p>

<p>$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 <a href="https://www.nada.kth.se/~johanh/algnotes.pdf" rel="nofollow noreferrer">https://www.nada.kth.se/~johanh/algnotes.pdf</a> which might put the decision version in here to be in $ACC^0$.</p>

<p>Refer algorithm 10 and theorem 2 here <a href="http://www.mmrc.iss.ac.cn/~lzhi/Course/mchapter15.ps" rel="nofollow noreferrer">http://www.mmrc.iss.ac.cn/~lzhi/Course/mchapter15.ps</a>.</p>

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

CC BY-SA 3.0
2017-01-01T13:37:32.683Z
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
CC BY-SA 3.0
2017-01-01T13:45:30.553Z
@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$.
Turbo
CC BY-SA 3.0
2017-01-01T14:03:13.433Z
So it's actually an analogue of AC^i, not ACC^i.
Emil Jeřábek
CC BY-SA 3.0
2017-01-01T14:07:25.030Z
I see.. so there cannot be any reasonable analog of ACC^i? I think what I say as arithmetic circuit is regularly used in literature as arithmetic circuit. In any case I removed the arithmetic analog part.
Turbo
CC BY-SA 3.0
2017-01-01T14:47:43.500Z
I didn't say there cannot be a reasonable analogue. I said that it is not off-hand clear what it should be, so I asked you for clarification. I find it extremely odd that you ask questions involving symbols that you yourself don't know how to attach a meaning to.
Emil Jeřábek
CC BY-SA 3.0
2017-01-01T21:16:57.937Z
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
CC BY-SA 3.0
2017-01-01T23:14:24.250Z
@SashoNikolov just trying to understand what the smallest known complexity classes for decision version of these problems are using the known algorithms (updated to decision versions in main post).
Turbo
CC BY-SA 3.0
2017-01-02T07:05:21.237Z
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
CC BY-SA 3.0
2017-01-03T04:44:55.787Z
@JoshuaGrochow I just figured how to portray in Boolean complexity terms. Also back in arithmetic complexity terms I think LLL has log n depth while Zassenhaus' has only constant depth (modulo the Hensel part which is unclear to me). Is this right?
Turbo
<cc.complexity-theory><complexity-classes><circuit-complexity><polynomials><factoring>
Circuit complexity class of polynomial factoring and Hensel lifting in Zassenhaus' algorithm?
Turbo
# Circuit complexity class of polynomial factoring and Hensel lifting in Zassenhaus' algorithm?

(Asked by: username_0 on 2016-12-31)

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?

Link <https://mathoverflow.net/questions/258467/existence-of-randomized-polynomial-time-algorithm-and-some-arithmetic-analog-of/258477?noredirect=1#comment637557_258477>.

$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?

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, polynomials, factoring

> **Comments:**
> **username_1**: What do you mean by an "arithmetic analog of ACC^0"? What's supposed to be the arithmetic analogue of modular counting gates?  
> **username_0**: @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$.  
> **username_1**: So it's actually an analogue of AC^i, not ACC^i.  
> **username_0**: I see.. so there cannot be any reasonable analog of ACC^i? I think what I say as arithmetic circuit is regularly used in literature as arithmetic circuit. In any case I removed the arithmetic analog part.  
> **username_1**: I didn't say there cannot be a reasonable analogue. I said that it is not off-hand clear what it should be, so I asked you for clarification. I find it extremely odd that you ask questions involving symbols that you yourself don't know how to attach a meaning to.  
> **username_2**: 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.  
> **username_0**: @SashoNikolov just trying to understand what the smallest known complexity classes for decision version of these problems are using the known algorithms (updated to decision versions in main post).  
> **username_3**: 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.  
> **username_0**: @JoshuaGrochow I just figured how to portray in Boolean complexity terms. Also back in arithmetic complexity terms I think LLL has log n depth while Zassenhaus' has only constant depth (modulo the Hensel part which is unclear to me). Is this right?  

---

## 0 answers

