I talteori givet et heltal A og et positivt heltal N med gcd( A N) = 1 er multiplikationsrækkefølgen af en modulo N det mindste positive heltal k med A^k( mod N ) = 1. ( 0< K < N )
Eksempler:
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
Hvis vi ser nærmere efter, så observerer vi, at vi ikke behøver at beregne effekt hver gang. vi kan opnå næste potens ved at gange 'A' med det foregående resultat af et modul.
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
Kør en sløjfe fra 1 til N-1 og returner den mindste +ve potens af A under modulo n, som er lig med 1.
Nedenfor er implementeringen af ovenstående idé.
C++// C++ program to implement multiplicative order #include
// 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.*/
# 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 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. ?> <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>
Output:
3
Tidskompleksitet: PÅ)
Rumkompleksitet: O(1)
Reference: https://en.wikipedia.org/wiki/Multiplicative_order