Lema de Hensel – Barcelona Geeks

El lema de Hensel es un resultado que estipula las condiciones para que las raíces de los polinomios módulo potencias de números primos sean «elevadas» a raíces módulo potencias superiores. El método de elevación descrito en la prueba recuerda al método de Newton para resolver ecuaciones. Digamos que las ecuaciones del siguiente tipo deben ser resueltas:

$(x^3 - a) mod \; p^k = 0$

La idea es usar el Lema de Hensel para resolver este tipo de congruencia. También se conoce como el lema de «levantamiento» de Hensel, que es el resultado de la aritmética modular . Si f es una función polinomial y p es un número primo , entonces si f(a ₁ ) = 0 (mod p) y [f'(a ₁ )] mod p != 0 , entonces es posible “levantar” esta solución a la solución para f(x) = 0 (mod p ^k ) usando la siguiente recursión . Note que [f'(a ₁ )] ^-1 se refiere al inverso modular def ‘(a ₁ ) módulo p .

$a_k + 1 = a_k - f(a_k) * [f'(a_1)]^{-1} (mod \; p^{k+1})$

Ejemplo 1:

$x^3 - 3 = 0 (mod \; 25)$

Primero, resuelve (x = 2 es la solución para mod 5)

=> $x^3 - 3 \equiv 0 (mod \; 5)$
=> $X = 2 f'(2) \neq 0 (mod \; 5)$
=> $a_2 = 2 - f(2)[f'(2)]^{-1} mod \; 25$
=> $a_2 = 2 - 5 * 3 \; mod \; 25$
=> $a_2 = -13 \; mod \; 25$
=> $a_2 = 12 \; mod \; 25$

Ejemplo 2:

$(x^3 - 3) \equiv (0 \; mod \; 49)$

Esto no tiene solución ya que (x ³ – 3) % mod 7 = 0 no tiene solución

A continuación se muestra la implementación del lema de Hensel :

C++

// C++ program to illustrate the
// Hensel's Lemma
#include <bits/stdc++.h>
using namespace std;
 
// Consider f(x) = x ^ 3 - k,
// where k is a constant
 
// Function to find the modular
// inverse of a modulo m
int inv(int a, int m)
{
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;
    if (m == 1)
        return 0;
 
    // Apply the Euclidean algorithm,
    // to find the modular inverse
    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0)
        x1 += m0;
    return x1;
}
 
// Function to find the derivative of
// f(x) and f'(x) = 3 * (x ^ 2)
int derivative(int x)
{
    return 3 * x * x;
}
 
// Function to find the image of
// x in f(x) = x ^ 3 - k.
int Image(int x, int k)
{
    return x * x * x - k;
}
 
// Function to find the next power
// of the number
int next_power(int a_t, int t, int a1,
               int prime, int k)
{
    // Next power of prime for which
    // solution is to be found
    int power_p = (int)pow(prime, t + 1);
 
    // Using Hensel's recursion to
    // find the solution (next_a) for
    // next power of prime
    int next_a = (a_t
                  - Image(a_t, k)
                        * inv(derivative(a1),
                              prime))
                 % power_p;
 
    // If next_a < 0 return equivalent
    // positive remainder modulo p
    if (next_a < 0)
        return next_a += power_p;
 
    // Return the next power of a
    return next_a;
}
 
// Function to find the solution of
// the required exponent of prime
int powerOfPrime(int prime, int power,
                 int k, int a1)
{
    // The lemma does not work for
    // derivative of f(x) at a1
    if (derivative(a1) != 0) {
        int a_t = a1;
 
        // Looping from 1 to power
        // of prime whose solution
        // is to be found
        for (int p = 1; p < power; p++) {
            a_t = next_power(a_t, p,
                             a1, prime, k);
        }
 
        // Final answer after evaluating
        // all the exponents up till
        // the required exponent
        return a_t;
    }
 
    return -1;
}
 
// Driver Code
int main()
{
    int prime = 7, a1 = 3;
    int power = 2, k = 3;
 
    // Function Call
    cout << powerOfPrime(prime, power,
                         k, a1);
 
    return 0;
}

Java

// Java program to illustrate the
// Hensel's Lemma
import java.util.*;
 
class GFG{
 
// Consider f(x) = x ^ 3 - k,
// where k is a constant
 
// Function to find the modular
// inverse of a modulo m
static int inv(int a, int m)
{
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;
     
    if (m == 1)
        return 0;
 
    // Apply the Euclidean algorithm,
    // to find the modular inverse
    while (a > 1)
    {
        q = a / m;
        t = m;
        m = a % m;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0)
        x1 += m0;
         
    return x1;
}
 
// Function to find the derivative of
// f(x) and f'(x) = 3 * (x ^ 2)
static int derivative(int x)
{
    return 3 * x * x;
}
 
// Function to find the image of
// x in f(x) = x ^ 3 - k.
static int Image(int x, int k)
{
    return x * x * x - k;
}
 
// Function to find the next power
// of the number
static int next_power(int a_t, int t, int a1,
                      int prime, int k)
{
     
    // Next power of prime for which
    // solution is to be found
    int power_p = (int)Math.pow(prime, t + 1);
 
    // Using Hensel's recursion to
    // find the solution (next_a) for
    // next power of prime
    int next_a = (a_t - Image(a_t, k) *
                  inv(derivative(a1), prime)) %
                  power_p;
 
    // If next_a < 0 return equivalent
    // positive remainder modulo p
    if (next_a < 0)
        return next_a += power_p;
 
    // Return the next power of a
    return next_a;
}
 
// Function to find the solution of
// the required exponent of prime
static int powerOfPrime(int prime, int power,
                        int k, int a1)
{
     
    // The lemma does not work for
    // derivative of f(x) at a1
    if (derivative(a1) != 0)
    {
        int a_t = a1;
 
        // Looping from 1 to power
        // of prime whose solution
        // is to be found
        for(int p = 1; p < power; p++)
        {
            a_t = next_power(a_t, p,
                             a1, prime, k);
        }
 
        // Final answer after evaluating
        // all the exponents up till
        // the required exponent
        return a_t;
    }
    return -1;
}
 
// Driver Code
public static void main(String []args)
{
    int prime = 7, a1 = 3;
    int power = 2, k = 3;
     
    // Function Call
    System.out.print(powerOfPrime(prime, power,
                                  k, a1));
}
}
 
// This code is contributed by rutvik_56

Python3

# Python3 program to illustrate the
# Hensel's Lemma
 
# Consider f(x) = x ^ 3 - k,
# where k is a constant
 
# Function to find the modular
# inverse of a modulo m
def inv(a, m):
     
    m0 = m
    x0 = 0
    x1 = 1
     
    if (m == 1):
        return 0
 
    # Apply the Euclidean algorithm,
    # to find the modular inverse
    while (a > 1):
        q = a // m
        t = m
        m = a % m
        a = t
        t = x0
        x0 = x1 - q * x0
        x1 = t
         
    if (x1 < 0):
        x1 += m0
         
    return x1
 
# Function to find the derivative of
# f(x) and f'(x) = 3 * (x ^ 2)
def derivative(x):
     
    return 3 * x * x
 
# Function to find the image of
# x in f(x) = x ^ 3 - k.
def Image(x, k):
     
    return x * x * x - k
 
# Function to find the next power
# of the number
def next_power(a_t, t, a1, prime, k):
     
    # Next power of prime for which
    # solution is to be found
    power_p = int(pow(prime, t + 1))
 
    # Using Hensel's recursion to
    # find the solution(next_a) for
    # next power of prime
    next_a = (a_t - Image(a_t, k) *
              inv(derivative(a1), prime)) % power_p
 
    # If next_a < 0 return equivalent
    # positive remainder modulo p
    if (next_a < 0):
        next_a += power_p
        return next_a
 
    # Return the next power of a
    return next_a
 
# Function to find the solution of
# the required exponent of prime
def powerOfPrime(prime, power, k, a1):
     
    # The lemma does not work for
    # derivative of f(x) at a1
    if (derivative(a1) != 0):
        a_t = a1
         
        # Looping from 1 to power
        # of prime whose solution
        # is to be found
        for p in range(1, power):
            a_t = next_power(a_t, p, a1, prime, k)
 
        # Final answer after evaluating
        # all the exponents up till
        # the required exponent
        return a_t
 
    return -1
 
# Driver Code
prime = 7
a1 = 3
power = 2
k = 3
 
# Function Call
print(powerOfPrime(prime, power, k, a1))
 
# This code is contributed by amreshkumar3

C#

// C# program to illustrate the
// Hensel's Lemma
using System;
class GFG
{
 
// Consider f(x) = x ^ 3 - k,
// where k is a constant
 
// Function to find the modular
// inverse of a modulo m
static int inv(int a, int m)
{
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;  
    if (m == 1)
        return 0;
 
    // Apply the Euclidean algorithm,
    // to find the modular inverse
    while (a > 1)
    {
        q = a / m;
        t = m;
        m = a % m;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0)
        x1 += m0;      
    return x1;
}
 
// Function to find the derivative of
// f(x) and f'(x) = 3 * (x ^ 2)
static int derivative(int x)
{
    return 3 * x * x;
}
 
// Function to find the image of
// x in f(x) = x ^ 3 - k.
static int Image(int x, int k)
{
    return x * x * x - k;
}
 
// Function to find the next power
// of the number
static int next_power(int a_t, int t, int a1,
                      int prime, int k)
{
     
    // Next power of prime for which
    // solution is to be found
    int power_p = (int)Math.Pow(prime, t + 1);
 
    // Using Hensel's recursion to
    // find the solution (next_a) for
    // next power of prime
    int next_a = (a_t - Image(a_t, k) *
                  inv(derivative(a1), prime)) %
                  power_p;
 
    // If next_a < 0 return equivalent
    // positive remainder modulo p
    if (next_a < 0)
        return next_a += power_p;
 
    // Return the next power of a
    return next_a;
}
 
// Function to find the solution of
// the required exponent of prime
static int powerOfPrime(int prime, int power,
                        int k, int a1)
{
     
    // The lemma does not work for
    // derivative of f(x) at a1
    if (derivative(a1) != 0)
    {
        int a_t = a1;
 
        // Looping from 1 to power
        // of prime whose solution
        // is to be found
        for(int p = 1; p < power; p++)
        {
            a_t = next_power(a_t, p,
                             a1, prime, k);
        }
 
        // Final answer after evaluating
        // all the exponents up till
        // the required exponent
        return a_t;
    }
    return -1;
}
 
// Driver Code
public static void Main(string []args)
{
    int prime = 7, a1 = 3;
    int power = 2, k = 3;
     
    // Function Call
    Console.Write(powerOfPrime(prime, power,
                                  k, a1));
}
}
 
// This code is contributed by pratham76.

Javascript

<script>
// Javascript program to illustrate the
// Hensel's Lemma
 
// Consider f(x) = x ^ 3 - k,
// where k is a constant
  
// Function to find the modular
// inverse of a modulo m
function inv(a, m)
{
    let m0 = m, t, q;
    let x0 = 0, x1 = 1;
      
    if (m == 1)
        return 0;
  
    // Apply the Euclidean algorithm,
    // to find the modular inverse
    while (a > 1)
    {
        q = Math.floor(a / m);
        t = m;
        m = a % m;
        a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    if (x1 < 0)
        x1 += m0;
          
    return x1;
}
  
// Function to find the derivative of
// f(x) and f'(x) = 3 * (x ^ 2)
function derivative(x)
{
    return 3 * x * x;
}
  
// Function to find the image of
// x in f(x) = x ^ 3 - k.
function Image(x, k)
{
    return x * x * x - k;
}
  
// Function to find the next power
// of the number
function next_power(a_t, t, a1, prime, k)
{
      
    // Next power of prime for which
    // solution is to be found
    let power_p = Math.floor(Math.pow(prime, t + 1));
  
    // Using Hensel's recursion to
    // find the solution (next_a) for
    // next power of prime
    let next_a = (a_t - Image(a_t, k) *
                  inv(derivative(a1), prime)) %
                  power_p;
  
    // If next_a < 0 return equivalent
    // positive remainder modulo p
    if (next_a < 0)
        return next_a += power_p;
  
    // Return the next power of a
    return next_a;
}
  
// Function to find the solution of
// the required exponent of prime
function powerOfPrime(prime, power,
                        k, a1)
{
      
    // The lemma does not work for
    // derivative of f(x) at a1
    if (derivative(a1) != 0)
    {
        let a_t = a1;
  
        // Looping from 1 to power
        // of prime whose solution
        // is to be found
        for(let p = 1; p < power; p++)
        {
            a_t = next_power(a_t, p,
                             a1, prime, k);
        }
  
        // Final answer after evaluating
        // all the exponents up till
        // the required exponent
        return a_t;
    }
    return -1;
}
 
  // Driver Code
     
    let prime = 7, a1 = 3;
    let power = 2, k = 3;
      
    // Function Call
    document.write(powerOfPrime(prime, power,
                                  k, a1));
                                   
// This code is contributed by target_2.             
</script>

Producción:

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta