因子分解

因子分解，將給定的合數分解為素數的乘積。對於較小的正整數可藉助於素數表用試除的方法求出其因子分解式。對於大整數，有許多快速分解方法，如連分數方法、類群方法、橢圓曲線方法、二次篩法及數域篩法等。套用它們藉助於現代計算機可以得到不少大數分解式。

基本介紹

• 中文名：因子分解
• 定義：將給定的合數分解為素數的乘積

歷史

1995年R.P.布倫特套用橢圓曲線方法求出第10個費馬數的分解式F10＝2210＋1＝21 024＋1＝45 592 577×6 487 031 809×p40×p252，式中p40和p252分別是40位和252位素數。

1998年J.楊通過計算找到費馬數F303 088有因子3×2303 093＋1。大數分解與素數判定緊密相關，在公鑰密碼中有實際套用。