互質

Question

我想創造我afinne代碼的互質：

static void Main(string[] args) 
     { 
      string input = ""; 
      string openMessage = ""; 
      openMessage = openMessage.ToUpper(); 
      string cryptedMessage = ""; 
      int a; 
      int b; 
      int m; 

      Console.WriteLine("Enter the modular size of the alphabet:"); 
      input = Console.ReadLine(); 
      m = int.Parse(input); 

      Console.WriteLine("Enter first value for encrypting the message:"); 
      input = Console.ReadLine(); 
      a = int.Parse(input); 
      while(a!=0 && m !=0) 
      { 
       if (a > m) 
       { 
        a %= m; 
       } else 
       { 
        m %= a; 
       } 

      } 
      Console.WriteLine("Enter second value for encrypting the message:"); 
      input = Console.ReadLine(); 
      b = int.Parse(input); 

      Console.WriteLine("Enter the message you want to encrypt:"); 
      input = Console.ReadLine(); 
      openMessage = input.ToUpper(); 

      foreach (char letter in openMessage) 
      { 
       int letterNumber = (int)letter; 
       letterNumber = (a * (letterNumber - 65) + b) % m; //Afinne Cipher math 
       letterNumber = letterNumber + 65; 
       char encryptedLetter = (char)letterNumber; 
       cryptedMessage = cryptedMessage + encryptedLetter; 
      } 
      Console.WriteLine(cryptedMessage); 

     } 

有沒有人有一個建議，如何做到這一點？

我想比較int m和int a。我擡頭看谷歌，發現this，但看起來很難實現我的代碼。

Answer 1

用於確定兩個非負整數的greatest common divisor的euclidean algorithm可以在C＃中實現，如下所示。

public int Gcd(int m, int n) 
{ 
    var tmp = 0; 
    if (m < n) 
    { 
     tmp = m; 
     m = n; 
     n = tmp; 
    } 
    while (n != 0) 
    { 
     tmp = m % n; 
     m = n; 
     n = tmp; 
    } 
    return m; 
} 

基於此實施方式中，一小部分m/n可以用下面的函數降低。

public void Reduce(ref int m, ref int n) 
{ 
    var Gcd = Gcd(m, n); 
    m /= Gcd; 
    n /= Gcd; 
}