ALGORITMO DE LA RAÍZ CUADRADA MODULAR CUANDO N ES NUMERO COMPUESTO EN JAVA

En una publicación anterior pudimos observar tanto el algoritmo que se usa para obtener la raíz cuadrada si es que la hubiera así como la implementación , claro esta esto fue cuando N era numero Primo , en esta oportunidad lo haremos cuando N es numero Compuesto, cabe recalcar que para mayor comodidad de mi parte habrá partes en la implementación que solo mencionare las funciones usadas ya que como indique en la publicación anterior , la raíz cuadrada abarca muchas operaciones extra que ya hemos implementado anteriormente por lo que les dejare el link correspondiente a estas cuando se les haga mención, bueno comencemos.

Algoritmo

Básicamente el algoritmo para números compuestos consiste en factorizar a N en dos factores primos distintos e impares(p y q, donde p>q) y aplicarle el algoritmo de raíz cuadrada cuando N es primo por separado en la cual obtendremos las raíces (r,-r) y (s,-s) para luego continuar con lo que resta del algoritmo.

Ver Publicación acerca de Raiz cuadrada cuando N es primo.

Implementación:
Clase Factorización:

public class Factorizacion {
    public ArrayList< integer > factorizar(int numero)
    {
        ArrayList< integer > factores = new ArrayList<>();
        int i=3;
        while(numero!=1)
        {
            while(numero%2==0)
            {
                factores.add(2);
                numero=numero/2;
            }
            while(numero%i==0)
            {
                factores.add(i);
                numero=numero/i;
            }
            i++;
        }
        return factores;
    }
}

Clase Raíz Cuadrada Compuesta:

public class RaizCompuesta {
    int p,q,a,c,d,x,y,r,s,n;
    int raicesF[]=new int[4];
    ArrayList< Integer > factores = new ArrayList<  >();
    int raizP1[]=new int[2],raizP2[]=new int[2];
    Factorizacion obj= new Factorizacion();
    boolean aux1,aux2;//Sirven para validar la existencia de las raices
    public int[] CalcularRaizCompuesta(int p1,int a1)
    {
        factores=obj.factorizar(p1);
        p=factores.get(1);
        q=factores.get(0);
        a=a1;
        n=p*q;
        System.out.println("p: "+p);
        System.out.println("q: "+q);
        //System.out.println("p: "+p);
        //System.out.println("q: "+q);
        Raiz objRaiz1 = new Raiz();
        Raiz objRaiz2 = new Raiz();
        aux1=objRaiz1.CalcularRaiz(p,a);
        aux2=objRaiz2.CalcularRaiz(q,a);
        if(aux1==false||aux2==false)
        {
            return null;
        }
        else
        {
            raizP1=objRaiz1.getRaiz();
            raizP2=objRaiz2.getRaiz();
            Euclides objEuclides= new Euclides();
            long mcd[]=new long[3];
            mcd= objEuclides.euclidesExtendido((long)p, (long)q);
            c=(int) mcd[1];
            d=(int) mcd[2];
            //System.out.println("c:"+c);
            //System.out.println("d:"+d);
            r=raizP1[0];
            s=raizP2[0];
            //System.out.println("r: "+r);
            //System.out.println("s: "+s);
            x=(r*d*q+s*c*p)%(n);
            y=(r*d*q-s*c*p)%(n);
            //System.out.println("X: "+x);
            //System.out.println("Y: "+y);
            raicesF[0]=x%n;
            raicesF[1]=-1*raicesF[0];
            raicesF[2]=y%n;
            raicesF[3]=-1*raicesF[2];
            for(int i=0;i< 4;i++)
            {
                if(raicesF[i]< 0)
                {
                    raicesF[i]=raicesF[i]+n;
                }
            }
            return raicesF;
        }    
    }
    
}

Fragmento del código de la Interfaz Principal:

public class Factorizacion {
        RaizCompuesta obj= new RaizCompuesta();
        int raices[]=new int[4];
        raices=obj.CalcularRaizCompuesta(Integer.parseInt(numero_p.getText()),Integer.parseInt(numero_a.getText()));
        if(raices==null)
        {
            JOptionPane.showMessageDialog(null, "NO EXISTEN RAICES");
        }
        else
        {
            raiz_1.setText(""+raices[0]);
            raiz_2.setText(""+raices[1]);
            raiz_3.setText(""+raices[2]);
            raiz_4.setText(""+raices[3]);
        }

Espero les sea de utilidad y hasta la siguiente Publicación.