一種生成大素數的方法和裝置的製作方法

2023-06-29 11:23:01

專利名稱：一種生成大素數的方法和裝置的製作方法
技術領域：
本發明涉及密碼學領域，尤其涉及一種生成大素數的方法和裝置。
背景技術：
在密碼實現過程中，特別是公開密鑰密碼的實現過程中，需要嵌入式系統生成大素數供加密等過程使用，例如，RSA加密過程中的密鑰參數需要使用嵌入式系統生成的大素數。現有技術中，大素數的生成過程包括首先生成長度足夠的隨機數；然後判斷該隨機數是否為素數；當確定該隨機數不為素數時，則重新生成一組新隨機數或對當前隨機數進行適度變換，然後再次判斷新隨機數是否為素數，直到生成一個符合要求的隨機數。在上述生成大素數的過程中，發明人發現現有技術中至少存在如下問題由於目前廣泛使用的素性判斷方法本身的運算時間較長，而大多數情況下需要尋找數百甚至上千次隨機數後才能找到大素數，即需要使用數百甚至上千次的素性判斷方法，從而導致生成大素數的時間較長。

發明內容
本發明的實施例提供一種生成大素數的方法和裝置，能夠節省大素數的生成時間。一方面，提供一種生成大素數的方法，包括①、根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；②、將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；③、判斷所述取模值組中是否存在等於零的取模值；如果存在，則執行④；否則， 執行⑤；④、根據預先設置的步長更新所述隨機數，更新所述取模值組中的取模值，並返回 ③；⑤、檢測所述隨機數的當前值是否為素數，如果為素數，則執行⑥；否則，返回④；⑥、存儲或輸出所述隨機數的當前值。另一方面，提供一種生成大素數的方法，包括①、根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；②、將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；③、判斷所述取模值組中是否存在等於零的取模值；如果存在，則執行④；否則， 執行⑦；
④、根據預先設置的步長分別更新所述取模值組中的取模值，或者，根據所述步長和所述小素數表中的素數，分別更新所述取模值組中的取模值；⑤、判斷所述取模值組中是否存在等於零的取模值；如果存在，則返回④；否則， 執行⑥；⑥、更新所述隨機數；⑦、檢測所述隨機數的當前值是否為素數，如果為素數，則執行⑧；否則，返回④；⑧、存儲或輸出所述隨機數的當前值。又一方面，提供一種生成大素數的裝置，包括生成模塊，用於根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；取模模塊，用於將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；判斷模塊，用於判斷所述取模值組中是否存在等於零的取模值；更新模塊，用於在所述判斷模塊判斷所述取模值組中存在等於零的取模值，或者所述檢測模塊檢測到所述隨機數的當前值不是素數時，根據預先設置的步長更新所述隨機數，更新所述取模值組中的取模值，並觸發所述判斷模塊判斷所述取模值組中是否存在等於零的取模值；檢測模塊，用於在所述判斷模塊判斷所述取模值組中不存在等於零的取模值時， 檢測所述隨機數的當前值是否為素數；處理模塊，用於在所述檢測模塊檢測到所述隨機數的當前值為素數時，存儲或輸出所述隨機數的當前值。再一方面，提供一種生成大素數的裝置，包括生成模塊，用於根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；取模模塊，用於將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；判斷模塊，用於判斷所述取模值組中是否存在等於零的取模值，當第一次判斷的結果為是時，觸發所述檢測模塊檢測所述隨機數的當前值是否為素數；第一更新模塊，用於在所述判斷模塊判斷所述取模值組中存在等於零的取模值， 或者所述檢測模塊檢測到所述隨機數的當前值不是素數時，根據預先設置的步長分別更新所述取模值組中的取模值，並觸發所述判斷模塊判斷所述取模值組中是否存在等於零的取模值，或者，根據所述步長和所述小素數表中的素數，分別更新所述取模值組中的取模值， 並觸發所述判斷模塊判斷所述取模值組中是否存在等於零的取模值；第二更新模塊，用於在所述判斷模塊的第一次判斷之後的判斷的結果為是時，更新所述隨機數，並觸發所述檢測模塊檢測所述隨機數的當前值是否為素數；檢測模塊，用於檢測所述隨機數的當前值是否為素數； 處理模塊，用於在所述檢測模塊檢測到所述隨機數的當前值為素數時，存儲或輸出所述隨機數的當前值。本發明實施例提供的技術方案中，先通過取模對生成的隨機數進行篩選，再對符合要求的隨機數進行素性檢測，從而減少素性檢測的次數，從而節省大素數的生成時間，解決了現有技術中由於素性判斷次數較多而導致的生成大素數的時間較長的問題。


為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附 圖僅僅是本發明的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他的附圖。圖1為本發明實施例一提供的一種生成大素數的方法流程圖；圖2為本發明實施例二提供的一種生成大素數的方法流程圖；圖3為本發明實施例三提供的一種生成大素數的方法流程圖；圖4為本發明實施例四提供的一種生成大素數的方法流程圖；圖5為本發明實施例五提供的一種生成大素數的方法流程圖；圖6為本發明實施例六提供的一種生成大素數的方法流程圖；圖7為本發明實施例七提供的一種生成大素數的方法流程圖；圖8為本發明實施例八提供的一種生成大素數的裝置結構圖；圖9為本發明實施例九提供的一種生成大素數的裝置結構圖。
具體實施例方式下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。如圖1所示，為本發明實施例一提供的一種生成大素數的方法流程圖，包括以下步驟步驟101，根據用戶輸入的位數生成相應長度的隨機數；在本實施例中，步驟101中隨機數的位數與用戶輸入的位數相同。為了確保該生成的隨機數足夠大，可以將該隨機數的最高位設置為1 ；為了確保該生成的隨機數為奇數， 以便於縮小隨機數的範圍，便於素數的生成，也可以將隨機數的最低位設置為1 ；還可以對隨機數進行其他設置，以便於素數的生成，在此不再一一贅述。步驟102，將隨機數的當前值對小素數表中各個素數分別取模，得到取模值組；其中，取模值組中包括對隨機數對各個素數分別取模得到的取模值。在本實施例中，通過步驟102將該當前隨機數對小素數表中的各個素數分別取模，既可以為將該當前隨機數對小素數表中預先設置範圍內的各個素數分別取模，也可以為將該當前隨機數對小素數表中小於該當前隨機數的各個素數分別取模，還可以為將該當前隨機數對小素數表中小於該當前隨機數的其他範圍的素數分別取模，在此不作限制。在本實施例中，隨機數可以按照包含至少一個字的字組形式存儲，該字組中的字按照從高位到低位的順序依次排列。將隨機數的當前值對小素數表中的素數取模，包括A、從最高位字開始，將隨機數的當前字對所述小素數表中的素數取模，得到當前取模值；
\
B、判斷當前字是否為最低位字，如果是最低位字，則執行C ；否則，執行D ；C、確定當前取模值為所述隨機數對所述素數的取模結果；D、對所述當前取模值和所述隨機數的下一字進行拼接，得到中間值，所述當前取模值位於所述中間值的高位，所述下一字位於所述中間值的高位，所述下一字為所述隨機數中與所述當前字相鄰的低位字；E、將所述中間值對所述素數取模，得到下一取模值，將所述當前字更新為所述下一字，將所述當前取模值更新為所述下一取模值，並返回步驟B。上述流程中，當前字和下一字為隨機數的字組中的相鄰的兩個字，且當前字高於
下一字。由於隨機數以字組的形式存儲，因此當該隨機數存儲的字的個數為M時，通過步驟102將隨機數的當前值對小素數表中的各個素數分別取模，可以為通過雙字變量的方式將M個字的隨機數的當前值對小素數表中的各個素數分別取模，也可以為通過其他方式將 M個字的隨機數的當前值對小素數表中的各個素數分別取模，在此不再一一贅述。步驟103，判斷取模值組中是否存在等於零的取模值，如果存在，則執行步驟104 ； 否則，執行步驟105。步驟104，根據預先設置的步長更新隨機數，更新取模值組中的取模值，並返回步驟 103 ；具體地，更新所述取模值組中的取模值的過程，可以是根據預先設置的步長分別更新取模值組中的取模值；也可以是根據步長和小素數表中的素數，分別更新所述取模值組中的取模值，即，根據步長分別更新所述取模值組中的取模值，當更新後的取模值小於零、大於或者等於所述小素數表中與該取模值對應的素數時，根據該素數更新所述取模值。 具體地，當取模值小於零時，將取模值自加小素數表中與該取模值對應的素數；當取模值大於或者等於小素數表中與該取模值對應的素數時，將該取模值自減小素數表中與該取模值對應的素數，或者，將該取模值更新為該取模值對小素數表中與該取模值對應的素數取模得到的結果。其中，上述根據預先設置的步長更新隨機數，可以具體為將隨機數自加步長；相應地，上述根據步長分別更新取模值組中的取模值，具體為將取模值組中的各個取模值分別自加步長。上述根據預先設置的步長更新隨機數，還可以具體為將隨機數自減步長；相應地，上述根據步長分別更新取模值組中的取模值，具體為將取模值組中各個取模值分別自減步長。在本實施例中，預先設置的步長可以為偶數值，該偶數值可以為正數，也可以為負數，在此不作限制。步驟105，檢測隨機數的當前值是否為素數，如果為素數，則執行步驟106 ；否則， 執行步驟104 ；當隨機數的當前值為P時，通過步驟105檢測生成結果是否為素數的方法，可以為將小於隨機數的當前值的至少一個隨機數的(P-I)次冪分別對隨機數的當前值取模，得到第一隨機取模值組後，檢測該第一隨機取模值組中各個取模值是否等於1 ；也可以為將小於隨機數的當前值的至少一個隨機數的P次冪分別對隨機數的當前值取模，得到第二隨機取模值組後，將小於該第二隨機數的至少一個隨機數分別對隨機數的當前值取模，得到第三隨機取模值組，檢測該第二隨機取模值組中各個取模值與第三隨機取模值組中相應的取模值是否相等；還可以通過其他方式檢測隨機數的當前值是否為素數，在此不再一一贅述。步驟106，存儲或輸出隨機數的當前值。本發明實施例提供的技術方案中，先通過取模對生成的隨機數進行篩選，再對符合要求的隨機數進行素性檢測，從而減少素性檢測的次數，從而節省大素數的生成時間，解決了現有技術 中由於素性判斷次數較多而導致的生成大素數的時間較長的問題。如圖2所示，為本發明實施例二提供的一種生成大素數的方法流程圖，包括以下步驟步驟201，根據用戶輸入的位數生成相應長度的隨機數。其中，隨機數的位數與用戶輸入的位數相同。如果生成的隨機數的最高位不為1， 可以將該最高位置為1 ；如果生成的隨機數的最低位不為1，可以將最低位置為1。步驟202，將隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組。步驟203，判斷取模值組中是否存在等於零的取模值；如果存在，則執行步驟204 ； 否則，執行步驟208。步驟204，根據預先設置的步長分別更新取模值組中的取模值，或者，根據步長和小素數表中的素數，分別更新取模值組中的取模值。具體地，根據步長和小素數表中的素數分別更新取模值組中的取模值的過程，可以為根據步長分別更新取模值組中的取模值，當取模值小於零、大於或者等於小素數表中與該取模值對應的素數時，根據該素數更新取模值，即，當取模值小於零時，將取模值自加小素數表中與該取模值對應的素數；當取模值大於或者等於小素數表中與該取模值對應的素數時，將取模值自減小素數表中與該取模值對應的素數，或者，將取模值更新為取模值對小素數表中與該取模值對應的素數取模得到的結果。其中，根據步長分別更新取模值組中的取模值，可以為將取模值組中各個取模值分別自加步長；也可以為將取模值組中各個取模值分別自減所述步長。步驟205，根據步長更新中間變量。其中，中間變量的初始值為零。如果步驟204將取模值組中各個取模值分別自加所述步長，則上述根據步長更新中間變量，具體為將中間變量自加步長。如果步驟204將取模值組中各個取模值分別自減步長，則上述根據步長更新中間變量，具體為將中間變量自減步長。上述步長可以為偶數值。需要說明的是，上述步驟205可以在步驟204之前執行，也可以與步驟204同時執行。步驟206，判斷取模值組中是否存在等於零的取模值；如果存在，則返回步驟204 ； 否則，執行步驟207。步驟207，將隨機數更新為該隨機數與中間變量的當前值之和。步驟208，檢測隨機數的當前值是否為素數，如果為素數，則執行步驟209 ；否則， 返回步驟204。
步驟209，存儲或輸出隨機數的當前值。本發明實施例提供的技術方案中，先通過取模對生成的隨機數進行篩選，再對符合要求的隨機數進行素性檢測，從而減少素性檢測的次數，從而節省大素數的生成時間，解決了現有技術中由於素性判斷次數較多而導致的生成大素數的時間較長的問題。如圖3所示，為本發明實施例三提供的一種生成大素數的方法流程圖，包括以下步驟步驟301，根據用戶輸入的位數生成相應長度的隨機數。其中，隨機數的位數與用戶輸入的位數相同。如果生成的隨機數的最高位不為1， 可以將該最高位置為1 ；如果生成的隨機數的最低位不為1，可以將最低位置為1。步驟302，將隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組。步驟303，判斷取模值組中是否存在等於零的取模值；如果存在，則執行步驟304 ； 否則，執行步驟308。步驟304，根據預先設置的步長分別更新取模值組中的取模值，或者，根據步長和小素數表中的素數，分別更新取模值組中的取模值。具體地，根據步長和小素數表中的素數分別更新取模值組中的取模值的過程，可以為根據步長分別更新取模值組中的取模值，當取模值小於零、大於或者等於小素數表中與該取模值對應的素數時，根據該素數更新取模值，即，當取模值小於零時，將取模值自加小素數表中與該取模值對應的素數；當取模值大於或者等於小素數表中與該取模值對應的素數時，將取模值自減小素數表中與該取模值對應的素數，或者，將取模值更新為取模值對小素數表中與該取模值對應的素數取模得到的結果。其中，根據步長分別更新取模值組中的取模值，可以為將取模值組中各個取模值分別自加步長；也可以為將取模值組中各個取模值分別自減所述步長。步驟305，對更新次數自加1。其中，更新次數的初始值為零。需要說明的是，上述步驟305可以在步驟304之前執行，也可以與步驟304同時執行。步驟306，判斷取模值組中是否存在等於零的取模值；如果存在，則返回步驟304 ； 否則，執行步驟307。步驟307，根據更新次數和步長更新隨機數。具體地，如果步驟304將取模值組中各個取模值分別自加所述步長，則上述根據更新次數和步長更新隨機數，具體為對隨機數自加更新次數與步長的乘積。如果步驟304 將取模值組中各個取模值分別自減步長，則上述根據更新次數和步長更新隨機數，具體為 對隨機數自減更新次數與步長的乘積。上述步長可以為偶數值。步驟308，檢測隨機數的當前值是否為素數，如果為素數，則執行步驟309 ；否則， 返回步驟304。步驟309，存儲或輸出隨機數的當前值。 本發明實施例提供的技術方案中，先通過取模對生成的隨機數進行篩選，再對符合要求的隨機數進行素性檢測，從而減少素性檢測的次數，從而節省大素數的生成時間，解決了現有技術中由於素性判斷次數較多而導致的生成大素數的時間較長的問題。 如圖4所示，為本發明實施例四提供的一種生成大素數的方法流程圖，採用的技術方案描述如下根據輸入的第一參數，生成指定位數的隨機數，所述第一參數為所述隨機數的位數。優選地，在本發明實施例四中，對超過4個字節的隨機數稱為大數。對所述隨機數進行小素數篩選，再對通過小素數篩選的隨機數進行素性檢測，若通過素性檢測，則將所述隨機數作為一個大素數輸出。優選地，本發明實施例四中的小素數表為不超過4個字節的素數的集合，所述小素數表中的元素預設在計算機中。具體步驟如下步驟401，根據第一參數生成當前隨機數，將該當前隨機數的高位和最低位置為 1 ；具體地，在本發明實施例中，當前隨機數的高位是指所述當前隨機數的高字節位， 將所述當前隨機數的高位置為1的目的是保證生成的當前隨機數有足夠的位數，將所述當前隨機數的最低位置為1的目的是保證生成的當前隨機數是奇數；優選地，本發明實施例中生成的當前隨機數為1024位，設所述當前隨機數為P1 P1 = D02C3EC6C4B4BF5AF8519F1EFA08CC97A2798CE7197D22440695126FDA2F2B6C2 82515A43E6AB8D7179D085E6F76EFD7150FF21E86C8A88C38BCDC426E4DB8AB。步驟402，將當前隨機數對小素數表中的素數分別取模，得到取模值，將取模值存儲到臨時數組中，得到餘數數組；具體地，當前隨機數以字組形式存儲在計算機中，所述字的字長為2n比特，所述字組由字組成，所述字的個數為M :M等於所述當前隨機數的位數除以2n。同時，計算機內部自定義一個雙字變量T，所述雙字變量T由高位TH和低位TL組成。具體地，所述當前隨機數的具體取模過程為所述當前隨機數的第1個字與所述小素數表中的第一個素數取模，得到取模值，將所述取模值存儲到TH，同時，所述當前隨機數的第2個字存儲到TL，所述T對所述小素數表中的第一個素數取模，得到取模值，所述取模值替換所述TH中的元素，所述當前隨機數的第3個字替換所述TL中的元素，所述T再對所述小素數表中的第一個素數取模，得到取模值，所述取模值再替換所述TH中的元素，依次進行取模、存儲、替換循環，直到所述當前隨機數的第M個字替換所述TL中的元素，所述 T又對所述小素數表中的第一個素數取模，得到取模值，將所述取模值存儲到所述餘數數組中，所述當前隨機數再依照如上方法對所述小素數表中的其它素數分別取模。優選地，在本實施例中，所述小素數表包含53個素數，如下03,05,07,OB,0D,11，13，17，ID,1F，25，29，2B，2F，35，3B，3D，43，46，49，4F，53，59， 61，65，67，6B，6D，71，7F，83，89，8B，95，97，9D，A3，A7，AD，B3, B5, BF, Cl, C5, C7, D3, DF, E3, E5, E9, EF, Fl, FB ；相應地，所述餘數數組中的元素為00，02，03，00，03，04，09，02，18，10，16，01，18，13，2D，09，2D，09，11，2D，36，15，03， 2C，0C，4E，5E，36，5B，7A，14，83，88，17，44，93，6A，32，6C，7B，39，8A， B6，90， A7，57，32，2D， 03，29，40，40，4D。步驟403，判斷餘數數組中是否有0，如果有0，則表示所述當前隨機數沒有通過所述小素數表的篩選，執行步驟404，如果沒有0，則表示所述當前隨機數通過所述小素數表的篩選，執行步驟406。步驟404，對當前隨機數自加第一預設值；優選地，所述第一預設值為2η，在本實施例中，η為正整數，設所述第一預設值為 2，即所述當前隨機數自加整數2 ；具體地， 在本發明實施例中，所述當前隨機數P1取模後生成的餘數數組中有0，則表示當前隨機數P1沒有通過所述小素數表的篩選，則所述當前隨機數P1自加整數2，生成 P/ P1' = D02C3EC6C4B4BF5AF8519F1EFA08CC97A2798CE7197D22440695126FDA2F2B6C 282515A43E6AB8D7179D085E6F76EFD7150FF21E86C8A88C38BCDC426E4DB8AD。步驟405，對餘數數組中的每個元素自加第一預設值，生成對應的新元素，並對大於等於小素數表中對應素數的新元素自減小素數表中對應的素數，再執行步驟403;相應地，在本發明實施例中，執行完步驟405後的餘數數組為02,04,05,02,05,06,0Β,04,1Α,12，18，03，1Α,15，2F，0Β，2F，0Β，13，30，38，17，05， 2E，0E，51，61，38，5D，7C，16，85，8A，19，46，95，6C，34，6E，7D，3B，8C， B8，92， A9，59，34，30， 05，2B，42，42，4F。步驟406，檢測當前隨機數是否為素數，是則執行步驟407，否則返回步驟404;優選地，在本實施例中，通過素性檢測判斷所述當前隨機數是否為素數，具體方法為取小於所述當前隨機數的不同隨機數，用所述不同隨機數的(P-I)次冪分別對所述當前隨機數取模，得到取模值，檢測所述取模值是否為1，若為1，則表示所述當前隨機數為素數。具體地，所述P為所述隨機數。步驟407，輸出當前隨機數；優選地，在本實施例中，輸出的當前隨機數即為篩選出來的大素數。本發明實施例提供的技術方案中，先通過取模對生成的隨機數進行篩選，再對符合要求的隨機數進行素性檢測，從而減少素性檢測的次數，從而節省大素數的生成時間，解決了現有技術中由於素性判斷次數較多而導致的生成大素數的時間較長的問題。如圖5所示，為本發明實施例五提供的一種生成大素數的方法流程圖，採用的技術方案描述如下根據輸入第一參數，生成指定位數的隨機數，所述第一參數為所述隨機數的位數。 優選地，在本發明實施例五中，對超過2個字節的隨機數稱為大數。對所述隨機數進行小素數篩選，再對通過小素數篩選的隨機數進行素性檢測，若通過素性檢測，則將所述隨機數作為一個大素數輸出。本發明實施例五中小素數表為不超過2個字節的素數的集合，所述小素數表中的元素預設在計算機中。具體步驟如下步驟501，根據第一參數生成當前隨機數，將該當前隨機數的高位和最低位置為 1 ；具體地，在本發明實施例中，所述當前隨機數的高位是指所述當前隨機數的高字節位，將所述當前隨機數的高位置為1的目的是保證生成的當前隨機數有足夠的位數，將所述當前隨機數的最低位置為1的目的是保證生成的當前隨機數是奇數；優選地，本發明實施例中生成的當前隨機數為512位，設所述當前隨機數為P2:P2 = C1F7821A42CC4D35AB46E01A89034E3227B8A7FBA374C170C103585CD4994499177D267794C183176D044CAF181B4B9E762E3C60C9E0E17AF1ABBBD4C797AF21。步驟502，將當前隨機數對小素數表中的素數分別取模，得到取模值，將該取模值存儲到臨時數組中，得到餘數數組； 優選地，在本發明實施例中，所述小素數表包含45個素數，如下001D,001F,0025,0029,002B,002F,0035,003B,003D,0043,0047,0049,004F, 0053，0059，0061，0065，0067，006B，006D，0071，007F，0083，0089，008B，0095，0097，009D， 00A3,00A7,00AD,00B3,00B5,00BF,OOCl，00C5,00C7,00D3,00DF,00E3，00E5，00E9，00EF， OOFl，OOFB ；相應地，所述餘數數組中的元素為0000,0018,0018,0026,0028,0024,0008,001C,0007,0037,0022,0006, 0009, 003E,002F,004C,003C,0064，0010，001F，0046，0018，005A,0077，0082，0047，0025，002A， 0058，0021，0040，00ΑΕ，0063，0090，004C,0096，006B，002F,000E,0087，002F，0064，00A9, 00DC，0023。步驟503，判斷餘數數組中是否有0 ；如果有0，表示所述當前隨機數沒有通過小素數表的篩選，執行步驟504，如果沒有0，表示所述當前隨機數通過小素數表的篩選，執行步驟 506。步驟504，對當前隨機數自加第二預設值；優選地，所述第二預設值為2η，在本發明實施例中，η為負整數，設所述第二預設值為_4，即所述當前隨機數自加整數_4 ；具體地，在本發明實施例中，所述大數P2取模後生成的餘數數組中有0，則表示所述當前隨機數P2沒有通過所述小素數表的篩選，所述當前隨機數P2自加整數-4，生成Ρ2』 P2' = C1F7821A42CC4D35AB46E01A89034E3227B8A7FBA374C170C103585CD4994499 177D267794C183176D044CAF181B4B9E762E3C60C9E0E17AF1ABBBD4C797AF1D。步驟505，對餘數數組中的每個元素自加第二預設值，生成對應的新元素，並對小於0的新元素自加小素數表中對應的素數，再執行步驟503 ；相應地，在本發明實施例中，執行完步驟305後的餘數數組為0019,0014,0014,0022,0024,0020,0004,0018,0003,0033,001Ε,0002,0005, 003Α,002Β,0048，0038，0060，000C，001Β,0042，0014，0056，0073，007Ε，0043，0021，0026， 0054，001D,003C,OOAA,005F,008C,0048，0092，0067，002Β，000Α，0083，002Β，0060，00Α5， 00D8，001F。步驟506，檢測當前隨機數是否為素數，是則執行步驟507，否則返回步驟504 ；優選地，在本發明實施例中，通過素性檢測判斷所述當前隨機數是否為素數，具體方法為取小於所述當前隨機數的不同隨機數，檢測用所述不同隨機數的P次冪分別對所述當前隨機數取模得到的取模值是否等於所述不同隨機數分別對所述當前隨機數的取模值，若等於，則表示所述當前隨機數為素數。具體地，所述P為所述隨機數。步驟507，輸出當前隨機數；優選地，在本發明實施例中，輸出的所述當前隨機數即為篩選出來的大素數。本發明實施例提供的技術方案中，先通過取模對生成的隨機數進行篩選，再對符合要求的隨機數進行素性檢測，從而減少素性檢測的次數，從而節省大素數的生成時間，解決了現有技術中由於素性判斷次數較多而導致的生成大素數的時間較長的問題。如圖6所示，為本發明實施例六提供的一種生成大素數的方法流程圖，採用的技術方案描述如下

根據輸入第一參數，生成指定位數的隨機數，所述第一參數為所述隨機數的位數。 優選地，在本發明實施例六中，對超過4個字節的隨機數稱為大數。對所述隨機數進行小素數篩選，再對通過小素數篩選的隨機數進行素性檢測，若通過素性檢測，則將所述隨機數作為一個大素數輸出。優選地，本發明實施例六中小素數表為不超過4個字節的素數的集合。 在計算機中預設所述小素數表中的元素和一個累加變量，所述累加變量的初始值為0。具體步驟如下步驟601，根據第一參數生成當前隨機數，將該當前隨機數的高位和最低位置為 1 ；具體地，在本發明實施例中，所述當前隨機數的高位是指所述當前隨機數的高字節位，將所述當前隨機數的高位置為1的目的是保證生成的當前隨機數有足夠的位數，將所述當前隨機數的最低位置為1的目的是保證生成的當前隨機數是奇數；優選地，本發明實施例中生成的當前隨機數為256位，設所述當前隨機數為P3 P3 = F99310E590592EE6186A4E0A40AED3883B7967E2CE92B8A7724D8868DFD5CEF7o步驟602，將當前隨機數對小素數表中的素數分別取模，得到取模值，將該取模值存儲到臨時數組中，得到餘數數組；優選地，在本發明實施例中，所述小素數表包含40個素數，如下0003，0005，0007，000B，000D，0011，0013，0017，001D，001F，004F，0053，0059， 0061，0065，0067，006B，006D,0071，007F，0083，0089，008B，0095，0097，009D，00A3,00A7, OOAD,00B3，00B5，00BF，00C1,00C5,00C7,00D3,00DF,00E3,00E5，00E9，相應地，所述餘數數組中的元素為0000,0000,0002,0001,0006,000E,000A,0004,0010,0006,0035,0021,002D, 003F,0045，0008，002D，0043，0003，0055，0062，0014，0039，0028，005B，002C,009C,002A, 0080，007B，0F3E，015A，01D7，06AF，037A,027A,0344，08DA,0796，0EA7。步驟603，判斷餘數數組中是否有0，如果有0，則表示所述當前隨機數沒有通過所述小素數表的篩選，執行步驟604，如果沒有0，則表示所述當前隨機數通過所述小素數表的篩選，執行步驟606。步驟604，對累加變量自加第三預設值；優選地，所述第三預設值為2η，在本實施例中，η為正整數，設所述第三預設值為 4，即所述當前隨機數自加整數4 ；具體地，在本發明實施例中，所述大數P3取模後生成的餘數數組中有0，則表示所述當前隨機數P3沒有通過所述小素數表的篩選，則所述當前隨機數P3自加整數4，生成P/ P3' = F99310E590592EE6186A4E0A40AED3883B7967E2CE92B8A7724D8868DFD5CE F9。步驟605，對餘數數組中的每個元素自加第一預設值，生成對應的新元素，將新元素對小素數表中對應的素數取模，得到取模值，用該取模值替換餘數數組中對應的元素，再執行步驟603 ；
具體地，在本發明實施例中，執行完步驟605後的餘數數組為0002,0002,0004,0003,0008,0010,000C,0006,0012,0008,0037,0023,002F, 0041，0047，000A,002F,0045，0005，0057，0064，0016，003B,002A,005D,002E，009E，002C, 0082，007D，0F40,015C, 01D9,06B1,037C,027C,0346，08DC，0798，0EA9。步驟606，對當前隨機數自加累加變量值。步驟607，檢測當前隨機數是否為素數，是則執行步驟608，否則返回步驟604。步驟608，輸出當前隨機數；優選地，在本實施例中，輸出的所述當前隨機數即為篩選出來的大素數。本發明實施例提供的技術方案中，先通過取模對生成的隨機數進行篩選，再對符合要求的隨機數進行素性檢測，從而減少素性檢測的次數，從而節省大素數的生成時間，解決了現有技術中由於素性判斷次數較多而導致的生成大素數的時間較長的問題。如圖7所示，為本發明實施例七提供的一種生成大素數的方法流程圖，採用的技術方案描述如下根據輸入第一參數，生成指定位數的隨機數，所述第一參數為所述隨機數的位數。 優選地，在本發明實施例七中，對超過6個字節的隨機數稱為大數。對所述隨機數進行小素數篩選，再對通過小素數篩選的隨機數進行素性檢測，若通過素性檢測，則將所述隨機數作為一個大素數輸出。本發明實施例引入的小素數表為不超過2個字節的素數的集合。在計算機中預設所述小素數表中的元素和一個累加變量，所述累加變量初始值為0。具體步驟如下步驟701，根據第一參數生成當前隨機數，將該當前隨機數的高位和最低位置為 1 ；具體地，在本發明實施例中，所述當前隨機數的高位是指所述當前隨機數的高字節位，將所述當前隨機數的高位置為1的目的是保證生成的當前隨機數有足夠的位數，將所述當前隨機數的最低位置為1的目的是保證生成的當前隨機數是奇數；優選地，本實施例中生成的當前隨機數為384位，設所述當前隨機數為P4 P4 = F12A47AD213E43868E9909449009BA34DD490CF531015AB47F0ECCEDFC6126E6C 7D6233A49751B8543A4C429C920FDE5。步驟702，將當前隨機數對小素數表中的素數分別取模，得到取模值，將該取模值存儲到臨時數組中，得到餘數數組；優選地，在本發明實施例中，所述小素數表包含45個素數，如下0003，0005，0007，000B，000D，0011，0013，0017，001D，001F，0083，0089，008B， 0095，0097，009D,00A3,00A7,00AD,00B3,00B5,00BF,OOCl，00C5,00C7,00D3,00DF,00E3, 00E5，00E9，0167，016F，0175，017B，017F，0185，018D，0191，0199，01A3，0AC1，0ACF，0AD9， 0AE5，0AE7，OAED，OAFl，0AF3，0B03，OB11，0C77，0C83，0C89，0C91，0C95 ；相應地，所述餘數數組中的元素為0001，0000，0000，0000，0001，0000，000D，0006，000C，0013，005D，006C，0029， 003C,008C,0010，006B，0046，003E，000C，002D,0094，005C,006D,0068，004E，005E,0076， 005A，001C，0156，00B2，00E8，0057，0019，0019，0138，0149，0030，007B，04A9，0875，01D1， 03E0，02D2，03D1，051F，02E1，0805，09A2，0452，0687，041D，0212,OOFO0
步驟703，判斷餘數數組中是否有0 ；如果有0，表示所述當前隨機數沒有通過所述小素數表的篩選，執行步驟704，如果沒有0，表示所述當前隨機數通過所述小素數表的篩選，執行步驟706。 步驟704，對累加變量自加第四預設值；優選地，所述第四預設值為2η，在本實施例中，η為負整數，設所述第四預設值為_2，即所述當前隨機數自加整數_2 ；具體地，在本發明實施例中，對所述當前隨機數P4取模後生成的餘數數組中有0， 則表示所述當前隨機數P4沒有通過所述小素數表的篩選，所述當前隨機數P4自加整數-2， 生成P/ P/ = F12A47AD213E43868E9909449009BA34DD490CF531015AB47F0ECCEDFC6126Ε6 C7D6233A49751B8543A4C429C920FDE3。步驟705，對餘數數組中的每個元素自加第四預設值，生成對應的新元素，並對小於0的新元素自加小素數表中對應的素數，再執行步驟703 ；相應地，在本發明實施例中，執行完步驟705後的餘數數組為0002，0003，0005，0009，000C，000F,000Β，0004，000Α,0011，005Β，006Α，0027， 003Α,008Α,000Ε,0069，0044，003C,000Α,002Β,0092，005Α,006Β,0066，004C，005C, 0074， 0058,001Α,0154,00Β0,00Ε6,0055,0017,0017,0136,0147,002Ε,0079,04Α7,0873,01CF, 03DE,02D0，03CF，051D,02DF,0803，09Α0，0450，0685，041Β，0210，00ΕΕ ；步驟706，對當前隨機數自加累加變量值。步驟707，檢測當前隨機數是否為素數，是則執行步驟708，否則返回步驟704。步驟708，輸出當前隨機數；優選地，在本發明實施例中，輸出的所述當前隨機數即為篩選出來的大素數。本發明實施例提供的技術方案中，先通過取模對生成的隨機數進行篩選，再對符合要求的隨機數進行素性檢測，從而減少素性檢測的次數，從而節省大素數的生成時間，解決了現有技術中由於素性判斷次數較多而導致的生成大素數的時間較長的問題。如圖8所示，本發明實施例八提供的一種生成大素數的裝置結構圖，包括生成模塊810、取模模塊820、判斷模塊830、更新模塊840、檢測模塊850和處理模塊860，其中，生成模塊810，用於根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；取模模塊820，用於將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；判斷模塊830，用於判斷所述取模值組中是否存在等於零的取模值；更新模塊840，用於在判斷模塊830判斷所述取模值組中存在等於零的取模值，或者所述檢測模塊檢測到所述隨機數的當前值不是素數時，根據預先設置的步長更新所述隨機數，更新所述取模值組中的取模值，並觸發判斷模塊830判斷所述取模值組中是否存在等於零的取模值；具體地，上述更新模塊840，具體用於根據所述步長分別更新所述取模值組中的取模值；或者，根據所述步長和所述小素數表中的素數，分別更新所述取模值組中的取模值。上述更新模塊840，可以根據所述步長分別更新所述取模值組中的取模值；當所述取模值小於零、大於或者等於所述小素數表中與該取模值對應的素數時，根據該素數更新所述取模值。其中，上述更新模塊840可以將所述隨機數自加所述步長，將所述取模值組中的各個取模值分別自加所述步長；也可以將所述隨機數自減所述步長，將所述取模值組中各個取模值分別自減所述步長。上述更新模塊840，還可以在所述取模值小於零時，將所述取模值自加所述小素數表中與該取模值對應的素數；在所述取模值大於或者等於所述小素數表中與該取模值對應的 素數時，將所述取模值自減所述小素數表中與該取模值對應的素數，或者，將所述取模值更新為所述取模值對所述小素數表中與該取模值對應的素數取模得到的結果。其中，上述步長可以為偶數值。檢測模塊850，用於在判斷模塊830判斷所述取模值組中不存在等於零的取模值時，檢測所述隨機數的當前值是否為素數；處理模塊860，用於在所述檢測模塊850檢測到所述隨機數的當前值為素數時，存儲或輸出所述隨機數的當前值。上述的裝置，還包括最高位設置模塊870，用於在生成模塊810生成的隨機數的最高位不為1時，將所述最高位置為1。最低位設置模塊880，用於在生成模塊810生成的隨機數的最低位不為1時，將所述最低位置為1。本發明實施例提供的技術方案中，先通過取模對生成的隨機數進行篩選，再對符合要求的隨機數進行素性檢測，從而減少素性檢測的次數，從而節省大素數的生成時間，解決了現有技術中由於素性判斷次數較多而導致的生成大素數的時間較長的問題。如圖9所示，本發明實施例九提供的一種生成大素數的裝置結構圖，包括生成模塊910、取模模塊920、判斷模塊930、第一更新模塊940、第二更新模塊950、檢測模塊960和處理模塊970，其中，生成模塊910，用於根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；取模模塊920，用於將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；判斷模塊930，用於判斷取模值組中是否存在等於零的取模值，當第一次判斷的結果為是時，觸發檢測模塊960檢測所述隨機數的當前值是否為素數；第一更新模塊940，用於在判斷模塊930判斷所述取模值組中存在等於零的取模值，或者檢測模塊960檢測到所述隨機數的當前值不是素數時，根據預先設置的步長分別更新所述取模值組中的取模值，並觸發判斷模塊930判斷所述取模值組中是否存在等於零的取模值，或者，根據所述步長和所述小素數表中的素數，分別更新所述取模值組中的取模值，並觸發判斷模塊930判斷所述取模值組中是否存在等於零的取模值；具體地，上述第一更新模塊940，包括第一更新子模塊941，用於根據所述步長分別更新所述取模值組中的取模值；第二更新子模塊942，用於當所述取模值小於零、大於或者等於所述小素數表中與該取模值對應的素數時，根據該素數更新所述取模值。 具體地，上述第二更新子模塊942，具體用於當所述取模值小於零時，將所述取模值自加所述小素數表中與該取模值對應的素數；當所述取模值大於或者等於所述小素數表中與該取模值對應的素數時，將所述取模值自減所述小素數表中與該取模值對應的素數， 或者，將所述取模值更新為所述取模值對所述小素數表中與該取模值對應的素數取模得到的結果。第二更新模塊950，用於在判斷模塊930的第一次判斷之後的判斷的結果為是時， 更新所述隨機數，並觸發所述檢測模塊檢測所述隨機數的當前值是否為素數；檢測模塊960，用於檢測所述隨機數的當前值是否為素數；處理模塊970，用於在所述檢測模塊檢測到所述隨機數的當前值為素數時，存儲或輸出所述隨機數的當前值。上述裝置，還包括第三更新模塊980，用於在判斷模塊930判斷所述取模值組中存在等於零的取模值時，根據所述步長更新中間變量，所述中間變量的初始值為零；相應地，上述第二更新模塊950，具體用於將所述隨機數更新為所述隨機數與所述中間變量的當前值之和。當上述第一更新子模塊941將所述取模值組中各個取模值分別自加所述步長時； 相應地，上述第三更新模塊980，具體用於將所述中間變量自加所述步長。當上述第一更新子模塊941將所述取模值組中各個取模值分別自減所述步長；相應地，上述第三更新模塊980，具體用於將所述中間變量自減所述步長。上述的裝置，還包括第四更新模塊990，用於在判斷模塊930判斷所述取模值組中存在等於零的取模值時，對更新次數自加1，所述更新次數的初始值為零；相應地，上述第二更新模塊950，具體用於根據所述更新次數和所述步長更新所述隨機數。當上述第一更新子模塊941將所述取模值組中各個取模值分別自加所述步長時； 相應地，上述第二更新模塊950，具體用於對所述隨機數自加所述更新次數與所述步長的乘積。當上述第一更新子模塊941將所述取模值組中各個取模值分別自減所述步長時； 相應地，上述第二更新模塊950，具體用於對所述隨機數自減所述更新次數與所述步長的乘積。其中，上述步長可以為偶數值。上述裝置，還包括最高位設置模塊991，用於在生成模塊910生成的隨機數的最高位不為1時，將所述最高位置為1。最低位設置模塊992，用於在生成模塊910生成的隨機數的最低位不為1時，將所述最低位置為1。本發明實施例提供的技術方案中，先通過取模對生成的隨機數進行篩選，再對符合要求的隨機數進行素性檢測，從而減少素性檢測的次數，從而節省大素數的生成時間，解決了現有技術中由於素性判斷次數較多而導致的生成大素數的時間較長的問題。本發明實施例提供的生成大素數的方法和裝置，可以應用在嵌入式系統中。 結合本文中所公開的實施例描述的方法或算法的步驟可以直接用硬體、處理器執行的軟體模塊，或者二者的結合來實施。軟體模塊可以置於隨機存儲器(RAM)、內存、只讀存儲器(ROM)、電可編程ROM、電可擦除可編程ROM、寄存器、硬碟、可移動磁碟、CD-ROM、或技術領域內所公知的任意其它形式的存儲介質中。以上所述，僅為本發明的具體實施方式
，但本發明的保護範圍並不局限於此，任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到變化或替換，都應涵蓋在本發明的保護範圍之內。因此，本發明的保護範圍應所述以權利要求的保護範圍為準。
權利要求
1.一種生成大素數的方法，其特徵在於，包括①、根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；②、將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；③、判斷所述取模值組中是否存在等於零的取模值；如果存在，則執行④；否則，執行⑤；④、根據預先設置的步長更新所述隨機數，更新所述取模值組中的取模值，並返回③；⑤、檢測所述隨機數的當前值是否為素數，如果為素數，則執行⑥；否則，返回④；⑥、存儲或輸出所述隨機數的當前值。
2.根據權利要求1所述的方法，其特徵在於，所述更新所述取模值組中的取模值，具體為根據所述步長分別更新所述取模值組中的取模值；或者根據所述步長和所述小素數表中的素數，分別更新所述取模值組中的取模值。
3.根據權利要求2所述的方法，其特徵在於，所述根據所述步長和所述小素數表中的素數，分別更新所述取模值組中的取模值，包括根據所述步長分別更新所述取模值組中的取模值；當所述取模值小於零、大於或者等於所述小素數表中與該取模值對應的素數時，根據該素數更新所述取模值。
4.根據權利要求3所述的方法，其特徵在於，所述根據預先設置的步長更新所述隨機數，具體為將所述隨機數自加所述步長；所述根據所述步長，分別更新所述取模值組中的取模值，具體為 將所述取模值組中的各個取模值分別自加所述步長。
5.根據權利要求3所述的方法，其特徵在於，所述根據預先設置的步長更新所述隨機數，具體為將所述隨機數自減所述步長；所述根據所述步長，分別更新所述取模值組中的取模值，具體為 將所述取模值組中各個取模值分別自減所述步長。
6.根據權利要求3所述的方法，其特徵在於，所述當所述取模值小於零、大於或者等於所述小素數表中與該取模值對應的素數時，根據該素數更新所述取模值，具體為當所述取模值小於零時，將所述取模值自加所述小素數表中與該取模值對應的素數； 當所述取模值大於或者等於所述小素數表中與該取模值對應的素數時，將所述取模值自減所述小素數表中與該取模值對應的素數，或者，將所述取模值更新為所述取模值對所述小素數表中與該取模值對應的素數取模得到的結果。
7.根據權利要求1至6任一項所述的方法，其特徵在於，所述步長為偶數值。
8.根據權利要求1所述的方法，其特徵在於，所述根據用戶輸入的位數生成相應長度的隨機數之後，還包括如果所述隨機數的最高位不為1，則將所述最高位置為1。
9.根據權利要求1所述的方法，其特徵在於，所述根據用戶輸入的位數生成相應長度的隨機數之後，還包括如果所述隨機數的最低位不為1，則將所述最低位置為1。
10.一種生成大素數的方法，其特徵在於，包括①、根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；②、將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；③、判斷所述取模值組中是否存在等於零的取模值；如果存在，則執行④；否則，執行⑦；④、根據預先設置的步長分別更新所述取模值組中的取模值，或者，根據所述步長和所述小素數表中的素數，分別更新所述取模值組中的取模值；⑤、判斷所述取模值組中是否存在等於零的取模值；如果存在，則返回④；否則，執行⑥、更新所述隨機數；⑦、檢測所述隨機數的當前值是否為素數，如果為素數，則執行⑧；否則，返回④；⑧、存儲或輸出所述隨機數的當前值。
11.根據權利要求10所述的方法，其特徵在於，所述根據所述步長和所述小素數表中的素數，分別更新所述取模值組中的取模值，包括根據所述步長分別更新所述取模值組中的取模值；當所述取模值小於零、大於或者等於所述小素數表中與該取模值對應的素數時，根據該素數更新所述取模值。
12.根據權利要求11所述的方法，其特徵在於，所述當所述取模值小於零、大於或者等於所述小素數表中與該取模值對應的素數時，根據該素數更新所述取模值，具體為當所述取模值小於零時，將所述取模值自加所述小素數表中與該取模值對應的素數；當所述取模值大於或者等於所述小素數表中與該取模值對應的素數時，將所述取模值自減所述小素數表中與該取模值對應的素數，或者，將所述取模值更新為所述取模值對所述小素數表中與該取模值對應的素數取模得到的結果。
13.根據權利要求11所述的方法，其特徵在於，判斷所述取模值組中存在等於零的取模值之後，還包括根據所述步長更新中間變量，所述中間變量的初始值為零；所述更新所述隨機數，具體為將所述隨機數更新為所述隨機數與所述中間變量的當前值之和。
14.根據權利要求13所述的方法，其特徵在於，所述根據所述步長，分別更新所述取模值組中的取模值，具體為將所述取模值組中各個取模值分別自加所述步長；所述根據所述步長更新中間變量，具體為將所述中間變量自加所述步長。
15.根據權利要求13所述的方法，其特徵在於，所述根據所述步長，分別更新所述取模值組中的取模值，具體為 將所述取模值組中各個取模值分別自減所述步長； 所述根據所述步長更新中間變量，具體為 將所述中間變量自減所述步長。
16.根據權利要求11所述的方法，其特徵在於，判斷所述取模值組中存在等於零的取模值之後，還包括對更新次數自加1，所述更新次數的初始值為零；所述更新所述隨機數，具體為根據所述更新次數和所述步長更新所述隨機數。
17.根據權利要求16所述的方法，其特徵在於，所述根據所述步長，分別更新所述取模值組中的取模值，具體為 將所述取模值組中各個取模值分別自加所述步長； 所述根據所述更新次數和所述步長更新所述隨機數，具體為 對所述隨機數自加所述更新次數與所述步長的乘積。
18.根據權利要求16所述的方法，其特徵在於，所述根據所述步長，分別更新所述取模值組中的取模值，具體為 將所述取模值組中各個取模值分別自減所述步長； 所述根據所述更新次數和所述步長更新所述隨機數，具體為 對所述隨機數自減所述更新次數與所述步長的乘積。
19.根據權利要求10至18任一項所述的方法，其特徵在於，所述步長為偶數值。
20.根據權利要求10所述的方法，其特徵在於，所述根據用戶輸入的位數生成相應長度的隨機數之後，還包括如果所述隨機數的最高位不為1，則將所述最高位置為1。
21.根據權利要求10所述的方法，其特徵在於，所述根據用戶輸入的位數生成相應長度的隨機數之後，還包括如果所述隨機數的最低位不為1，則將所述最低位置為1。
22.—種生成大素數的裝置，其特徵在於，包括生成模塊、取模模塊、判斷模塊、更新模塊、檢測模塊和處理模塊，其中，所述生成模塊，用於根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；所述取模模塊，用於將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；所述判斷模塊，用於判斷所述取模值組中是否存在等於零的取模值； 所述更新模塊，用於在所述判斷模塊判斷所述取模值組中存在等於零的取模值，或者所述檢測模塊檢測到所述隨機數的當前值不是素數時，根據預先設置的步長更新所述隨機數，更新所述取模值組中的取模值，並觸發所述判斷模塊判斷所述取模值組中是否存在等於零的取模值；所述檢測模塊，用於在所述判斷模塊判斷所述取模值組中不存在等於零的取模值時， 檢測所述隨機數的當前值是否為素數；所述處理模塊，用於在所述檢測模塊檢測到所述隨機數的當前值為素數時，存儲或輸出所述隨機數的當前值。
23.根據權利要求22所述的裝置，其特徵在於，所述更新模塊，具體用於根據所述步長分別更新所述取模值組中的取模值；或者根據所述步長和所述小素數表中的素數，分別更新所述取模值組中的取模值。
24.根據權利要求23所述的裝置，其特徵在於，所述更新模塊，具體用於根據所述步長分別更新所述取模值組中的取模值；當所述取模值小於零、大於或者等於所述小素數表中與該取模值對應的素數時，根據該素數更新所述取模值。
25.根據權利要求M所述的裝置，其特徵在於，所述更新模塊，具體用於將所述隨機數自加所述步長，將所述取模值組中的各個取模值分別自加所述步長。
26.根據權利要求M所述的裝置，其特徵在於，所述更新模塊，具體用於將所述隨機數自減所述步長，將所述取模值組中各個取模值分別自減所述步長。
27.根據權利要求M所述的裝置，其特徵在於，所述更新模塊，具體用於當所述取模值小於零時，將所述取模值自加所述小素數表中與該取模值對應的素數；當所述取模值大於或者等於所述小素數表中與該取模值對應的素數時，將所述取模值自減所述小素數表中與該取模值對應的素數，或者，將所述取模值更新為所述取模值對所述小素數表中與該取模值對應的素數取模得到的結果。
28.根據權利要求22至27任一項所述的裝置，其特徵在於，所述步長為偶數值。
29.根據權利要求22所述的裝置，其特徵在於，還包括最高位設置模塊，用於在所述生成模塊生成的隨機數的最高位不為1時，將所述最高位置為1。
30.根據權利要求22所述的裝置，其特徵在於，還包括最低位設置模塊，用於在所述生成模塊生成的隨機數的最低位不為1時，將所述最低位置為1。
31.一種生成大素數的裝置，其特徵在於，包括生成模塊、取模模塊、判斷模塊、第一更新模塊、第二更新模塊、檢測模塊和處理模塊，其中，所述生成模塊，用於根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；所述取模模塊，用於將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；所述判斷模塊，用於判斷所述取模值組中是否存在等於零的取模值，當第一次判斷的結果為是時，觸發所述檢測模塊檢測所述隨機數的當前值是否為素數；所述第一更新模塊，用於在所述判斷模塊判斷所述取模值組中存在等於零的取模值， 或者所述檢測模塊檢測到所述隨機數的當前值不是素數時，根據預先設置的步長分別更新所述取模值組中的取模值，並觸發所述判斷模塊判斷所述取模值組中是否存在等於零的取模值，或者，根據所述步長和所述小素數表中的素數，分別更新所述取模值組中的取模值，並觸發所述判斷模塊判斷所述取模值組中是否存在等於零的取模值；所述第二更新模塊，用於在所述判斷模塊的第一次判斷之後的判斷的結果為是時，更新所述隨機數，並觸發所述檢測模塊檢測所述隨機數的當前值是否為素數； 所述檢測模塊，用於檢測所述隨機數的當前值是否為素數；所述處理模塊，用於在所述檢測模塊檢測到所述隨機數的當前值為素數時，存儲或輸出所述隨機數的當前值。
32.根據權利要求31所述的裝置，所述第一更新模塊，包括第一更新子模塊，用於根據所述步長分別更新所述取模值組中的取模值； 第二更新子模塊，用於當所述取模值小於零、大於或者等於所述小素數表中與該取模值對應的素數時，根據該素數更新所述取模值。
33.根據權利要求32所述的裝置，其特徵在於，所述第二更新子模塊，具體用於當所述取模值小於零時，將所述取模值自加所述小素數表中與該取模值對應的素數；當所述取模值大於或者等於所述小素數表中與該取模值對應的素數時，將所述取模值自減所述小素數表中與該取模值對應的素數，或者，將所述取模值更新為所述取模值對所述小素數表中與該取模值對應的素數取模得到的結果。
34.根據權利要求32所述的裝置，其特徵在於，還包括第三更新模塊，用於在所述判斷模塊判斷所述取模值組中存在等於零的取模值時，根據所述步長更新中間變量，所述中間變量的初始值為零；所述第二更新模塊，具體用於將所述隨機數更新為所述隨機數與所述中間變量的當前值之和。
35.根據權利要求34所述的裝置，其特徵在於，所述第一更新子模塊，具體用於將所述取模值組中各個取模值分別自加所述步長； 所述第三更新模塊，具體用於將所述中間變量自加所述步長。
36.根據權利要求34所述的裝置，其特徵在於，所述第一更新子模塊，具體用於將所述取模值組中各個取模值分別自減所述步長； 所述第三更新模塊，具體用於將所述中間變量自減所述步長。
37.根據權利要求32所述的裝置，其特徵在於，還包括第四更新模塊，用於在所述判斷模塊判斷所述取模值組中存在等於零的取模值時，對更新次數自加1，所述更新次數的初始值為零；所述第二更新模塊，具體用於根據所述更新次數和所述步長更新所述隨機數。
38.根據權利要求37所述的裝置，其特徵在於，所述第一更新子模塊，具體用於將所述取模值組中各個取模值分別自加所述步長； 所述第二更新模塊，具體用於對所述隨機數自加所述更新次數與所述步長的乘積。
39.根據權利要求37所述的裝置，其特徵在於，所述第一更新子模塊，具體用於將所述取模值組中各個取模值分別自減所述步長； 所述第二更新模塊，具體用於對所述隨機數自減所述更新次數與所述步長的乘積。
40.根據權利要求31至39任一項所述的裝置，其特徵在於，所述步長為偶數值。
41.根據權利要求31所述的裝置，其特徵在於，還包括最高位設置模塊，用於在所述生成模塊生成的隨機數的最高位不為1時，將所述最高位置為1。
42.根據權利要求31所述的裝置，其特徵在於，還包括最低位設置模塊，用於在所述生成模塊生成的隨機數的最低位不為1時，將所述最低位置為1。
全文摘要
本發明公開一種生成大素數的方法和裝置，該方法包括①根據用戶輸入的位數生成相應長度的隨機數，所述隨機數的位數與所述用戶輸入的位數相同；②將所述隨機數的當前值對預先設置的小素數表中的各個素數分別取模，得到取模值組；③判斷所述取模值組中是否存在等於零的取模值；如果存在，則執行④；否則，執行⑤；④根據預先設置的步長更新所述隨機數，更新所述取模值組中的取模值，並返回③；⑤檢測所述隨機數的當前值是否為素數，如果為素數，則執行⑥；否則，返回④；⑥存儲或輸出所述隨機數的當前值。本發明實施例提供的技術方案能夠減少素性檢測的次數，從而節省大素數的生成時間。
文檔編號H04L9/22GK102325024SQ201110289038
公開日2012年1月18日 申請日期2011年9月26日 優先權日2011年9月26日
發明者於華章, 陸舟 申請人:飛天誠信科技股份有限公司