问题一：在GF(p)上求多项式的根。据我所知，目前没找到确定性多项式算法，但有很多随机多项式算法。目前猜测，如果此多项式有可交换的Galois群，那可以在多项式时间分解。
问题二：在GF(p)上分解多项式。同样，这不会比问题一容易。目前有很多随机多项式算法或是实际性能不错的方法。
问题三：在Z上分解多项式。有趣的是，这个问题要比Z上的大整数分解容易得多（因此基于多项式分解的RSA体制是没用处的。）。1982年由Lenstra,A.K.，Lenstra.Jr.H.W.和Lovasz,L.提出的著名的LLL算法证明这个问题是属于P类。证明了其复杂性为O(n^12+n^9(log|f|^3)),n为f的次数。但由于它确实很慢，实际上从没有人真正用它来分解因式。

在GF(p)上，一个比较实用的算法如下：
设输入多项式为A.
1.[Squarefree Factorization] 将A变换成A1*(A2^2)*(A3^3)……。A1,A2……都无平方因子，且互素。
2.[Distinct degree factorization] 对步骤1中算出的每个Ai，找出A(i.d)——A的所有d次素因子的乘积。
3.[Final splittings] 将A(i,d)分解为多个d次因子。
4.[Cleanup]

在Z上，可以借助前面算法去设计一些方法，还是比较复杂。