Tìm Căn bậc hai dưới Modulo p (thuật toán Shanks Tonelli) trong C ++

Trong bài toán này, chúng ta được cho hai giá trị n và một số nguyên tố p. Nhiệm vụ của chúng ta là tìm Square Root trong Modulo p.

Hãy lấy một ví dụ để hiểu vấn đề,

Input : n = 4, p = 11
Output : 9

Phương pháp tiếp cận giải pháp

Ở đây, chúng tôi sẽ sử dụng Thuật toán Tonelli-Shanks .

Thuật toán Tonelli-Shanks được sử dụng trong số học mô-đun để giải quyết một giá trị x có dạng x2 =n (mod p).

Thuật toán tìm modulo căn bậc hai sử dụng Thuật toán Tonelli của shank -

Bước 1 - Tìm giá trị của $ (n ^ {((p-1) / 2)}) (mod \:p) $, nếu giá trị của nó là p -1 thì căn bậc hai mô-đun không được.

Bước 2 - Sau đó, chúng ta sẽ sử dụng giá trị p-1 as (s * 2 ^e ). Trong đó s là số lẻ và dương và e là số dương.

Bước 3 - Tính giá trị q ^ ((p-1) / 2) (mod p) =-1

Bước 4 - sử dụng vòng lặp cho m lớn hơn 0 và cập nhật giá trị của x,

Tìm m sao cho b ^ (2 ^ m) - 1 (mod p) trong đó 0 <=m <=r-1.

Nếu M bằng 0, hãy trả về x, nếu không, hãy cập nhật các giá trị,

x = x * (g^(2 ^ (r - m - 1))
b = b * (g^(2 ^ (r - m))
g = (g^(2 ^ (r - m - 1))
r = m

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#include <iostream>
#include <math.h>
using namespace std;
int powerMod(int base, int exponent, int modulus) {
   int result = 1;
   base = base % modulus;
   while (exponent > 0) {
      if (exponent % 2 == 1)
      result = (result * base)% modulus;
      exponent = exponent >> 1;
      base = (base * base) % modulus;
   }
   return result;
}
int gcd(int a, int b) {
   if (b == 0)
   return a;
   else
   return gcd(b, a % b);
}
int orderValues(int p, int b) {
   if (gcd(p, b) != 1) {
      return -1;
   }
   int k = 3;
   while (1) {
      if (powerMod(b, k, p) == 1)
      return k;
      k++;
   }
}
int findx2e(int x, int& e) {
   e = 0;
   while (x % 2 == 0) {
      x /= 2;
      e++;
   }
   return x;
}
int calcSquareRoot(int n, int p) {
   if (gcd(n, p) != 1) {
      return -1;
   }
   if (powerMod(n, (p - 1) / 2, p) == (p - 1)) {
      return -1;
   }
   int s, e;
   s = findx2e(p - 1, e);
   int q;
   for (q = 2; ; q++) {
      if (powerMod(q, (p - 1) / 2, p) == (p - 1))
      break;
   }
   int x = powerMod(n, (s + 1) / 2, p);
   int b = powerMod(n, s, p);
   int g = powerMod(q, s, p);
   int r = e;
   while (1) {
      int m;
      for (m = 0; m < r; m++) {
         if (orderValues(p, b) == -1)
         return -1;
         if (orderValues(p, b) == pow(2, m))
         break;
      }
      if (m == 0)
      return x;
      x = (x * powerMod(g, pow(2, r - m - 1), p)) % p;
      g = powerMod(g, pow(2, r - m), p);
      b = (b * g) % p;
      if (b == 1)
      return x;
      r = m;
   }
}
int main() {
   int n = 3;
   int p = 13;
   int sqrtVal = calcSquareRoot(n, p);
   if (sqrtVal == -1)
      cout<<"Modular square root is not exist";
   else
      cout<<"Modular square root of the number is "<<sqrtVal;
}

Đầu ra

Modular square root of the number is 9