[發(fā)明專利]基于密碼學(xué)技術(shù)應(yīng)用的大數(shù)快速分解方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201210197737.8
• 申請(qǐng)日: 2012-06-15
• 公開(kāi)（公告）號(hào): CN102769528A
• 公開(kāi)（公告）日: 2012-11-07
• 發(fā)明（設(shè)計(jì)）人: 劉詩(shī)章;陳豫生;賀漫古
• 申請(qǐng)（專利權(quán)）人: 劉詩(shī)章;陳豫生;賀漫古
• 主分類號(hào): H04L9/30
• 分類號(hào): H04L9/30;G06F7/72
• 代理公司: 北京華夏博通專利事務(wù)所(普通合伙) 11264
• 代理人: 劉俊

1.一種基于密碼學(xué)技術(shù)應(yīng)用的大數(shù)快速分解方法：其分解步驟如下：

步驟1，壓縮正整數(shù)，建立模M＝30的縮剩余系。選取M＝30為模，求其對(duì)正整數(shù)的同余類，并做出其縮剩余系，由Euler函數(shù)：

得到：從而可形成八個(gè)等差數(shù)列；

步驟2，建立素?cái)?shù)族，在與模M＝30互素的八類中各取出一個(gè)代表數(shù)a₁，，…，a₈，它們依次為：

1、7、11、13、17、19、23、29；

于是7以上的素?cái)?shù)p均可用模M＝30的縮剩余系表出，即：

P=a1···a8(mod30);]]>

本發(fā)明將上式表示的全部數(shù)值定義為殆素?cái)?shù)族，并記作Kp，于是有：

Kp＝a+30(n-1)；

其中：n≥1，a＜30、且(a，30)＝1；

步驟3，根據(jù)計(jì)算機(jī)存儲(chǔ)空間的許可和實(shí)際需要，可選定30n為最大取值范圍；

步驟4，生成殆素?cái)?shù)族Kp₁，Kp₂，…，Kp_s，其中，Kp_s≤30n-1；

步驟5，將擬分解的大數(shù)M代入公式：Kp＝a+30(n-1)，

即：M＝a+30(n-1)；

從而可找出該數(shù)值M在殆素?cái)?shù)表中的確定位置，即所在列(n)和行(a)的位置；

步驟6，將該數(shù)位進(jìn)行設(shè)定，即當(dāng)計(jì)算機(jī)執(zhí)行刪除程序并刪除到該數(shù)位時(shí)，程序能夠自動(dòng)停止并發(fā)出提示；

步驟7，采用刪除法，刪除殆素?cái)?shù)族中的合數(shù)；按照殆素?cái)?shù)族Kp₁，Kp₂，…，Kp_m的數(shù)值大小(其中)，依次進(jìn)行如下操作：根據(jù)含Kp_i因子的合數(shù)的分布特點(diǎn)，將含Kp_i因子的合數(shù)全部刪除，直至要選擇的范圍30n；

步驟8，當(dāng)刪除操作運(yùn)行到刪除數(shù)值M所在位置時(shí)，程序自動(dòng)停止運(yùn)行并發(fā)出提示；

步驟9，程序停止前正執(zhí)行的是刪除某素因子合數(shù)的操作，該素因子即為數(shù)值M的因子；

步驟10，將其另一個(gè)因子也按上述方法處理，直至確認(rèn)它也是素因子為止。

2.如權(quán)利要求1所述基于密碼學(xué)技術(shù)應(yīng)用的大數(shù)快速分解方法應(yīng)用于信息安全和密碼學(xué)技術(shù)應(yīng)用領(lǐng)域。