In de getaltheorie, gegeven een geheel getal A en een positief geheel getal N met ggd( AN) = 1, is de vermenigvuldigingsvolgorde van een modulo N het kleinste positieve gehele getal k met A^k( mod N) = 1. ( 0< K < N )
Voorbeelden:
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
Als we goed kijken, zien we dat we het vermogen niet elke keer hoeven te berekenen. we kunnen de volgende macht verkrijgen door 'A' te vermenigvuldigen met het vorige resultaat van een module.
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
Voer een lus uit van 1 tot N-1 en retourneer de kleinste +ve macht van A onder modulo n, die gelijk is aan 1.
Hieronder ziet u de implementatie van bovenstaand idee.
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>
Uitgang:
3
Tijdcomplexiteit: OP)
Ruimtecomplexiteit: O(1)
Referentie: https://en.wikipedia.org/wiki/Multiplicatieve_order