多变元公钥密码等新一代密码体制在信息安全领域发挥着越来越重要的作用。本文以多变元公钥密码体制为背景，研究了有限域上多变元多项式方程组求解问题的近似算法和有限域上多变元多项式的函数分解问题。　　 本文首先引入了二次多变元多项式方程组求解的MAX-MQ优化问题，即给定有限域Fq上一组二次多变元多项式的方程组，找一组解使其满足的方程个数最多。本文证明了随机赋值方法是MAX-MQ问题的近似比为q+O(q-n/2)的多项式时间复杂度的近似算法，其中n代表变元的个数。当n较大时，这个值趋近于q。结合Hastad关于MAX-MQ问题的不可近似性的结论：对于任意小的正数ε，以近似比q-ε近似求解MAX-MQ问题是NP困难的。本文得出结论，有限域Fq上MAX-MQ问题的极小近似比是q。　　 本文还针对以“2R”密码体制为背景的函数分解问题进行了研究。对现有的以微分与齐次化思想为基础的函数分解算法给出了较为完整的理论分析，证明了叶等人提出的猜想，从而为函数分解这一有效算法提供了理论保证。本文证明了对于一组随机可分解的四次齐次多项式，基于微分的算法可以以很高的概率在多项式时间内得到它的正则的分解：当域特征为0时，这个概率是1，当域为有限域Fq并且q比较大时，这个概率接近于1。我们还提出了一个猜想，指出一组多项式的函数分解可以由它的齐次化形式的多项式的函数分解得到，并且证明了对于次数为四的多变元多项式组及一种更一般的情形该猜想以较大概率成立。最后证明了一组多项式的右分解因子可以由它的右分解空间在多项式时间内得到。　　 最后，本文还研究了一般多变元多项式的函数分解问题的不可判定性，将希尔伯特第十问题与函数分解问题联系了起来，证明了若“具有正整系数的丢番图方程是否有正整数解”这个问题是不可判定的，则一般多变元多项式的函数分解问题也是不可判定的。