Multiplikative Ordnung
In der Zahlentheorie ist bei einer gegebenen ganzen Zahl A und einer positiven ganzen Zahl N mit ggT( A N) = 1 die multiplikative Ordnung eines Modulo N die kleinste positive ganze Zahl k mit A^k( mod N ) = 1. ( 0 < K < N )
Beispiele:
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
Wenn wir genau hinsehen, stellen wir fest, dass wir die Leistung nicht jedes Mal neu berechnen müssen. Wir können die nächste Potenz erhalten, indem wir „A“ mit dem vorherigen Ergebnis eines Moduls multiplizieren.
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
Führen Sie eine Schleife von 1 bis N-1 aus und geben Sie die kleinste +ve-Potenz von A unter Modulo n zurück, die gleich 1 ist.
Nachfolgend finden Sie die Umsetzung der obigen Idee.
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# // 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>
Ausgabe :
3
Zeitkomplexität: AN)
Raumkomplexität: O(1)
Referenz: https://en.wikipedia.org/wiki/Multiplicative_order
