因式分解與密碼

李迎新

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

數(shù)學(xué)家彼得·肖爾于1994年構(gòu)造了大數(shù)的質(zhì)因數(shù)分解算法，證明在多數(shù)情況下利用量子計(jì)算機(jī)能夠?qū)Υ髷?shù)進(jìn)行分解，從而從根本上動(dòng)搖了當(dāng)代密鑰的安全基礎(chǔ).如果量子計(jì)算使得RSA加密不再安全，那用什么來取代它呢？答案是量子密碼.

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

盧塞羅是出于實(shí)際應(yīng)用的目的開展這項(xiàng)研究的.他解釋說，目前最常見的RSA加密算法公開的最大密鑰包含600多個(gè)十進(jìn)制數(shù)字，如果利用經(jīng)典計(jì)算機(jī)和最知名的經(jīng)典算法，對(duì)這個(gè)密鑰進(jìn)行因式分解需要花費(fèi)的時(shí)間可能比宇宙的年齡還要長(zhǎng).比RSA加密更安全的量子密碼，它不僅更難被破譯，而且如果有人試圖盜取信息，它就會(huì)改變系統(tǒng)，使發(fā)送方和接收方都能夠察覺.

（作者單位：江蘇省淮安外國(guó)語學(xué)校）