[發明專利]一種改進的快速生成大素數的方法在審
| 申請號： | 201510814575.1 | 申請日： | 2015-11-23 |
| 公開（公告）號： | CN105515770A | 公開（公告）日： | 2016-04-20 |
| 發明（設計）人： | 葉寧;梁成良;林巧民;王汝傳 | 申請（專利權）人： | 南京郵電大學 |
| 主分類號： | H04L9/30 | 分類號： | H04L9/30;H04L9/08 |
| 代理公司： | 南京知識律師事務所 32207 | 代理人： | 汪旭東 |
| 地址： | 210023 *** | 國省代碼： | 江蘇;32 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 一種 改進 快速 生成 素數 方法 | ||
1.一種改進的快速生成大素數的方法，其特征在于，所述方法包括如下步驟：
步驟1：首先隨機生成指定位數的大整數；
步驟1-1：定義一個數組，其中數組中的每一個元素的范圍是0～0xFFFFFFFF；
步驟1-2：以時間為隨機種子；
步驟1-3：循環隨機的產生數組中的每一個元素上的數；
步驟1-4：循環結束后，使最高位的元素與0x80000000進行按位或運算，使得產生的大 整數的最高位是1，即保證大數的位數；
步驟2：對產生的隨機大整數進行預處理：
步驟3：對步驟2中經過預處理后的大整數進行5次的Miller-Rabin算法檢測；步驟4：
如果5次都通過檢測，則該大整數就是素數，轉到步驟6；
步驟5：如果沒有通過檢測，則在該大整數數的基礎上加上預先定義的素數表 PrimeTableB[N]中的數，轉到步驟2；
步驟6：保存并輸出該大素數。
2.根據權利要求1所述的一種改進的快速生成大素數的方法，其特征在于，所述步驟2 包括如下步驟：
步驟2-1：將大整數與整數1進行按位或運算，使其為一個奇數；
步驟2-2：判斷其奇數能否被整數5整除；
步驟2-3：如果能，則在其奇數的基礎上加上預先定義的素數表PrimeTableB[N]中的數， 轉到步驟2-1；
步驟2-4：如果不能，則轉到步驟2-5；
步驟2-5：判斷大整數能否整除預定義素數表PrimeTableA[M]中的素數；
步驟2-6：如果能整除，則說明產生的大整數不是素數，在該大整數數的基礎上加上預先 定義的素數表PrimeTableB[N]中的數，轉到步驟2-1；
步驟2-7：如果該大整數不能整除預定義素數表PrimeTableA[M]中所有的素數，則說明 其可能是素數，轉到步驟3。
3.根據權利要求1所述的一種改進的快速生成大素數的方法，其特征在于，所述方法是 基于Miller-Rabin素數檢測算法，通過加入預處理過程，并且采用Montgomery模乘算法對 原Miller-Rabin算法檢測素數進行了優化。
4.根據權利要求1所述的一種改進的快速生成大素數的方法，其特征在于，所述方法應 用于增加RSA算法的密鑰長度。
5.根據權利要求1所述的一種改進的快速生成大素數的方法，其特征在于，所述方法采 用的是預定義素數表PrimeTableB中的素數元素作為隨機遞增的增量進行搜索。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于南京郵電大學，未經南京郵電大學許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201510814575.1/1.html，轉載請聲明來源鉆瓜專利網。
