Applet de factorizacion de enteros gausianos
// <XMP>
// Gaussian Integer factorization applet
//
// Written by Dario Alejandro Alpern (Buenos Aires - Argentina)
// Last updated May 31st, 2002, See http://www.alpertron.com.ar/GAUSIANO.HTM
//
// No part of this code can be used for commercial purposes without
// the written consent from the author. Otherwise it can be used freely
// except that you have to write somewhere in the code this header.
//
import java.applet.*;
import java.util.*;
import java.awt.*;
import java.math.*;
public final class gausiano extends Applet implements Runnable {
private BigInteger Primes[];
private int Exponents[];
private BigInteger Solution1[];
private BigInteger Solution2[];
private BigInteger Increment[];
private BigInteger Aux[];
private BigInteger ValA, ValB;
private StringBuffer info;
private String txt;
private int SolNbr;
private Frame factorWindow;
private ecmc factorPanel;
private volatile Thread calcThread;
private BigInteger LastModulus = BigInteger.valueOf(0);
private int Ind;
private String textError;
void w(String texto) {
info=info.append(texto);
}
void Solution(BigInteger value) {
SolNbr++;
w(SolNbr+") x = "+value.toString()+"<BR>");
}
public void init() {
Primes=new BigInteger[400];
Exponents=new int[400];
Solution1=new BigInteger[400];
Solution2=new BigInteger[400];
Increment=new BigInteger[400];
Aux=new BigInteger[400];
}
/* type = 0: factor expression, type = 1: just compute expression */
public String startCalc(String expr, int type) {
String InputField;
if (calcThread != null) {
// TerminateThread = true;
try {
calcThread.join(); /* Wait until the solving thread dies */
} catch (InterruptedException ie) {};
}
calcThread = new Thread(this); /* Start solving thread */
try {
int ExpressionRC;
BigInteger [] ExpressionResult = new BigInteger[2];
InputField = expr.trim();
if (InputField.equals("")) {
ExpressionRC = -6;
}
try {
ExpressionRC = GaussExpression.ComputeExpression(InputField, ExpressionResult);
} catch (OutOfMemoryError e) {ExpressionRC = -1;}
switch (ExpressionRC) {
case -1:
textError = "No hay suficiente memoria.";
break;
case -2:
textError = "Número muy grande (más de 500 dígitos).";
break;
case -3:
textError = "Expresión intermedia con más de 2000 dígitos.";
break;
case -4:
textError = "División no entera.";
break;
case -5:
textError = "Error de paréntesis.";
break;
case -6:
textError = "Error de sintaxis.";
break;
case -7:
textError = "Demasiados paréntesis.";
break;
case -8:
textError = "Parámetro inválido.";
break;
default:
if (ExpressionResult[0].compareTo(BigInteger.valueOf(10L).pow(500))>=0) {
textError = "Número muy grande (más de 500 dígitos).";
}
else {
textError = "";
}
}
if (textError.length() > 0) {return textError;}
ValA = ExpressionResult[0];
ValB = ExpressionResult[1];
} catch (Exception e) {return "Se entraron datos inválidos";}
if (type == 1) { /* Only computing expression */
info=new StringBuffer();
w("<HTML><HEAD><TITLE>Calculadora de enteros gausianos</TITLE></HEAD><BODY>");
w("<CENTER><H3><FONT COLOR=Red>Calculadora de enteros gausianos</FONT></H3></CENTER>");
w("<P><I>por Dario Alejandro Alpern</I><P><DL><DT>Expresión de entrada:<DD>");
w(InputField);
w("<P><DT>Valor:<DD>");
w(ValA.toString()+(ValB.signum()>=0?" + ":" - ")+ValB.abs().toString()+" i</DL>");
w("<P>Si encontró algún error, por favor envíeme un <A HREF=\"mailto:[email protected]?subject=Factorizacion de enteros de Gauss\">e-mail</A><P>");
w("<A HREF=\"GBOOK.HTM\">Apriete aquí</A> para ver o firmar mi libro de invitados.</BODY></HTML>");
return info.toString();
}
calcThread.start();
return "";
}
public String resultCalc() {
if (calcThread == null) {
return info.toString();
}
return "";
}
public void run() {
String parms1[];
StringBuffer parms2[];
parms1=new String[0];
parms2=new StringBuffer[1];
info=new StringBuffer();
w("<TITLE>Applet de factorizacion de enteros de Gauss</TITLE><CENTER><FONT COLOR=Red><B>");
w("Factores primos de "+ValA.toString()+(ValB.signum()>=0?" + ":" - ")+ValB.abs().toString()+" i</B></FONT></CENTER><P><I>por Dario Alejandro Alpern</I><P>");
Date OldDate=new Date();
long Old=OldDate.getTime();
SolNbr = 0;
GaussianFactorization();
Date NewDate=new Date();
long New=NewDate.getTime();
w("<P>Tiempo de cálculo: ");
int t=(int)(((New-Old)/1000+86400)%86400);
w(t/3600+"h "+((t%3600)/60)+"m "+(t%60)+"s");
w("<P>Si encontró algún error, por favor envíeme un <A HREF=\"mailto:[email protected]?subject=Factorizacion de enteros de Gauss\">e-mail</A><P>");
w("<A HREF=\"GBOOK.HTM\">Apriete aquí</A> para ver o firmar mi libro de invitados.</BODY></HTML>");
calcThread = null;
}
void GaussianFactorization() {
BigInteger BigInt0, BigInt1, BigInt2;
BigInt0 = BigInteger.valueOf(0L);
BigInt1 = BigInteger.valueOf(1L);
BigInt2 = BigInteger.valueOf(2L);
BigInteger K, Mult1, Mult2, p, q, M1, M2, Tmp;
int index, index2;
BigInteger norm = ValA.multiply(ValA).add(ValB.multiply(ValB));
Ind = 0;
if (norm.signum() == 0) {
w("Cualquier primo gausiano divide este número");
return;
}
w("<UL>");
if (norm.compareTo(BigInt1) > 0) {
if (norm.bitLength() < 32) {
long modulus = norm.longValue();
int Exp = 0;
Ind = 0;
while (modulus % 2 == 0) {
Exp++;
modulus /= 2;
}
if (Exp > 0) {
Primes[0] = BigInt2;
Exponents[0] = Exp;
Ind++;
}
long Div = 3;
while (Div*Div <= modulus) {
Exp = 0;
while (modulus % Div == 0) {
Exp++;
modulus /= Div;
}
if (Exp > 0) {
Primes[Ind] = BigInteger.valueOf(Div);
Exponents[Ind] = Exp;
Ind++;
}
Div += 2;
}
if (modulus > 1) {
Primes[Ind] = BigInteger.valueOf(modulus);
Exponents[Ind] = 1;
Ind++;
}
}
else { /* Factor norm > 2^32 */
factorPanel = new ecmc();
factorWindow = new Frame("Factorizacion de la norma");
factorWindow.setResizable(false);
factorWindow.add(factorPanel);
factorPanel.setSize(600, 390);
Insets in = factorWindow.getInsets();
factorWindow.setSize(600+in.right+in.left, 390+in.top+in.bottom);
factorWindow.show();
Ind = factorPanel.getFactors(norm, Primes, Exponents);
factorWindow.remove(factorPanel);
factorWindow.dispose();
}
for (index = 0; index < Ind; index++) {
p = Primes[index];
if (p.equals(BigInt2)) {
for (index2 = 0; index2 < Exponents[index]; index2++) {
DivideGaussian(BigInt1, BigInt1); /* Divide by 1+i */
DivideGaussian(BigInt1, BigInt1.negate()); /* Divide by 1-i */
}
}
if (p.testBit(1) == false) { /* if p = 1 (mod 4) */
q = p.subtract(BigInt1); /* q = p-1 */
K = BigInt1;
do { // Compute Mult1 = sqrt(-1) mod p
K = K.add(BigInt1);
Mult1 = K.modPow(q.shiftRight(2),p);
} while (Mult1.equals(BigInt1) || Mult1.equals(q));
Mult2 = BigInt1;
while (true) {
K = Mult1.multiply(Mult1).add(Mult2.multiply(Mult2)).divide(p);
if (K.equals(BigInt1)) {
break;
}
M1 = Mult1.mod(K);
M2 = Mult2.mod(K);
if (M1.compareTo(K.shiftRight(1)) > 0) {M1 = M1.subtract(K);}
if (M2.compareTo(K.shiftRight(1)) > 0) {M2 = M2.subtract(K);}
Tmp = Mult1.multiply(M1).add(Mult2.multiply(M2)).divide(K);
Mult2 = Mult1.multiply(M2).subtract(Mult2.multiply(M1)).divide(K);
Mult1 = Tmp;
} /* end while */
if (Mult1.abs().compareTo(Mult2.abs()) < 0) {
Tmp = Mult1;
Mult1 = Mult2;
Mult2 = Tmp;
}
for (index2 = 0; index2 < Exponents[index]; index2++) {
DivideGaussian(Mult1,Mult2);
DivideGaussian(Mult1,Mult2.negate());
}
} /* end p = 1 (mod 4) */
else { /* if p = 3 (mod 4) */
for (index2 = 0; index2 < Exponents[index]; index2++) {
DivideGaussian(Primes[index],BigInt0);
} /* end p = 3 (mod 4) */
}
}
}
if (ValA.equals(BigInt1)) {
if (Ind == 0) {
w("Ningún primo gausiano divide este número");
}
}
else if (ValA.add(BigInt1).signum() == 0) {
w("<LI>-1");
}
else if (ValB.equals(BigInt1)) {
w("<LI>i");
}
else {
w("<LI>-i");
}
w("</UL>");
}
private void DivideGaussian(BigInteger real, BigInteger imag) {
real = real.abs();
BigInteger norm = real.multiply(real).add(imag.multiply(imag));
BigInteger realNum = ValA.multiply(real).add(ValB.multiply(imag));
BigInteger imagNum = ValB.multiply(real).subtract(ValA.multiply(imag));
if (realNum.mod(norm).signum() == 0 &&
imagNum.mod(norm).signum() == 0) {
ValA = realNum.divide(norm);
ValB = imagNum.divide(norm);
w("<LI>");
w(real.toString()+(imag.signum()>=0?" + ":" - ")+imag.abs().toString()+" i");
}
}
}
Espero que les sirva el code ;D Saludos