因式分解與密碼

李迎新（摘編）

因式分解與密碼

李迎新（摘編）

責任編輯：沈紅艷李詩email：czsshy@126.com

在日常生活中，我們取款、上網等都需要密碼，有一種用“因式分解法”產生的密碼，方便記憶.原理是：如將多項式x4-y4進行因式分解，結果是（x+y）（x-y）（x2+y2），若取x=9、y=9，則各個因式的值是：x-y=0、x+y=18、x2+y2=162，于是就可以把“018162”作為一個六位數的密碼.大數的因式分解是網絡安全協議的核心，比如最常見的RSA加密算法.

數學家彼得·肖爾于1994年構造了大數的質因數分解算法，證明在多數情況下利用量子計算機能夠對大數進行分解，從而從根本上動搖了當代密鑰的安全基礎.如果量子計算使得RSA加密不再安全，那用什么來取代它呢？答案是量子密碼.

2012年8月20日，據物理學家組織網報道，美國加州大學圣巴巴拉分校的研究人員設計和制造了一臺量子處理器，可成功將合數15分解成3和5的乘積.雖然這只是一個最基本的質因數分解運算，但這項突破性成果是研制可進行更復雜因式分解運算的量子計算機道路上的一個里程碑，對于數字加密和網絡安全具有重要意義.該研究結果發表于《自然·物理》雜志網絡版.論文的第一作者埃里克·盧塞羅說：“15雖是一個小數字，但重要的是，我們已經證明，我們可以在一臺固態量子處理器上運行彼得·肖爾提出的質因數分解算法.這是此前從未進行過的.”

盧塞羅是出于實際應用的目的開展這項研究的.他解釋說，目前最常見的RSA加密算法公開的最大密鑰包含600多個十進制數字，如果利用經……