快速檢驗(yàn)梅森素?cái)?shù)的一種新方法

林柏鋼

(1. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350116；2. 網(wǎng)絡(luò)系統(tǒng)信息安全福建省高校重點(diǎn)實(shí)驗(yàn)室，福建 福州 350116)

快速檢驗(yàn)梅森素?cái)?shù)的一種新方法

林柏鋼1,2

(1. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350116；2. 網(wǎng)絡(luò)系統(tǒng)信息安全福建省高校重點(diǎn)實(shí)驗(yàn)室，福建 福州 350116)

研究梅森素?cái)?shù)與偶完全數(shù)的內(nèi)在聯(lián)系，分析偶完全數(shù)因子分解的結(jié)構(gòu)特點(diǎn)，分別得到一個準(zhǔn)偶完全數(shù)序列的通項(xiàng)公式：Sn=22n-2·(22n-1-1)，和一個準(zhǔn)梅森素?cái)?shù)序列的通項(xiàng)公式：SMn=(22n-1-1). 最后給出快速檢驗(yàn)梅森素?cái)?shù)新方法的算法思路.

準(zhǔn)偶完全數(shù)序列； 通項(xiàng)公式； 梅森素?cái)?shù)； 快速檢驗(yàn)算法

0 引言

公鑰密碼的特點(diǎn)之一就是與素?cái)?shù)緊密相關(guān)，判定素?cái)?shù)、大數(shù)分解以及尋找最大的素?cái)?shù)，始終是人們關(guān)注的課題[1-2]. 在我們所知道的梅森素?cái)?shù)尋找過程中，如果說至今為止已找到的第48個梅森素?cái)?shù)(對應(yīng)確定的第48個偶完全數(shù))，那可是花了九牛二虎之力才取得的成果[3-4]. 也就是說，從尋找第35個梅森素?cái)?shù)開始，靠的是現(xiàn)代互聯(lián)網(wǎng)技術(shù)才得以取得突破進(jìn)展. 20世紀(jì)90年代中后期，在美國程序設(shè)計(jì)師沃特曼和庫爾沃斯基等人的共同努力下，成立了世界上第一個基于互聯(lián)網(wǎng)的分布式計(jì)算項(xiàng)目——因特網(wǎng)梅森素?cái)?shù)大搜尋(GIMPS)計(jì)劃[5-6]. 人們只要在GIMPS的主頁上下載一個計(jì)算梅森素?cái)?shù)的免費(fèi)程序，就可以立即參加該項(xiàng)目來搜尋新的梅森素?cái)?shù). 1996年11月13日，Joel Armengaud基于GIMPS平臺，找到了第35位梅森素?cái)?shù)，對應(yīng)p=1 398 269，Mp= 814 717 564…451 315 711，素?cái)?shù)有420 921位. 2013年1月25日，美國中央密蘇里大學(xué)柯蒂斯·庫珀(Curtis Cooper)教授的研究……