Násobné poradie
V teórii čísel je dané celé číslo A a kladné celé číslo N s gcd(AN) = 1, multiplikatívne poradie modulu N je najmenšie kladné celé číslo k s A^k(mod N) = 1. ( 0 < K < N )
Príklady:
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
Ak sa pozrieme bližšie, zistíme, že nemusíme zakaždým počítať výkon. môžeme získať ďalší výkon vynásobením „A“ predchádzajúcim výsledkom modulu.
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
Spustite slučku od 1 do N-1 a vráťte najmenší kladný výkon A pod modulo n, ktorý sa rovná 1.
Nižšie je uvedená implementácia vyššie uvedenej myšlienky.
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>
výstup:
3
Časová zložitosť: O(N)
Priestorová zložitosť: O(1)
Referencia: https://en.wikipedia.org/wiki/Multiplicative_order
