整數分解（英語：integer factorization）又称整数因式分解、整数因子分解，或整数因子化，在数论中，“整数的因数分解”是指在可能的情况下，将一个正整数分解为更小整数的乘积，即寫成幾個因數的乘積。若进一步限制因数为质数，则这个过程称为质因数分解（英語：prime...

(3+1)\times (2+1)=24} 。 自然数N的正因数和，以因数函数 σ ( N ) {\displaystyle \sigma (N)} 表示。由质因数分解而得。 若 N {\displaystyle N} 唯一分解为 N = p 1 a 1 × p 2 a 2 × p 3 a 3 ×...

Cocks）在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。 對极大整数做因数分解的難度決定了 RSA 算法的可靠性。換言之，對一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的...

因数的乘积。兩個沒有共同質因子的正整數稱為互質。因為1沒有質因子，1與任何正整數（包括1本身）都是互質。只有一個質因子的正整數為質數。 将一个正整数表示成质因数乘积的过程和得到的表示结果叫做质因数分解。显示质因数分解结果时，如果其中某个质因数出现了不止一次，可以用幂次的形式表示。例如360的质因数分解是：...

{\displaystyle A=QR} 其中Q是正交矩阵（意味着QTQ = I）而R是上三角矩阵。如果A是非奇异的，且限定R的对角线元素为正，则这个因数分解是唯一的。 更一般的说，我们可以因数分解复数 m {\displaystyle m} × n {\displaystyle n} 矩阵（有着m ≥ n）为 m {\displaystyle...

{\displaystyle {\frac {60}{12}}=5} ）。 可以通过質因數分解来计算最大公因数。例如计算 gcd ( 18 , 84 ) {\displaystyle \gcd(18,84)} ，可以先进行质因数分解 18 = 2 × 3 2 {\displaystyle 18=2\times...

{\displaystyle 1\times 3} 、 1 × 1 × 3 {\displaystyle 1\times 1\times 3} 等都是3的有效因數分解）。 古希臘數學家欧几里得於公元前300年前後證明有無限多個質數存在（欧几里得定理）。現時人們已發現多種驗證質數的方法。其中试除法比較簡單，但需時較長：設被測試的自然數為...

× 23，合數360可以寫成23 × 32 × 5，而且若將質因數依大小排列後，此表示法是唯一的。這是算术基本定理。 有許多的素性测试可以在不進行因數分解的情形下，判斷一數字是質數還是合數。 所有大於2的偶數都是合數，也就是在正整數中除了2以外，其餘數的個位數為0、2、4、6、8者均為合數。4為最小的合數。...

因數分解以及離散對數的公開密鑰加密算法（比如RSA加密演算法， 迪菲-赫尔曼密鑰交換，橢圓曲線加密）。RSA演算法的基礎在於假設了我們不能有效率的分解一個已知的整數。就目前所知，這假設對傳統（即非量子）的電腦為真；沒有已知的傳統演算法可以在多項式時間內解決這個問題。但秀爾演算法展示了因數分解...

{\displaystyle p-q|f(1)} p + q | f ( − 1 ) {\displaystyle p+q|f(-1)} 因数分解 高斯整數分解 多項式 根 十字相乘 乘法公式 也有polynomial factorisation或factoring的用法 因式即多項式。 Burnside...

number），或译脆数，是一個可以因數分解為小質數乘積的正整數。光滑數一詞是是伦纳德·阿德曼所提出。光滑數在以因數分解為基礎的密码学中扮演重要角色。 若一正整數的質因數均不大於B，此整數即為B-光滑數。例如1620的因數分解為22 × 34 × 5，質因數均不大於5，因此1620是5-光滑數。 10和12的因數分解分別為2...

{White}1}3^{\color {White}3}7.^{\color {White}2}5\\\end{array}}} 常常需要將數字分解為質因數的乘積（因數分解）。作法是先找到數字的質因數，再將數字除以其質因數，一直到所得的數字為另一個質數為止。 2 ) 950 _ 5 ) 475 _ 5 ) 19...

500是499与501之间的自然数。 合數，正因數有1、2、4、5、10、20、25、50、100、125、250和500。 質因數分解為 2 2 × 5 3 {\displaystyle 2^{2}\times 5^{3}} 。 過剩數，真因數和為592，盈度為92。 半完全數，和為本身的其中一組因數為1、 4、 20、...

分解大半素数则比较困难。简单的来说，虽然35很容易就可以被分解成5×7，但是要想分解很大的半素数就不是那么容易了。RSA加密演算法中有一個稱為RSA-2048的半素数，有2,048位元，十進位有617位，RSA曾經公開懸賞200,000美元，給予成功將RSA-2048因數分解...

合數，正因數有1、2、4、5、8、10、20、25、40、50、100、125、200、250、500和1000。 質因數分解為 2 3 × 5 3 {\displaystyle 2^{3}\times 5^{3}} 。 過剩數，真因數和為1340，盈度為340。 半完全數，和為本身的其中一組因數為1、...

特別地，1這個數稱為單位，沒有質因數，既不是質數也不是合數。此外，0不在可因數分解的整數的範圍內，因為任意質數皆為零的因數。 自然數的許多性質可以從其質因數分解觀察到或計算得到。 某數的某個質因數的冪數，是該質數冪可以整除該數的最大冪次。即n有質因數p，若p的冪數是...

400是399與401之間的自然數。 合數，正因數有1、2、4、5、8、10、16、20、25、40、50、80、100、200和400。 質因數分解為 2 4 × 5 2 {\displaystyle 2^{4}\times 5^{2}} 。 第96個過剩數，真因數和為561，盈度為161。前一個為396、下一個為402。...

\therefore a} 為0的因數，0為 a {\displaystyle a\,\!} 的倍數，也就是說，任何整數都是0的因數。 另外，因为0不能作为任何数的因数，所以0没有倍数。 在計算機科學中，0經常用於表示布尔值假（F）。 在数位电路中，不使用精确的电压值来代表信号的值，只使用「0」和「1」两个值。「0...

第19個合數，正因數有1、2、3、5、6、10、15和30。前一個為28、下一個為32。 質因數分解為 2 × 3 × 5 {\displaystyle 2\times 3\times 5} 。 第5個過剩數，真因數和為42，盈度為12。前一個為24、下一個為36。 第7個半完全數，和為本身的其中一組因數為1、...

= ax+by，其中x和y都是整数，并且a和b的每一个公因数都能整除这个d。d的绝对值叫做最大公因数，记为 gcd ( a , b ) {\displaystyle \gcd(a,b)} 。 在日常语言中，公约数也用来表示几个人不同观点中相同的部分。 因数分解 最大公因數 公倍數...

100（一百）是99与101之间的自然数。 第74個合數，正因數有1、2、4、5、10、20、25、50和100。前一個為99、下一個為102。 質因數分解為 2 2 × 5 2 {\displaystyle 2^{2}\times 5^{2}} 。 第22個過剩數，真因數和為117，盈度為17。前一個為96、下一個為102。...

22（二十二）是21与23之间的自然数。 第13個合數，正因數有1、2、11和22。前一個為21、下一個為24。 質因數分解為 2 × 11 {\displaystyle 2\times 11} 。 第18個虧數，真因數和為14，虧度為8。前一個為21、下一個為23。...

300是299與301之間的自然數。 合數，正因數有1、2、3、4、5、6、10、12、15、20、25、30、50、60、75、100、150和300。 質因數分解為 2 2 × 3 × 5 2 {\displaystyle 2^{2}\times 3\times 5^{2}} 。...

第10個合數，正因數有1、2、3、6、9和18。前一個為16、下一個為20。 質因數分解為 2 × 3 2 {\displaystyle 2\times 3^{2}} 。 第2個過剩數，真因數和為21，盈度為3。前一個為12、下一個為20。 第3個半完全數，和為本身的其中一組因數為1、 2、 6、...

25（二十五）是24与26之间的自然数。 第15個合數，正因數有1、5和25。前一個為24、下一個為26。 質因數分解為 5 2 {\displaystyle 5^{2}} 。 第20個虧數，真因數和為6，虧度為19。前一個為23、下一個為26。 第9個半質數。前一個為22、下一個為26。...

第11個合數，正因數有1、2、4、5、10和20。前一個為18、下一個為21。 質因數分解為 2 2 × 5 {\displaystyle 2^{2}\times 5} 。 第3個過剩數，真因數和為22，盈度為2。前一個為18、下一個為24。 第4個半完全數，和為本身的其中一組因數為1、 4、 5、...

椭圆曲线数字签名算法（ECDSA） 对于ECC系统来说，完成运行系统所必须的群操作比同样大小的因数分解系统或模整数离散对数系统要慢。不过，ECC系统的拥护者相信ECDLP问题比DLP或因数分解问题要难的多，并且因此使用ECC能用小的多的密钥长度来提供同等的安全，在这方面来说它确实比例如RSA...

合數，正因數有1、2、3、6、37、74、111和222。 質因數分解為 2 × 3 × 37 {\displaystyle 2\times 3\times 37} 。 第52個過剩數，真因數和為234，盈度為12。前一個為220、下一個為224。 第53個半完全數，和為本身的其中一組因數為37、...

{a_{1}a_{2}}{\gcd(a_{1},a_{2})}}} 来求解，这时首先要知道它们的最大公因数。而最大公因数可以通过短除法得到。 利用整数的唯一分解定理，还可以用質因數分解法。将每个整数进行质因数分解。对每个质数，在质因数分解的表达式中寻找次数最高的乘幂，最后将所有这些质数乘幂相乘就可以得到最小公倍数。譬如...

6,12,18,24,30,36,42,48,54,60,66,72,...} 4和6的公倍數為同時為4和6的倍數的數： 12 , 24 , 36 , 48 , 60 , 72 , . . . {\displaystyle 12,24,36,48,60,72,...} 因数分解 最小公倍數 公因數...

数到每个可计算函数作为在这种编程语言中计算这个函数的值的程序。Roger 等价定理特征化了是哥德尔编号的可计算函数集合的编号。 哥德尔使用基于素数因数分解的哥德尔编码系统。他首先把唯一的自然数指派到在他所处理的算术的形式语言中的每个基本符号。 为了编码是符号序列的整个公式，哥德尔使用了如下系统。给出正整数的序列...