因子分解

因子分解（英语：factorization），将给定的合数分解为素数的乘积。对于较小的正整数可借助于素数表用试除的方法求出其因子分解式。对于大整数，有许多快速分解方法，如连分数方法、类群方法、椭圆曲线方法、二次筛法及数域筛法等。应用它们借助于现代计算机可以得到不少大数分解式。1995年R.P.布伦特应用椭圆曲线方法求出第10个费马数的分解式F₁₀＝2^2¹⁰＋1＝2^1 024＋1＝45 592 577×6 487 031 809×p₄₀×p₂₅₂，式中p₄₀和p₂₅₂分别是40位和252位素数。1998年J.杨通过计算找到费马数F_303 088有因子3×2^303 093＋1。大数分解与素数判定紧密相关，在公钥密码中有实际应用。