信息计算2019级1班22号李浩栋

李浩栋

RSA

算法原理：

　　RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

实现代码：

GCD.java：

1. import java.math.BigInteger;
   
2. 
   
3. public class GCD {
   
4. 
   
5.     public BigInteger MaxFactor(BigInteger value1,BigInteger value2){
   
6. 
   
7. 
   
8.         BigInteger zero = new BigInteger("0");
   
9. 
   
10.         while (true){
    
11. 
    
12.             BigInteger dividend = new BigInteger(value1.max(value2).toString());
    
13. 
    
14.             BigInteger divisor = new BigInteger(value1.min(value2).toString());
    
15. 
    
16.             if(dividend.remainder(divisor).equals(zero)){
    
17. 
    
18.                 return divisor;
    
19. 
    
20.             }
    
21.             else{
    
22. 
    
23.                 value1 = value1.min(value2);
    
24. 
    
25.                 value2 = dividend.remainder(divisor);
    
26. 
    
27.             }
    
28. 
    
29.         }
    
30. 
    
31.     }
    
32. 
    
33. }
    

复制代码

HightEXPMod.java：

1. import java.math.BigInteger;
   
2. 
   
3. public class HightEXPMod {
   
4. 
   
5.     public BigInteger computeHightEXPMod(BigInteger value, BigInteger exponent, BigInteger modValue){
   
6. 
   
7. 
   
8.         BigInteger result = new BigInteger("1");
   
9. 
   
10.         BigInteger zero = new BigInteger("0");
    
11. 
    
12.         BigInteger two = new BigInteger("2");
    
13. 
    
14.         BigInteger one = new BigInteger("1");
    
15. 
    
16.         while (!exponent.equals(zero)){
    
17. 
    
18.             if(!exponent.remainder(two).equals(zero)){
    
19. 
    
20.                 result = result.multiply(value).remainder(modValue);
    
21. 
    
22.                 exponent = exponent.subtract(one);
    
23. 
    
24.             }
    
25.             else {
    
26. 
    
27.                 while (exponent.remainder(two).equals(zero)){
    
28. 
    
29.                     exponent = exponent.divide(two);
    
30. 
    
31.                     value = value.multiply(value).remainder(modValue);
    
32. 
    
33.                 }
    
34. 
    
35.             }
    
36. 
    
37.         }
    
38. 
    
39.         return result;
    
40.     }
    
41. }
    

复制代码

InverseMod.java：

1. import java.math.BigInteger;
   
2. 
   
3. public class InverseMod {
   
4. 
   
5.     public BigInteger computeModInverse(BigInteger value, BigInteger modValue){
   
6. 
   
7.         GCD gcd = new GCD();
   
8. 
   
9.         BigInteger one = new BigInteger("1");
   
10. 
    
11.         BigInteger zero = new BigInteger("0");
    
12. 
    
13.         if(gcd.MaxFactor(value,modValue).equals(one)){
    
14. 
    
15.             BigInteger n1 = new BigInteger(modValue.toString());
    
16. 
    
17.             BigInteger n2 = new BigInteger(value.toString());
    
18. 
    
19.             BigInteger b1 = new BigInteger("0");
    
20. 
    
21.             BigInteger b2 = new BigInteger("1");
    
22. 
    
23.             BigInteger q = n1.divide(n2);
    
24. 
    
25.             BigInteger r = n1.subtract(q.multiply(n2));
    
26. 
    
27.             BigInteger t = new BigInteger("0");
    
28. 
    
29.             while(true){
    
30. 
    
31.                 if(!r.equals(zero)){
    
32. 
    
33.                     n1 = n2;
    
34. 
    
35.                     n2 = r;
    
36. 
    
37.                     t = b2;
    
38. 
    
39.                     b2 = b1.subtract(q.multiply(b2));
    
40. 
    
41.                     b1 = t;
    
42. 
    
43.                     q = n1.divide(n2);
    
44. 
    
45.                     r = n1.subtract(q.multiply(n2));
    
46. 
    
47.                 }
    
48.                 else{
    
49. 
    
50.                     if(!n2.equals(one)){
    
51. 
    
52.                         return zero;
    
53.                     }
    
54.                     else if(n2.equals(one)){
    
55. 
    
56.                         if (b2.compareTo(zero) < 0){
    
57. 
    
58.                             return b2.add(modValue);
    
59. 
    
60.                         }
    
61.                         else{
    
62. 
    
63.                             return b2.remainder(modValue);
    
64.                         }
    
65.                     }
    
66. 
    
67.                 }
    
68.             }
    
69.         }
    
70.         else {
    
71. 
    
72.             return zero;
    
73. 
    
74.         }
    
75.     }
    
76. }
    

复制代码

PrimeNumber.java：

1. import java.math.BigInteger;
   
2. import java.util.Random;
   
3. 
   
4. public class PrimeNumber {
   
5. 
   
6.     public BigInteger getPrimeNumber(){
   
7. 
   
8.         while(true){
   
9. 
   
10.             Random random = new Random();
    
11. 
    
12.             BigInteger primeNumber = BigInteger.probablePrime(1024,random);
    
13. 
    
14.             if(judgePrimeNumber(primeNumber)){
    
15. 
    
16.                 return primeNumber;
    
17. 
    
18.             }
    
19. 
    
20.         }
    
21. 
    
22.     }
    
23. 
    
24.     public static boolean judgePrimeNumber(BigInteger primeNumber_pro){
    
25. 
    
26.         int s = 0;
    
27. 
    
28.         BigInteger primeNumber_m = new BigInteger(primeNumber_pro.toString());
    
29. 
    
30.         BigInteger one = new BigInteger("1");
    
31. 
    
32.         BigInteger zero = new BigInteger("0");
    
33. 
    
34.         BigInteger two = new BigInteger("2");
    
35. 
    
36.         primeNumber_m = primeNumber_m.subtract(one);
    
37. 
    
38.         while (true){
    
39. 
    
40.             if(primeNumber_m.remainder(two).equals(zero)){
    
41. 
    
42.                 s += 1;
    
43. 
    
44.                 primeNumber_m = primeNumber_m.divide(two);
    
45. 
    
46.             }
    
47.             else {
    
48. 
    
49.                 break;
    
50. 
    
51.             }
    
52.         }
    
53. 
    
54.         while (true){
    
55. 
    
56.             Random random = new Random();
    
57. 
    
58.             int lenght = (int)(Math.random() * 1024);
    
59. 
    
60.             BigInteger divide = BigInteger.probablePrime(lenght,random);
    
61. 
    
62.             BigInteger b = primeNumber_pro.subtract(one).divide(divide);
    
63. 
    
64.             int r = 0;
    
65. 
    
66.             HightEXPMod hightEXPMod = new HightEXPMod();
    
67. 
    
68.             BigInteger z = hightEXPMod.computeHightEXPMod(b,primeNumber_m,primeNumber_pro);
    
69. 
    
70.             while(true){
    
71. 
    
72.                 if(z.equals(one) || z.equals(primeNumber_pro.subtract(one))){
    
73. 
    
74.                     return true;
    
75. 
    
76.                 }
    
77.                 else{
    
78. 
    
79.                     while(true){
    
80. 
    
81.                         if(r == s - 1){
    
82. 
    
83.                             return false;
    
84. 
    
85.                         }
    
86.                         else{
    
87. 
    
88.                             r += 1;
    
89. 
    
90.                             z = hightEXPMod.computeHightEXPMod(z,two,primeNumber_pro);
    
91. 
    
92.                             if(z.equals(primeNumber_pro.subtract(one))){
    
93. 
    
94.                                 return true;
    
95. 
    
96.                             }
    
97.                             else {
    
98. 
    
99.                             }
    
100. 
     
101.                         }
     
102. 
     
103.                     }
     
104. 
     
105.                 }
     
106. 
     
107.             }
     
108.         }
     
109. 
     
110.     }
     
111. }
     

复制代码

RSAEncipher.java：

1. import java.math.BigInteger;
   
2. import java.util.Scanner;
   
3. import java.util.zip.Inflater;
   
4. 
   
5. public class RSAEncipher {
   
6. 
   
7.     static String information = null;
   
8. 
   
9.     public static void main(String[] args) {
   
10. 
    
11.         System.out.print("input information to encipher: ");
    
12. 
    
13.         Scanner inpute = new Scanner(System.in);
    
14. 
    
15.         information = inpute.nextLine();
    
16. 
    
17.         information = Encipher(information);
    
18. 
    
19.         System.out.println(information);
    
20.         
    
21. 
    
22.     }
    
23. 
    
24.     public static String Encipher(String information){
    
25. 
    
26.         PrimeNumber primeNumber = new PrimeNumber();
    
27. 
    
28.         BigInteger one = new BigInteger("1");
    
29. 
    
30.         BigInteger zero = new BigInteger("0");
    
31. 
    
32.         BigInteger p = primeNumber.getPrimeNumber();
    
33. 
    
34.         BigInteger q = primeNumber.getPrimeNumber();
    
35. 
    
36.         BigInteger n = p.multiply(q);
    
37. 
    
38.         BigInteger $n = p.subtract(one).multiply(q.subtract(one));
    
39. 
    
40.         BigInteger e = primeNumber.getPrimeNumber();
    
41. 
    
42.         GCD gcd = new GCD();
    
43. 
    
44.         InverseMod inverseMod = new InverseMod();
    
45. 
    
46.         while(!gcd.MaxFactor(e,$n).equals(one) || inverseMod.computeModInverse(e,$n).equals(zero)){
    
47. 
    
48.             e = primeNumber.getPrimeNumber();
    
49.         }
    
50. 
    
51.         BigInteger d = inverseMod.computeModInverse(e,$n);
    
52. 
    
53.         HightEXPMod hightEXPMod = new HightEXPMod();
    
54. 
    
55.         String information_encipher = "";
    
56. 
    
57.         for(int i = 0; i < information.length();i++){
    
58. 
    
59.             int c_value = (int)(information.charAt(i));
    
60. 
    
61.             BigInteger information_m = new BigInteger(c_value + "");
    
62. 
    
63.             information_m = hightEXPMod.computeHightEXPMod(information_m,e,n);
    
64. 
    
65.             System.out.println(information_m.toString());
    
66. 
    
67.             information_m = hightEXPMod.computeHightEXPMod(information_m,d,n);
    
68. 
    
69.             char c = (char) Integer.parseInt(information_m.toString());
    
70. 
    
71.             information_encipher += c;
    
72.         }
    
73. 
    
74.         return information_encipher;
    
75.     }
    
76. }
    

复制代码

运行截图：

李浩栋

椭圆曲线加密（ECC）

ecc简介：

　　椭圆曲线加密，全称EllipseCurve Cryptography，简称ECC。与传统的基于大素数因数分解难题的方式不同，ECC通过椭圆曲线的方式产生密钥。相比RSA，ECC优势是可以使用更短的密钥，来实现与RSA相当或更高的安全。

题目设计：

(1)编程计算该椭圆曲线上所有在有限域GF(89)上的点；
(2)编程实现椭圆曲线上任意一个点P(例如P=(12,5))的倍点运算的递归算法，即计算k*P( k=2,3,…)；（重点！）
(3)利用此递归算法找出椭圆曲线上的所有生成元G以及它们的阶n，即满足n*G=O；
(4)设计实现某一用户B的公钥、私钥算法，即得到public key=(n, G, PB, Ep(a, b))
secure key=nB(小于n)
(5)假如用户A发送明文消息“yes”并加密传输给用户B，用户B接收消息后要能解密为明文。试用ECC密码体制实现此功能。

李浩栋

实现代码：
ecc.cpp：

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<string.h>
   
4. #include<math.h>
   
5. #include<time.h>
   
6. #define MAX 100
   
7. 
   
8. typedef struct point {
   
9.         int point_x;
   
10.         int point_y;
    
11. }Point;
    
12. typedef struct ecc {
    
13.         struct point p[MAX];
    
14.         int len;
    
15. }ECCPoint;
    
16. typedef struct generator {
    
17.         Point p;
    
18.         int p_class;
    
19. }GENE_SET;
    
20. 
    
21. void get_all_points();
    
22. int int_sqrt(int s);
    
23. Point timesPiont(int k, Point p);
    
24. Point add_two_points(Point p1, Point p2);
    
25. int inverse(int n, int b);
    
26. void get_generetor_class();
    
27. void encrypt_ecc();
    
28. void decrypt_ecc();
    
29. int mod_p(int s);
    
30. void print();
    
31. int isPrime(int n);
    
32. 
    
33. char alphabet[27] = "abcdefghijklmnopqrstuvwxyz";
    
34. int a = -1, b = 0, p = 89;//椭圆曲线为E89(-1,0)： y2=x3-x (mod 89)
    
35. ECCPoint eccPoint;
    
36. GENE_SET geneSet[MAX];
    
37. int geneLen;
    
38. char plain[] = "yes";
    
39. int m[MAX];
    
40. int cipher[MAX];
    
41. int nB;//私钥
    
42. Point P1, P2, Pt, G, PB;
    
43. Point Pm;
    
44. int C[MAX];
    
45. 
    
46. int main()
    
47. {
    
48.         get_generetor_class();
    
49.         encrypt_ecc();
    
50.         decrypt_ecc();
    
51.         return 0;
    
52. }
    
53. //task4:加密
    
54. void encrypt_ecc()
    
55. {
    
56.         int num, i, j;
    
57.         int gene_class;
    
58.         int num_t;
    
59.         int k;
    
60.         srand(time(NULL));
    
61.         //明文转换过程
    
62.         for (i = 0; i < strlen(plain); i++)
    
63.         {
    
64.                 for (j = 0; j < 26; j++) //for(j=0;j<26;j++)
    
65.                 {
    
66.                         if (plain[i] == alphabet[j])
    
67.                         {
    
68.                                 m[i] = j;//将字符串明文换成数字，并存到整型数组m里面
    
69.                         }
    
70.                 }
    
71.         }
    
72.         //选择生成元
    
73.         num = rand() % geneLen;
    
74.         gene_class = geneSet[num].p_class;
    
75.         while (isPrime(gene_class) == -1)//不是素数
    
76.         {
    
77.                 num = rand() % (geneLen - 3) + 3;
    
78.                 gene_class = geneSet[num].p_class;
    
79.         }
    
80.         //printf("gene_class=%d\n",gene_class);
    
81.         G = geneSet[num].p;
    
82.         //printf("G:(%d,%d)\n",geneSet[num].p.point_x,geneSet[num].p.point_y);
    
83.         nB = rand() % (gene_class - 1) + 1;//选择私钥
    
84.         PB = timesPiont(nB, G);
    
85.         printf("\n公钥：\n");
    
86.         printf("{y^2=x^3%d*x+%d,%d,(%d,%d),(%d,%d)}\n", a, b, gene_class, G.point_x, G.point_y, PB.point_x, PB.point_y);
    
87.         printf("私钥：\n");
    
88.         printf("nB=%d\n", nB);
    
89.         //加密
    
90.         //
    
91.         k = rand() % (gene_class - 2) + 1;
    
92.         P1 = timesPiont(k, G);
    
93.         //
    
94.         num_t = rand() % eccPoint.len; //选择映射点
    
95.         Pt = eccPoint.p[num_t];
    
96.         //printf("Pt:(%d,%d)\n",Pt.point_x,Pt.point_y);
    
97.         P2 = timesPiont(k, PB);
    
98.         Pm = add_two_points(Pt, P2);
    
99.         printf("加密数据：\n");
    
100.         printf("kG=(%d,%d),Pt+kPB=(%d,%d),C={", P1.point_x, P1.point_y, Pm.point_x, Pm.point_y);
     
101.         for (i = 0; i < strlen(plain); i++)
     
102.         {
     
103.                 //                num_t=rand()%eccPoint.len; //选择映射点
     
104.                 //                Pt=eccPoint.p[num_t];
     
105.                 C[i] = m[i] * Pt.point_x + Pt.point_y;
     
106.                 printf("{%d}", C[i]);
     
107.         }
     
108.         printf("}\n");
     
109. }
     
110. //task5:解密
     
111. void decrypt_ecc()
     
112. {
     
113.         Point temp, temp1;
     
114.         int m, i;
     
115.         temp = timesPiont(nB, P1);
     
116.         temp.point_y = 0 - temp.point_y;
     
117.         temp1 = add_two_points(Pm, temp);//求解Pt
     
118. //        printf("(%d,%d)\n",temp.point_x,temp.point_y);
     
119. //        printf("(%d,%d)\n",temp1.point_x,temp1.point_y);
     
120.         printf("\n解密结果：\n");
     
121.         for (i = 0; i < strlen(plain); i++)
     
122.         {
     
123.                 m = (C[i] - temp1.point_y) / temp1.point_x;
     
124.                 printf("%c", alphabet[m]);//输出密文
     
125.         }
     
126.         printf("\n");
     
127. }
     
128. //判断是否为素数
     
129. int isPrime(int n)
     
130. {
     
131.         int i, k;
     
132.         k = sqrt(n);
     
133.         for (i = 2; i <= k; i++)
     
134.         {
     
135.                 if (n % i == 0)
     
136.                         break;
     
137.         }
     
138.         if (i <= k) {
     
139.                 return -1;
     
140.         }
     
141.         else {
     
142.                 return 0;
     
143.         }
     
144. }
     
145. //task3:求生成元以及阶
     
146. void get_generetor_class()
     
147. {
     
148.         int i, j = 0;
     
149.         int count = 1;
     
150.         Point p1, p2;
     
151.         get_all_points();
     
152.         //        p1.point_x=p2.point_x=3;
     
153.         //        p1.point_y=p2.point_y=2;
     
154.         //        while(1)
     
155.         //        {
     
156.         //                printf("(%d,%d)+(%d,%d)---%d\n",p1.point_x,p1.point_y,p2.point_x,p2.point_y,count);
     
157.         //                p2=add_two_points(p1,p2);
     
158.         //                count++;
     
159.         //                if(p2.point_x==-1 && p2.point_y==-1)
     
160.         //                {
     
161.         //                        break;
     
162.         //                }
     
163.         //        }
     
164.         //        printf("\n\n(%d,%d)---%d\n",p1.point_x,p1.point_y,count);
     
165.                 //
     
166.         //        do{
     
167.         //                        printf("(%d,%d)+(%d,%d)---%d\n",p1.point_x,p1.point_y,p2.point_x,p2.point_y,count);
     
168.         //                        p2=add_two_points(p1,p2);
     
169.         //                        count++;
     
170.         //                       
     
171.         //        } while(!((p2.point_x==p1.point_x)&&(p2.point_y==p1.point_y)));
     
172.         //        printf("(%d,%d)+(%d,%d)---%d\n",p1.point_x,p1.point_y,p2.point_x,p2.point_y,count);
     
173.         //        count ++ ;
     
174.         //        printf("\n\n(%d,%d)---%d\n",p1.point_x,p1.point_y,count);
     
175.         printf("\n**********************************输出生成元以及阶：*************************************\n");
     
176.         for (i = 0; i < eccPoint.len; i++)
     
177.         {
     
178.                 count = 1;
     
179.                 p1.point_x = p2.point_x = eccPoint.p[i].point_x;
     
180.                 p1.point_y = p2.point_y = eccPoint.p[i].point_y;
     
181.                 while (1)
     
182.                 {
     
183.                         p2 = add_two_points(p1, p2);
     
184.                         if (p2.point_x == -1 && p2.point_y == -1)
     
185.                         {
     
186.                                 break;
     
187.                         }
     
188.                         count++;
     
189.                         if (p2.point_x == p1.point_x)
     
190.                         {
     
191.                                 break;
     
192.                         }
     
193.                 }
     
194.                 count++;
     
195.                 if (count <= eccPoint.len + 1)
     
196.                 {
     
197.                         geneSet[j].p.point_x = p1.point_x;
     
198.                         geneSet[j].p.point_y = p1.point_y;
     
199.                         geneSet[j].p_class = count;
     
200.                         printf("(%d,%d)--->>%d\t", geneSet[j].p.point_x, geneSet[j].p.point_y, geneSet[j].p_class);
     
201.                         j++;
     
202.                         if (j % 6 == 0) {
     
203.                                 printf("\n");
     
204.                         }
     
205.                 }
     
206.                 geneLen = j;
     
207.         }
     
208. }

复制代码

接上：

1. //task2:倍点运算的递归算法
   
2. Point timesPiont(int k, Point p0)
   
3. {
   
4.         if (k == 1) {
   
5.                 return p0;
   
6.         }
   
7.         else if (k == 2) {
   
8.                 return add_two_points(p0, p0);
   
9.         }
   
10.         else {
    
11.                 return add_two_points(p0, timesPiont(k - 1, p0));
    
12.         }
    
13. }
    
14. 
    
15. //两点的加法运算
    
16. Point add_two_points(Point p1, Point p2)
    
17. {
    
18.         long t;
    
19.         int x1 = p1.point_x;
    
20.         int y1 = p1.point_y;
    
21.         int x2 = p2.point_x;
    
22.         int y2 = p2.point_y;
    
23.         int tx, ty;
    
24.         int x3, y3;
    
25.         int flag = 0;
    
26.         //求
    
27.         if ((x2 == x1) && (y2 == y1))
    
28.         {
    
29.                 //相同点相加
    
30.                 if (y1 == 0)
    
31.                 {
    
32.                         flag = 1;
    
33.                 }
    
34.                 else {
    
35.                         t = (3 * x1 * x1 + a) * inverse(p, 2 * y1) % p;
    
36.                 }
    
37.                 //printf("inverse(p,2*y1)=%d\n",inverse(p,2*y1));
    
38.         }
    
39.         else {
    
40.                 //不同点相加
    
41.                 ty = y2 - y1;
    
42.                 tx = x2 - x1;
    
43.                 while (ty < 0)
    
44.                 {
    
45.                         ty += p;
    
46.                 }
    
47.                 while (tx < 0)
    
48.                 {
    
49.                         tx += p;
    
50.                 }
    
51.                 if (tx == 0 && ty != 0)
    
52.                 {
    
53.                         flag = 1;
    
54.                 }
    
55.                 else {
    
56.                         t = ty * inverse(p, tx) % p;
    
57.                 }
    
58.         }
    
59.         if (flag == 1)
    
60.         {
    
61.                 p2.point_x = -1;
    
62.                 p2.point_y = -1;
    
63.         }
    
64.         else {
    
65.                 x3 = (t * t - x1 - x2) % p;
    
66.                 y3 = (t * (x1 - x3) - y1) % p;
    
67.                 //使结果在有限域GF(P)上
    
68.                 while (x3 < 0)
    
69.                 {
    
70.                         x3 += p;
    
71.                 }
    
72.                 while (y3 < 0)
    
73.                 {
    
74.                         y3 += p;
    
75.                 }
    
76.                 p2.point_x = x3;
    
77.                 p2.point_y = y3;
    
78.         }
    
79.         return p2;
    
80. }
    
81. //求b关于n的逆元
    
82. int inverse(int n, int b)
    
83. {
    
84.         int q, r, r1 = n, r2 = b, t, t1 = 0, t2 = 1, i = 1;
    
85.         while (r2 > 0)
    
86.         {
    
87.                 q = r1 / r2;
    
88.                 r = r1 % r2;
    
89.                 r1 = r2;
    
90.                 r2 = r;
    
91.                 t = t1 - q * t2;
    
92.                 t1 = t2;
    
93.                 t2 = t;
    
94.         }
    
95.         if (t1 >= 0)
    
96.                 return t1 % n;
    
97.         else {
    
98.                 while ((t1 + i * n) < 0)
    
99.                         i++;
    
100.                 return t1 + i * n;
     
101.         }
     
102. }
     
103. //task1:求出椭圆曲线上所有点
     
104. void get_all_points()
     
105. {
     
106.         int i = 0;
     
107.         int j = 0;
     
108.         int s, y = 0;
     
109.         int n = 0, q = 0;
     
110.         int modsqrt = 0;
     
111.         int flag = 0;
     
112.         if (4 * a * a * a + 27 * b * b != 0)
     
113.         {
     
114.                 for (i = 0; i <= p - 1; i++)
     
115.                 {
     
116.                         flag = 0;
     
117.                         n = 1;
     
118.                         y = 0;
     
119.                         s = i * i * i + a * i + b;
     
120.                         while (s < 0)
     
121.                         {
     
122.                                 s += p;
     
123.                         }
     
124.                         s = mod_p(s);
     
125.                         modsqrt = int_sqrt(s);
     
126.                         if (modsqrt != -1)
     
127.                         {
     
128.                                 flag = 1;
     
129.                                 y = modsqrt;
     
130.                         }
     
131.                         else {
     
132.                                 while (n <= p - 1)
     
133.                                 {
     
134.                                         q = s + n * p;
     
135.                                         modsqrt = int_sqrt(q);
     
136.                                         if (modsqrt != -1)
     
137.                                         {
     
138.                                                 y = modsqrt;
     
139.                                                 flag = 1;
     
140.                                                 break;
     
141.                                         }
     
142.                                         flag = 0;
     
143.                                         n++;
     
144.                                 }
     
145.                         }
     
146.                         if (flag == 1)
     
147.                         {
     
148.                                 eccPoint.p[j].point_x = i;
     
149.                                 eccPoint.p[j].point_y = y;
     
150.                                 j++;
     
151.                                 if (y != 0)
     
152.                                 {
     
153.                                         eccPoint.p[j].point_x = i;
     
154.                                         eccPoint.p[j].point_y = (p - y) % p;
     
155.                                         j++;
     
156.                                 }
     
157.                         }
     
158.                 }
     
159.                 eccPoint.len = j;//点集个数
     
160.                 print(); //打印点集
     
161.         }
     
162. }
     
163. 
     
164. //取模函数
     
165. int mod_p(int s)
     
166. {
     
167.         int i;        //保存s/p的倍数
     
168.         int result;        //模运算的结果
     
169.         i = s / p;
     
170.         result = s - i * p;
     
171.         if (result >= 0)
     
172.         {
     
173.                 return result;
     
174.         }
     
175.         else
     
176.         {
     
177.                 return result + p;
     
178.         }
     
179. }
     
180. 
     
181. //判断平方根是否为整数
     
182. int int_sqrt(int s)
     
183. {
     
184.         int temp;
     
185.         temp = (int)sqrt(s);//转为整型
     
186.         if (temp * temp == s)
     
187.         {
     
188.                 return temp;
     
189.         }
     
190.         else {
     
191.                 return -1;
     
192.         }
     
193. }
     
194. //打印点集
     
195. void print()
     
196. {
     
197.         int i;
     
198.         int len = eccPoint.len;
     
199.         printf("\n该椭圆曲线上共有%d个点(包含无穷远点)\n", len + 1);
     
200.         for (i = 0; i < len; i++)
     
201.         {
     
202.                 if (i % 8 == 0)
     
203.                 {
     
204.                         printf("\n");
     
205.                 }
     
206.                 printf("(%2d,%2d)\t", eccPoint.p[i].point_x, eccPoint.p[i].point_y);
     
207.         }
     
208.         printf("\n");
     
209. }

复制代码

运行截图：