МУЛЬТИПЛІКАТИВНИЙ ПОРЯДОК

У теорії чисел задано ціле число A та натуральне число N з gcd( A N) = 1, мультиплікативний порядок за модулем N є найменшим натуральним числом k з A^k( mod N ) = 1. ( 0< K < N )

Приклади:

Input : A = 4  N = 7 Output : 3 explanation : GCD(4 7) = 1    A^k( mod N )   = 1 ( smallest positive integer K ) 4^1 = 4(mod 7) = 4 4^2 = 16(mod 7) = 2 4^3 = 64(mod 7) = 1 4^4 = 256(mod 7) = 4 4^5 = 1024(mod 7) = 2 4^6 = 4096(mod 7) = 1 smallest positive integer K = 3 Input : A = 3  N = 1000 Output : 100 (3^100 (mod 1000) == 1) Input : A = 4  N = 11 Output : 5

Якщо ми придивимося уважніше, то побачимо, що нам не потрібно кожен раз обчислювати потужність. ми можемо отримати наступний ступінь, помноживши 'A' на попередній результат модуля.

Explanation : A = 4  N = 11 initially result = 1 with normal with modular arithmetic (A * result) 4^1 = 4 (mod 11 ) = 4 || 4 * 1 = 4 (mod 11 ) = 4 [ result = 4] 4^2 = 16(mod 11 ) = 5 || 4 * 4 = 16(mod 11 ) = 5 [ result = 5] 4^3 = 64(mod 11 ) = 9 || 4 * 5 = 20(mod 11 ) = 9 [ result = 9] 4^4 = 256(mod 11 )= 3 || 4 * 9 = 36(mod 11 ) = 3 [ result = 3] 4^5 = 1024(mod 5 ) = 1 || 4 * 3 = 12(mod 11 ) = 1 [ result = 1] smallest positive integer 5

Запустіть цикл від 1 до N-1 і поверніть найменший +ve ступінь A за модулем n, який дорівнює 1.

Нижче представлена реалізація вищезазначеної ідеї.

C++

// C++ program to implement multiplicative order #include   using namespace std; // function for GCD int GCD ( int a  int b ) {  if (b == 0 )  return a;  return GCD( b  a%b ) ; } // Function return smallest +ve integer that // holds condition A^k(mod N ) = 1 int multiplicativeOrder(int A int N) {  if (GCD(A N ) != 1)  return -1;  // result store power of A that raised to  // the power N-1  unsigned int result = 1;  int K = 1 ;  while (K < N)  {  // modular arithmetic  result = (result * A) % N ;  // return smallest +ve integer  if (result == 1)  return K;  // increment power  K++;  }  return -1 ; } //driver program to test above function int main() {  int A = 4  N = 7;  cout << multiplicativeOrder(A N);  return 0; }

Java

// Java program to implement multiplicative order import java.io.*; class GFG {  // function for GCD  static int GCD(int a int b) {    if (b == 0)  return a;    return GCD(b a % b);  }    // Function return smallest +ve integer that  // holds condition A^k(mod N ) = 1  static int multiplicativeOrder(int A int N) {    if (GCD(A N) != 1)  return -1;    // result store power of A that raised to  // the power N-1  int result = 1;    int K = 1;    while (K < N) {    // modular arithmetic  result = (result * A) % N;    // return smallest +ve integer  if (result == 1)  return K;    // increment power  K++;  }    return -1;  }    // driver program to test above function  public static void main(String args[]) {    int A = 4 N = 7;    System.out.println(multiplicativeOrder(A N));  } } /* This code is contributed by Nikita Tiwari.*/

Python3

# Python 3 program to implement # multiplicative order # function for GCD def GCD (a b ) : if (b == 0 ) : return a return GCD( b a % b ) # Function return smallest + ve # integer that holds condition  # A ^ k(mod N ) = 1 def multiplicativeOrder(A N) : if (GCD(A N ) != 1) : return -1 # result store power of A that raised  # to the power N-1 result = 1 K = 1 while (K < N) : # modular arithmetic result = (result * A) % N # return smallest + ve integer if (result == 1) : return K # increment power K = K + 1 return -1 # Driver program A = 4 N = 7 print(multiplicativeOrder(A N)) # This code is contributed by Nikita Tiwari.

// C# program to implement multiplicative order using System; class GFG {  // function for GCD  static int GCD(int a int b)  {    if (b == 0)  return a;    return GCD(b a % b);  }    // Function return smallest +ve integer   // that holds condition A^k(mod N ) = 1  static int multiplicativeOrder(int A int N)   {    if (GCD(A N) != 1)  return -1;    // result store power of A that   // raised to the power N-1  int result = 1;    int K = 1;    while (K < N)   {    // modular arithmetic  result = (result * A) % N;    // return smallest +ve integer  if (result == 1)  return K;    // increment power  K++;  }    return -1;  }    // Driver Code  public static void Main()   {    int A = 4 N = 7;    Console.Write(multiplicativeOrder(A N));  } } // This code is contributed by Nitin Mittal.

PHP

 // PHP program to implement  // multiplicative order // function for GCD function GCD ( $a  $b ) { if ($b == 0 ) return $a; return GCD( $b  $a % $b ) ; } // Function return smallest // +ve integer that holds  // condition A^k(mod N ) = 1 function multiplicativeOrder($A $N) { if (GCD($A $N ) != 1) return -1; // result store power of A  // that raised to the power N-1 $result = 1; $K = 1 ; while ($K < $N) { // modular arithmetic $result = ($result * $A) % $N ; // return smallest +ve integer if ($result == 1) return $K; // increment power $K++; } return -1 ; } // Driver Code $A = 4; $N = 7; echo(multiplicativeOrder($A $N)); // This code is contributed by Ajit. ?>

JavaScript

<script> // JavaScript program to implement  // multiplicative order  // function for GCD   function GCD(a b) {     if (b == 0)   return a;     return GCD(b a % b);   }     // Function return smallest +ve integer that   // holds condition A^k(mod N ) = 1   function multiplicativeOrder(A N) {     if (GCD(A N) != 1)   return -1;     // result store power of A that raised to   // the power N-1   let result = 1;     let K = 1;     while (K < N) {     // modular arithmetic   result = (result * A) % N;     // return smallest +ve integer   if (result == 1)   return K;     // increment power   K++;   }     return -1;   } // Driver Code  let A = 4 N = 7;     document.write(multiplicativeOrder(A N));     // This code is contributed by chinmoy1997pal. </script>

Вихід:

Часова складність: O(N)

Космічна складність: О(1)

Посилання: https://en.wikipedia.org/wiki/Multiplicative_order

Створіть вікторину

TechCodeview

Мультиплікативний порядок