实验三：实现一个大素数生成算法

一、实验内容

掌进一步掌握大素数分解的一般原理和实现方法。能用间接方法实现大素数分解。用代码实现Solovay-Strassen素性测试法或Miller-Rabin素性测试法。

二、分实现一个大素数生成算法的基本原理

      2.1费马素性检验

         费马素性检验是一种随机化算法，判断一个数是合数还是可能是素数。

　　根据费马小定理：如果p是素数，<math>1 \le a \le p</math>，那么

　　<math>a^ \equiv 1 \pmod</math>。

　　如果我们想知道n是否是素数，我们在中间选取a，看看上面等式是否成立。如果对于数值a等式不成立，那么n是合数。如果有很多的a能够使等式成立，那么我们可以说n 可能是素数，或者伪素数。

　　在我们检验过程中，有可能我们选取的a都能让等式成立，然而n却是合数。这时等式

　　<math>a^ \equiv 1 \pmod</math>

　　被称为Fermat liar。如果我们选取满足下面等式的a

　　<math>a^ \not\equiv 1 \pmod</math>

　　那么a也就是对于n的合数判定的Fermat witness。

　　整个算法可以写成是下面两大部：

　　输入：n需要检验的数；k：参数之一来决定检验需要进行的次数。

　　输出：当n是合数时，否则可能是素数：

　　重复k次：

　　在[1, n − 1]范围内随机选取a

　　如果an − 1 mod n ≠ 1 那么返回合数

　　返回可能是素数

　　若使用模指数运算的快速算法，这个算法的运行时间是O(k × log3n)，这里k是一个随机的a需要检验的次数，n是我们想要检验的数。

　　众所周知，对于卡米歇尔数n，全部的a都会令gcd(a,n)=1，我们称之为fermat liars。尽管卡米歇尔数很是稀有，但是却足够令费马素性检验无法像如米勒-拉宾和Solovay-Strassen的素性检验般，成为被经常实际应用的素性检验。

　　一般的，如果n 不是卡米歇尔数，那么至少一半的

　　<math>a\in(\mathbb/n\mathbb)^*</math>

　　是 Fermat witnesses。在这里，令 a 为Fermat witness 、 a1, a2, ..., as 为 Fermat liars。那么

　　<math>(a\cdot a_i)^ \equiv a^\cdot a_i^ \equiv a^ \not\equiv 1\pmod</math>

　　所有的 a × ai for i = 1, 2, ..., s 都是 Fermat witnesses 。

加密程序PGP在算法当中用到了这个素性检验方法。

2.2 费马小定理

         费马小定理是数论中的一个重要定理，其内容为： 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p） 假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1。

 

2.3实现一个大素数生成算法流程

         在实际应用中根据上述检验算法用计算机产生素数时 可先通过一些方法对x 进行过滤。比如过滤掉所有偶数从而达到提高素数生成的目的 其具体方法和步骤如下

(1) 产生一个k 位的随机二进制数x

(2) 设高位和低位为1 设高位为1 是为了保证位数设低位为1 是为了保证所选的将要进行检测的随机数是奇数过滤掉所有偶数。

(3) 检查以确保x 是否可以被百位( 或千位) 以内的小素数整除 如3 5 7 11等等 因为判断x 是否能被小素数整除所需要的时间比用上面介绍的检测方法所完成的时间短很多所以可以先选择一些适当的小素数进行整除判断然后再用Rabin_Miller的算法进行进一步的检测一般来说整除100 以内的所有素数可排除76% 不是素数的可能性 整除256 以内的所有素数可排除80% 不是素数的可能性。

测试的数越大排除不是素数的可能性也就越大 但相应的运行时间也就越长 比较有效的方法是测试小于2000的素数。

(4) 对某随机数a 运行Rabix-Miller检测如果x 通过则另外产生一个随机数a 再测试 选取较小的a 值以保证速度 做5 次Rabin-Miller 测试 如果x 在其中失败重新产生x 再测试如果x 通过测试x 不是素数的概率低于千分之一 实际应用中发现x 不是素数还要低很多 因此若x 通过测试就可作为准素数使用。

        

三、实验结果

 

四、实验小结

         本次实验难度较大。我就把素数的位数默认为15位，这样运行速度可以加快点。如果还有生成更多位数的素数，检验的使用会带来很多问题，比如出现准素数的情况。虽然这样会没有多大难度了。但是也使可以体现大素数。

源代码：

 

1. import java.math.BigInteger; 
2. import java.awt.*; 
3. import javax.swing.*; 
4. import java.awt.event.*; 
5. import java.io.*; 
6. public class Prime extends WindowAdapter implements ActionListener,ItemListener{ 
7.  
8.         String st; 
9.         String en; 
10.         String re; 
11.         //标签//////////////////////////////////////////////// 
12.         Label l1=new Label("第一个素数:"),l2=new Label("再次个素数:"),l3=new Label("是否是素数：");  
13.         //Label l4=new Label("是否是素数："); 
14.         JFrame f; 
15.         TextField ta1=new TextField(70),ta2=new TextField(70),ta3=new TextField(70); 
16.         TextField ta4=new TextField(8); 
17.         //TextField ta5=new TextField(8); 
18.         Button b1=new Button("生成素数"),b2=new Button("检验素数"),b3=new Button("再次生成"); 
19.         Choice c1; 
20.         Panel p1,p2,p3,p4,p5,p6,p7,p8,p9; 
21.         public void display(){ 
22.         f=new JFrame("中国矿业大学密码学课程设计 学号：08093739 欧二强 "); 
23.         f.setSize(600,300); 
24.         f.setLocation(200,140); 
25.         f.setBackground(Color.lightGray); 
26.         f.setLayout(new BorderLayout()); 
27.         tiajiazujian(); 
28.         f.setVisible(true); 
29.     } 
30.     /*添加界面组件以及监听器*/ 
31.     public void tiajiazujian(){  
32.         //选择按钮 
33.         c1=new Choice(); 
34.         c1.add("实现一个大素数生成算法");//c1.add("仿射算法");c1.add("维吉尼亚算法");c1.add("置换算法");c1.add("实现分组密码算法DES  默认密钥为：cumtcs");c1.add("实现公钥密码算法RSA"); 
35.         c1.addItemListener(this); 
36.         f.add(c1,"North"); 
37.         p1=new Panel(); 
38.         p3=new Panel(); 
39.         f.add(p3,"Center"); 
40.         p3.setLayout(new FlowLayout()); 
41.         p3.add(l1);p3.add(ta1);p3.add(l2);p3.add(ta2);p3.add(l3);p3.add(ta3); 
42.         //p3.add(l4);p3.add(ta4); 
43.         p2=new Panel(); 
44.         f.add(p2,"South"); 
45.         p2.setLayout(new GridLayout(1,5)); 
46.         p2.add(b1);p2.add(b2);p2.add(b3);; 
47.         b1.addActionListener(this); 
48.         b2.addActionListener(this); 
49.         b3.addActionListener(this); 
50.     } 
51.     /*对应不同加密算法的按钮点击事件*/ 
52.     public void actionPerformed(ActionEvent e){                      
53.         if (e.getSource()==b3&&c1.getSelectedIndex()==0){//第三个按钮 
54.             sushu3(); 
55.         } 
56.         if (e.getSource()==b1&&c1.getSelectedIndex()==0)//第一个按钮 
57.         { 
58.             sushu1(); 
59.         } 
60.          
61.         if(e.getSource()==b2&&c1.getSelectedIndex()==0){//第二个按钮 
62.             sushu2(); 
63.         } 
64.      
65.     } 
66.  
67.     public void itemStateChanged(ItemEvent e){ 
68.      
69.      
70.     } 
71.  
72.     //实现一个大素数生成算法 
73.     public void sushu1(){ 
74.         int numDigits; 
75.         try { 
76.             numDigits = Integer.parseInt("15"); 
77.         } catch (Exception e) { 
78.             numDigits = 128; 
79.         } 
80.         BigInteger start = bigRandom(numDigits); 
81.  
82.         start = nextPrime(start); 
83.         BigInteger end = bigRandom(5); 
84.         end = nextPrime(end); 
85.  
86.         BigInteger result = start.multiply(end); 
87.         st=start.toString(); 
88.         en=start.toString(); 
89.         re=start.toString(); 
90.         ta1.setText(st); 
91.  
92.     } 
93.  
94.     public void sushu2(){ 
95.         double do1=Double.parseDouble(st); 
96.         String ss21=fun(do1); 
97.         ta3.setText(en+"-->"+ss21); 
98.          
99.     } 
100.     public void sushu3(){ 
101.         int numDigits; 
102.         try { 
103.             numDigits = Integer.parseInt("15"); 
104.         } catch (Exception e) { 
105.             numDigits = 128; 
106.         } 
107.         BigInteger start = bigRandom(numDigits); 
108.  
109.         start = nextPrime(start); 
110.         BigInteger end = bigRandom(5); 
111.         end = nextPrime(end); 
112.         BigInteger result = start.multiply(end); 
113.         st=start.toString(); 
114.         en=start.toString(); 
115.         re=start.toString(); 
116.         ta2.setText(en); 
117.  
118.     } 
119.  
120.  
121.  
122.  
123.     // 下面的 BigInteger.ZERO 和 BigInteger.ONE 在 JDK 1.1 中是无效的 
124.     private static final BigInteger ZERO = BigInteger.ZERO; 
125.     private static final BigInteger ONE = BigInteger.ONE; 
126.     private static final BigInteger TWO = new BigInteger("2"); 
127.      
128.     // 产生一个错误素数的概率小于 1/2 的 ERR_VAL 次方，可以将 ERR_VAL 定义为 200，降低其错误率 
129.     // Java 应该使用的是 Miller-Rabin 测试法，这种错误概率基本上可以认为是无错误。 
130.     private static final int ERR_VAL = 100; 
131.     private static StringBuffer[] digits = { new StringBuffer("0"), new StringBuffer("1"), new StringBuffer("2"), new StringBuffer("3"), new StringBuffer("4"), new StringBuffer("5"), 
132.         new StringBuffer("6"), new StringBuffer("7"), new StringBuffer("8"), new StringBuffer("9") }; 
133.  
134.     private static StringBuffer randomDigit(boolean isZeroOK) { 
135.         // 产生一个随机的数字（字符串形式的），isZeroOK 决定这个数字是否可以为 0 
136.         int index; 
137.         if (isZeroOK) 
138.             index = (int) Math.floor(Math.random() * 10); 
139.         else 
140.             index = 1 + (int) Math.floor(Math.random() * 9); 
141.         return (digits[index]); 
142.     } 
143.  
144.     public static BigInteger bigRandom(int numDigits) { 
145.         // 产生一个随机大整数，各位上的数字都是随机产生的，首位不为 0 
146.         StringBuffer s = new StringBuffer(""); 
147.         for (int i = 0; i < numDigits; i++) 
148.             if (i == 0) 
149.                 s.append(randomDigit(false)); 
150.             else 
151.                 s.append(randomDigit(true)); 
152.         return (new BigInteger(s.toString())); 
153.     } 
154.  
155.     private static boolean isEven(BigInteger n) { 
156.         // 测试一个大整数是否为偶数 
157.         return (n.mod(TWO).equals(ZERO)); 
158.     } 
159.  
160.     public static BigInteger nextPrime(BigInteger start) { 
161.         // 产生一个比给定大整数 start 大的素数，错误率低于 1/2 的 ERR_VAL 次方 
162.         if (isEven(start)) 
163.             startstart = start.add(ONE); 
164.         else 
165.             startstart = start.add(TWO); 
166.         if (start.isProbablePrime(ERR_VAL)) 
167.             return (start); 
168.         else 
169.             // 采用递归方式（递归的层数会是个天文数字吗？） 
170.             return (nextPrime(start)); 
171.     } 
172.         //租主方法 
173.     public static void main(String arg[]){ 
174.         Prime ob=new Prime(); 
175.         ob.display(); 
176.     } 
177.  
178.  
179.     //判断素数//////////////////////////////////////////////////////////////////////////////////// 
180.     public String fun(double n){ 
181.         boolean isPrime = true; 
182.         //如果n大于2 继续判断 否则 isPrime的值不变 2素数 
183.         if(n>2){ 
184.         //如果n是大于2的偶数 认定不是素数 修改变量值为false 
185.             if(n%2==0){ 
186.                 isPrime=false;} 
187.             else{ 
188.         //循环判断如果找到一个可以整除的数 则判定不是素数跳出循环 因为是判断奇数 因此 2 4 6 ...? 
189.         //不用考虑 循环递增2 即?3 5 7 ... 
190.                 for(int i=3;i<=(int)Math.sqrt(n);i+=2){ 
191.                     if(n%i==0){ 
192.                     isPrime=false; 
193.                     break;}} 
194.         } 
195.              
196. } 
197.         if(isPrime==true) 
198.             return "是素数"; 
199.         else 
200.             return "不是素数"; 
201.  
202.     } 
203.  
204.  
205.  
206. }