信息安全数学基础——模重复平方计算法（两种方法实现C+JAVA）

你好，我是罡罡同学！
代码谱第一页忘掉心上人，最后一页。。。。。。

前言

正在学习信息安全数学基础这门课程。
编程实现模重复平方计算法。

---

先介绍一下模重复平方算法

一、模重复平方算法

图片来自大学MOOC陈恭亮老师的视频中，稍有模糊。。。

下面我们用C语言来实现这个算法。我们可以思考一下，这个算法一共可以分为几个小部分？
首先，我们需要一个十进制转化为二进制的函数，主要用于将指数转化为二进制形式；
我们还需要知道，我们的循环计算需要执行多少次，所以我们需要一个函数来确定指数的位数；
最后一个函数就是我们的模重复平方计算函数了。当然我们还可以来定义一个打印函数。

废话不多说，上代码！！！

上代码！

#include<stdio.h>
#include<math.h>
int O_Binary(int n,int a[])//十进制转化为二进制函数 
{ int i,j,m; 
 for(m=0;m<15;m++)
 { i=n%2;
  j=n/2;
  n=j;
  a[m]=i;
 }
 for(m=15;m>=0;m--)//将数组倒序输出 
 { printf("%d",a[m]);
  if(m%4==0)//每隔四个数字打印一个空格 
   printf(" ");
 }
 printf("\n");
 return 0;
}
int judge_O_bit(int n)//表达十进制所需的位数 
{ int i=1;
 while(i)
 { if(n<pow(2,i))
  { 
   //printf("%d ",i);
   return i;
  }
  i++;
 }
}
int print(int a[])
{ int i;
 printf("将二进制存到数组中：\n\t");
 for(i=0;i<=15;i++)
 { printf("%d",a[i]);
  if((i+1)%4==0)//每隔四个数字打印一个空格 
   printf(" ");
 }
 return 0;
} 
int jisuan_Mod(int zhi,int di,int mo,int bit,int a[])//zhi 指数，di底数，mo模几，bit指数的二进制的位数  
{ int x,y,j;          //a[]存储指数的二进制，a[0]= 1 。。。。 
 printf("开始输出结果！-->>\n");
 y=di;
 for(j=0;j<bit;j++)
 { if(j==0)//第一次时 
  { x=di%mo;
   y=(y*y)%mo;
   printf("%d. n%d = %d\n",j+1,j,a[j]);
   printf("\ta%d ≡%d, b%d ≡%d(mod %d)\n",j,x,j+1,y,mo);
   continue;
  }
  if(a[j]==0&&j!=bit-1&&j!=0)//二进制为0 且不是最后一次 
  { x=x;//x不变，依旧为上一个x
   y=(y*y)%mo;
   printf("%d. n%d = %d\n",j+1,j,a[j]);
   printf("\ta%d ≡%d, b%d ≡%d(mod %d)\n",j,x,j+1,y,mo);
   continue;
  }
  else//二进制为1
  { x=(x*y)%mo; 
   if(j!=bit-1)
   { y=(y*y)%mo;//最后一次时不再算y，直接输出x即可
    printf("%d. n%d = %d\n",j+1,j,a[j]);
    printf("\ta%d ≡%d, b%d ≡%d(mod %d)\n",j,x,j+1,y,mo);continue;
   }
   printf("%d. n%d = %d\n",j+1,j,a[j]);
   printf("\ta%d ≡%d(mod %d)\n",j,x,mo);
   continue;
  }
 }
 printf("最后，计算出 %d^%d ≡%d(mod %d)",di,zhi,x,mo);
 return x;
}
int main()
{ int zhi,di,bit,i,yu,mo;
 int a[16]={0};
 printf("\t模重复平方计算\n");
 printf("请输入指数——十进制数字（0~32767）:");
 scanf("%d",&zhi);
 printf("请输入底数:");
 scanf("%d",&di);
 printf("请输入模数:");
 scanf("%d",&mo);//13的二进制位 1101 
 printf("指数转化为二进制:\n\t");
 O_Binary(zhi,a); //数组a存放指数的二进制，a[0]= 1 
 bit=judge_O_bit(zhi);
 print(a);
 printf("\n\n\n"); 
 jisuan_Mod(zhi,di,mo,judge_O_bit(zhi),a); 
 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

第一道习题，成功。
第二道习题，成功。
下面我们再用JAVA来实现第二种计算方法（这种是我们老师讲的，比较好理解）
首先还是将指数转化为二进制的形式，需要注意的是，第一次初始化，用底数乘1。当二进制的高位为1时，将底数平方再乘上底数，当元素为0时，只平方即可。
我们举个例子吧，如下图所示。

上JAVA代码！

import java.util.Scanner;
/*2020/10/31 
 *模重复平方算法(罡罡同学)
 */
public class Demo3{
 public static void main(String[] args){
  Scanner pi = new Scanner(System.in);
  System.out.print("\t模重复平方法(罡罡同学)\n请输入指数：");
  int zhi=pi.nextInt();
  System.out.print("请输入底数：");
  int di=pi.nextInt();
  System.out.print("请输入模数：");
  int mo=pi.nextInt();
  String bin1 = Integer.toBinaryString(zhi);//4位
  System.out.println("指数转化为二进制： "+bin1);
  System.out.printf("最后结果为： %d^%d ≡"+count_mod(bin1,di,mo)+"(mod%d)",di,zhi,mo);
 }
 public static int count_mod(String s,int di,int mo)
 { int result=0;
  for(int i=0;i<s.length();i++)//s.length 可以替代参数zhi
  { if(i==0)
   {
    result=(di*1)%mo;continue;
   }
   if(s.charAt(i)=='1')
   {
    result=(result*result)*di%mo;
   }
   else
   {
    result=(result*result)%mo;
   }
  }
  return result;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

程序执行结果截图：

个人认为第二种方法更简单，而且还可以直接调用很多JAVA已经定义好的函数！！！
大家记得点赞呀！谢谢！