互質和秀爾演算法

快捷方式: 差异，相似，杰卡德相似系数，参考。

互質和秀爾演算法之间的区别

互質 vs. 秀爾演算法

互质（英文：coprime，符號：⊥，又稱互素、relatively prime、mutually prime、co-prime）。在數論中，如果兩個或兩個以上的整數的最大公因數是 1，則稱它們為互质。依此定義：. 演算法（Shor算法），以數學家彼得·秀爾命名，是一個在1994年發現的，針對整數分解這題目的的量子演算法（在量子計算機上面運作的演算法）。比較不正式的說，它解決題目如下：給定一個整數N，找出他的質因數。 在一個量子計算機上面，要分解整數N，秀爾演算法的運作需要多項式時間（時間是log N的某個多項式這麼長，log N在這裡的意義是輸入的檔案長度）。更精確的說，這個演算法花費的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類BQP裡面。這比起傳統已知最快的因數分解演算法，普通數域篩選法，其花費次指數時間 -- 大約，還要快了一個指數的差異。 秀爾演算法非常重要，因為它代表使用量子計算機的話，我們可以用來破解已被廣泛使用的公開密鑰加密方法，也就是RSA加密演算法。RSA演算法的基礎在於假設了我們不能很有效率的分解一個已知的整數。就目前所知，這假設對傳統的（也就是非量子）電腦為真；沒有已知傳統的演算法可以在多項式時間內解決這個問題。然而，秀爾演算法展示了因數分解這問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於建立量子計算機和研究新的量子計算機演算法，是一個非常大的動力。 在2001年，IBM的一個小組展示了秀爾演算法的實例，使用NMR實驗的量子計算機，以及7個量子位元，將15分解成3×5。.

輾轉相除法

在数学中，辗转相除法，又称欧几里得算法（Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（）；因为，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如。这个重要的結論叫做貝祖定理。 辗转相除法最早出现在欧几里得的《几何原本》中（大约公元前300年），所以它是现行的算法中歷史最悠久的。这个算法原先只用来处理自然数和几何长度（相當於正實數），但在19世纪，辗转相除法被推广至其他类型的數學對象，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。 辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。 辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的五倍。拉梅于1844年证明了这点，同時這也標誌著计算复杂性理论的開端。.

互質和輾轉相除法 · 秀爾演算法和輾轉相除法 · 查看更多 »

最大公因數

数学中，兩個或多個整數的最大公因數（greatest common factor，hcf）指能够整除这些整数的最大正整数（这些整数不能都为零）。例如8和12的最大公因数为4。最大公因数也称最大公约数（greatest common divisor，gcd）。 整数序列a的最大公因数可以記為(a_1, a_2, \dots, a_n)或\gcd(a_1, a_2, \dots, a_n)。 求兩個整數最大公因數主要的方法：.

互質和最大公因數 · 最大公因數和秀爾演算法 · 查看更多 »