[發明專利]一種在嵌入式系統中生成大素數的方法

有效

• 申請號: 201110439890.2
• 申請日: 2011-12-23
• 公開（公告）號: CN102591618A
• 公開（公告）日: 2012-07-18
• 發明（設計）人: 陸舟;于華章
• 申請（專利權）人: 飛天誠信科技股份有限公司
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種在嵌入式系統中生成大素數的方法，應用于包括第一存儲區和第二存儲區的系統中，其特征在于，所述第一存儲區存儲有預設大小的標識組，所述標識組中的標識的序號為包括0在內的數值連續的整數，且不同的標識具有不同的序號；所述第二存儲區包括多個存儲單元，不同的存儲單元中存儲有不同的素數，所述方法包括以下步驟：

①、將所述第一存儲區中存儲的標識組中的全部標識置位；生成預定位數長度的隨機數，將所述隨機數存儲到第三存儲區，以所述第二存儲區中的存儲單元存儲的數據為模數，對所述第三存儲區存儲的數據取模，得到取模值；根據所述取模值以及所述取模值對應的存儲單元存儲的數據，確定所述標識組中需要被復位的標識的序號，并對所述序號對應的標識進行復位；

②、判斷所述標識組中是否存在置位的標識，如果存在，則執行步驟③；如果不存在，則返回步驟①；

③、根據所述隨機數和所述標識組中置位的標識的序號確定待測數，對所述待測數進行素性檢測，如果所述待測數通過素性檢測，則將所述待測數作為大素數輸出；如果所述標識組中所有置位的標識對應的待測數均未通過素性檢測，則返回步驟①。

2.如權利要求1所述的方法，其特征在于，所述根據所述取模值以及所述取模值對應的存儲單元存儲的數據，確定所述標識組中需要被復位的標識的序號，具體為：

當所述取模值為0時，將所述取模值與所述取模值對應的存儲單元存儲的數據的整數倍的和，作為所述需要被復位的標識的序號；

當所述取模值為奇數時，獲取所述取模值對應的存儲單元存儲的數據與所述取模值之間的差，將所述差除以2得到的結果作為所述需要被復位的標識的序號；

當所述取模值為非零偶數時，獲取所述當前取模值除以2得到的商，將所述當前素數與所述商的差作為所述需要被復位的標識的序號；

所述根據所述隨機數和所述標識組中置位的標識的序號確定待測數，具體為：

將所述置位的標識的序號的2倍與所述隨機數相加得到的結果，作為所述待測數。

3.如權利要求1所述的方法，其特征在于，所述根據所述取模值以及所述取模值對應的存儲單元存儲的數據，確定所述標識組中需要被復位的標識的序號，具體為：

當所述取模值為0時，將所述取模值與所述取模值對應的存儲單元存儲的數據的整數倍的和，作為所述需要被復位的標識的序號；

當所述取模值為奇數時，獲取所述取模值對應的存儲單元存儲的數據與所述取模值的和，將所述和除以2得到的商作為所述需要被復位的標識的序號；

當所述取模值為非零偶數時，將所述取模值除以2得到的商作為所述需要被復位的標識的序號；

所述根據所述隨機數和所述標識組中置位的標識的序號確定待測數，具體為：

將所述隨機數與所述置位的標識的序號的2倍的差，作為所述待測數。

4.如權利要求1所述的方法，其特征在于，所述生成預定位數長度的隨機數，包括：

生成預定位數長度的二進制數；

判斷所述二進制數的最低位是否為1，如果所述最低位為1，則將所述二進制數作為所述隨機數；如果所述最低位不為1，則將所述最低位置為1，并將所述二進制數作為所述隨機數。

5.如權利要求1所述的方法，其特征在于，所述生成預定位數長度的隨機數，包括：

生成預定位數長度的二進制數；

判斷所述二進制數的最高位是否為1，如果所述最高位為1，則將所述二進制數作為所述隨機數；如果所述最高位不為1，則將所述最高位置為1，并將所述二進制數作為所述隨機數。