orden multiplicativo

Posted on by Rudeus Greyrat

En teoría de números, dado un entero A y un entero positivo N con mcd( A , N) = 1, el orden multiplicativo de un módulo N es el entero positivo más pequeño k con A^k( mod N ) = 1. ( 0 < K < norte ) 

Ejemplos: 

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

Si observamos de cerca, observamos que no necesitamos calcular la potencia cada vez. podemos estar obteniendo la próxima potencia multiplicando ‘A’ con el resultado anterior de un módulo. 

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

Ejecute un ciclo de 1 a N-1 y devuelva la potencia +ve más pequeña de A bajo el módulo n que es igual a 1. 

A continuación se muestra la implementación de la idea anterior.  

C++

// 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 ) ;
}
 
// 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
// 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>

Producción : 

3

Complejidad de tiempo: O(N) 

Referencia: https://en.wikipedia.org/wiki/Multiplicative_order 

Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *