前言

正在學習資訊安全數學基礎這門課程，
編程實作模重復平方計演算法，

先介紹一下模重復平方演算法

一、模重復平方演算法

圖片來自大學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;
}

第一道習題，成功，
第二道習題，成功，
下面我們再用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;
 }
}

程式執行結果截圖：

個人認為第二種方法更簡單，而且還可以直接呼叫很多JAVA已經定義好的函式！！！
大家記得點贊呀！謝謝！