IMPLEMENTACIÓN DEL SIMBOLO DE JACOBI EN JAVA

Antes de hablar acerca del símbolo de jacobi es necesario hablar acerca del símbolo de Legendre , ya que esta es una generalización de este.

Símbolo de Legendre:

Sean «p» un número primo e impar, «a» un número entero positivo menor que «p». Entonces el símbolo de Legendre (a/p) se define por:

De acuerdo con la definición anterior podemos notar que es posible tener un conjunto de residuos cuadráticos , denotados por Qp,cuyo valor es 1.

Ejemplo:

Como ya mencione antes Jacobi es una generalización de Legendre.

Jacobi se define como:

Existe un algoritmo de tiempo polinomial que computa el símbolo de Jacobi (a/n) , siempre que “n” es un número impar grande mayor que l y «a» es un numero que va desde cero hasta «n-1».

Algoritmo:
Función Exponencial , necesario para hallar el Símbolo de Jacobi

Func_exp(x)
 cont=0
 Mientras (x mod 2 == 0) hacer
  x=x/2
  cont=cont+1
 Fin mientras
retornar (cont)

Función Jacobi:

IMPLEMENTACIÓN:

Función Exponencial:

public int funcion_exponencial(int a)
    {
        int c=0;
        while(a%2==0)
        {
            a=a/2;
            c++;
        }
        return c;
    }

Función para calcular el símbolo de jacobi:

    public int Opjacobi(int a , int n)
    {
        int a1,e,s = 0,n1;
        if(a==0)
        {
            return 0;
        }
        if(a==1)
        {
            return 1;
        }
        e=funcion_exponencial(a);
        a1=(int) (a/Math.pow(2,e));
        //  Asignando valores
        if(e%2==0)
        {
            s=1;
        }
        else
        {
            if(((n-1)%8==0)||((n-7)%8==0))
            {
                s=1;
            }
            else
            {
                if(((n-3)%8==0)||((n-5)%8==0))
                {
                    s=-1;
                }
            }
        }
        //Cambiando Signo
        if(((n-3)%4==0)&&((a1-3)%4==0))
        {
            s=-1*s;
        }
        n1=n%a1;
        if(a1==1)
        {
            return s;
        }
        else
        {
            return s*Opjacobi(n1,a1);
        }
    }

• Tweet
• Share
• Share
• Share
• Share