Simbolo de Jacobi

El sımbolo de Jacobi es una generalizacion del Simbolo de Legendre y es util para evaluar los sımbolos de Legendre asi como en la definicion de un tipo de numeros llamados pseudoprimos.

CODIGO EN C++

Necesitaremos la siguiente funcion:

son_congruentes(int a,int b,int n)(Funcion que verifica si dos numeros a y b son congruentes modulo n , puedes ver el codigo aqui)

int hallarExponente(int a)
{
  int cont=0;
  while(a%2==0)
  {
    a/=2;
    cont++;
  }
  return cont;
}

int Jacobi(int a,int n)
{
  int e=0,a1=1,n1=0,s=-2;
    
  //si  n es >=3  y 0 <= a < n
  if(n>=3 && 0<=a && a<n)
  {
     if(a==0 || a==1)
         return a;
         
     e=hallarExponente(a);    
     a1=(int)(a/pow(2,e));
     
     if(e%2==0) // si 'e' es par    
       s=1;
     else
     {
        if((son_congruentes(n,1,8))||(son_congruentes(n,7,8)))
           s=1;
        else
          if((son_congruentes(n,3,8))||(son_congruentes(n,5,8)))
            s=-1; 
     }
     
     if((son_congruentes(n,3,4))&&(son_congruentes(a1,3,4)))    
         s=-1*s;
         
     n1=n%a1;
     
     if(a1==1)
       return s;
     else
       return (s*Jacobi(n1,a1));     
  }    
  return -2 ; // retornamos error
}