All Questions

Before LLL came along in $1982$ there was no deterministic polynomial (in degree and number of bits in coefficients) way to factor square free primitive polynomials in $\Bbb Z[x]$. However was there ...

In $\Bbb F_q[x_1,\dots,x_n]$ given $d_1,\dots,d_n\in\Bbb N$ is there a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=\max_{i\in\{1,\dots,n\}}d_i$ and $d_i=deg(...

Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$ Is this problem equivalent to any hardness results?

Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha) $ in $O(n)$ ...