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

Опубликовано: 20 Января, 2022

В теории чисел, учитывая целое число A и положительное целое число N с НОД (A, N) = 1, мультипликативный порядок по модулю N - это наименьшее положительное целое число k с A ^ k (mod N) = 1. (0 < К <N)
Примеры :

 Ввод: A = 4, N = 7 
Выход: 3
объяснение: НОД (4, 7) = 1  
              A ^ k (mod N) = 1 (наименьшее положительное целое число K)
               4 ^ 1 = 4 (мод 7) = 4
               4 ^ 2 = 16 (мод 7) = 2
               4 ^ 3 = 64 (мод 7) = 1
               4 ^ 4 = 256 (мод 7) = 4
               4 ^ 5 = 1024 (мод 7) = 2
               4 ^ 6 = 4096 (мод 7) = 1

наименьшее натуральное число K = 3  

Ввод: A = 3, N = 1000. 
Вывод: 100 (3 ^ 100 (mod 1000) == 1) 

Ввод: A = 4, N = 11 
Выход: 5

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Если мы внимательно рассмотрим, то увидим, что нам не нужно каждый раз рассчитывать мощность. мы можем получить следующую степень, умножив «А» на предыдущий результат модуля.

 Объяснение : 
А = 4, N = 11  
исходный результат = 1 
с нормальным с модульной арифметикой (результат A *)
4 ^ 1 = 4 (мод. 11) = 4 || 4 * 1 = 4 (мод. 11) = 4 [результат = 4]
4 ^ 2 = 16 (мод 11) = 5 || 4 * 4 = 16 (мод. 11) = 5 [результат = 5]
4 ^ 3 = 64 (мод. 11) = 9 || 4 * 5 = 20 (мод. 11) = 9 [результат = 9]
4 ^ 4 = 256 (мод. 11) = 3 || 4 * 9 = 36 (мод. 11) = 3 [результат = 3]
4 ^ 5 = 1024 (мод. 5) = 1 || 4 * 3 = 12 (мод. 11) = 1 [результат = 1]

наименьшее натуральное число 5

Run a loop from 1 to N-1 and Return the smallest +ve power of A under modulo n which is equal to 1. 
Below is the implementation of above idea. 
 

CPP

// C++ program to implement multiplicative order
#include<bits/stdc++.h>
using namespace std;
 
// function for GCD
int GCD ( int a , int b )
{
    if (b == 0 )
        return a;
    return GCD( b , a%b ) ;
}
 
// Fucnction 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 rised to
    // the power N-1
    unsigned int result = 1;
 
    int K = 1 ;
    while (K < N)
    {
        // modular arithmetic
        result = (result * A) % N ;
 
        // return samllest +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 rised to
        // the power N-1
        int result = 1;
     
        int K = 1;
         
        while (K < N) {
             
            // modular arithmetic
            result = (result * A) % N;
         
            // return samllest +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
 
# funnction for GCD
def GCD (a, b ) :
    if (b == 0 ) :
        return a
    return GCD( b, a % b )
 
# Fucnction 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 rised
    # to the power N-1
    result = 1
 
    K = 1
    while (K < N) :
     
        # modular arithmetic
        result = (result * A) % N
 
        # return samllest + 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
        // rised to the power N-1
        int result = 1;
     
        int K = 1;
         
        while (K < N)
        {
             
            // modular arithmetic
            result = (result * A) % N;
         
            // return samllest +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
// PHP program to implement
// multiplicative order
 
// function for GCD
function GCD ( $a , $b )
{
    if ($b == 0 )
        return $a;
    return GCD( $b , $a % $b ) ;
}
 
// Fucnction 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 rised to the power N-1
    $result = 1;
 
    $K = 1 ;
    while ($K < $N)
    {
        // modular arithmetic
        $result = ($result * $A) % $N ;
 
        // return samllest +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 rised to
        // the power N-1
        let result = 1;
       
        let K = 1;
           
        while (K < N) {
               
            // modular arithmetic
            result = (result * A) % N;
           
            // return samllest +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>

Выход :

 3

Сложность времени: O (N)
Ссылка: https://en.wikipedia.org/wiki/Multiplicative_order
Эта статья предоставлена Нишантом Сингхом. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

РЕКОМЕНДУЕМЫЕ СТАТЬИ