📄 factorizer.java
字号:
package javax.math.factorization;
/**
* <p>Title: Factorization Library</p>
* <p>Description: </p>
* <p>Copyright: Copyright (c) 2004</p>
* <p>Company: </p>
* @author Vladimir Silva
* @version 1.0
*/
import java.math.BigInteger;
import java.io.OutputStream;
import java.io.IOException;
import java.io.FileOutputStream;
/**
* Sorry about all this awful spagethi code :-<
* I got it from: Dario Alejandro Alpern (Buenos Aires - Argentina)
* Last updated October 16th, 2003. See http://www.alpertron.com.ar/ECM.HTM
* I am not to blame for its crappy design and implementation, but....
* what the hell. it works!
* I modified it though, to make it less horrible (extracted the pieces i needed)
* If you are a brave soul, try to port this stuff to an object oriented, well-designed
* structure. I tried, but just gave up....
*/
public class Factorizer
{
static final String USAGE = "Factorizer -n BIG_NUMBER -out [OUT-FILE] -verbose";
static final int MAX_DIVISORS = 4000;
/**
* Factors of a num N are dined by: N = pd(i)^exp(i) * pd(i+1)^exp(i) * .....
* where pd = prime divisor
*/
final BigInteger _primeDivisors[] = new BigInteger[MAX_DIVISORS];
final int _exponents[] = new int[MAX_DIVISORS];
// the type of divisor: 0 == prime, 1 == composite (has other factors), -1 unknown
static final int _types[] = new int[MAX_DIVISORS];
// # to be factored
BigInteger _numToFactor;
// # of factors of the form: pd(i)^exp, where pd = prime divisors
static int NbrFactors = 0;
// Why this? Don't know...
static double dN;
static long TestNbr[] = new long[Constants.MP_INITIAL_SIZE];
static int NumberLength;
static long yieldFreq;
// time count?
static long OldTimeElapsed;
static long Old;
// used to dump output to stdout
static boolean VERBOSE = false;
// save factors to a file or dump to stdout
private boolean SAVE_2_FILE = false;
private String FILE_NAME = "";
/*
* Computes N^Exp mod prime
*/
long modPow(long NbrMod, long Expon, long currentPrime) {
long Power = 1;
long Square = NbrMod;
while (Expon != 0) {
if ( (Expon & 1) == 1) {
Power = (Power * Square) % currentPrime;
}
Square = (Square * Square) % currentPrime;
Expon /= 2;
}
return Power;
}
/*
*
*/
void InsertNewFactor(BigInteger InputFactor) {
int g;
/* Insert input factor */
for (g = NbrFactors - 1; g >= 0; g--) {
_primeDivisors[NbrFactors] = _primeDivisors[g].gcd(InputFactor);
if (_primeDivisors[NbrFactors].equals(Constants.BigInt1) == false &&
_primeDivisors[NbrFactors].equals(_primeDivisors[g]) == false) {
_exponents[NbrFactors] = _exponents[g];
_primeDivisors[g] = _primeDivisors[g].divide(_primeDivisors[NbrFactors]);
if (_types[g] < 100000000) {
_types[g] = -EllipticCurve.EC;
_types[NbrFactors] = - Constants.TYPE_EC - EllipticCurve.EC;
}
else if (_types[g] < 150000000) {
_types[NbrFactors] = -_types[g];
_types[g] = Constants.TYPE_AURIF - _types[g];
}
else if (_types[g] < 200000000) {
_types[NbrFactors] = -_types[g];
_types[g] = Constants.TYPE_TABLE - _types[g];
}
else {
_types[NbrFactors] = -_types[g];
_types[g] = Constants.TYPE_SIQS - _types[g];
}
NbrFactors++;
}
}
SortFactorsInputNbr();
}
//
void SortFactorsInputNbr() {
int g, i, j;
BigInteger Nbr1;
for (g = 0; g < NbrFactors - 1; g++) {
for (j = g + 1; j < NbrFactors; j++) {
if (_primeDivisors[g].compareTo(_primeDivisors[j]) > 0) {
Nbr1 = _primeDivisors[g];
_primeDivisors[g] = _primeDivisors[j];
_primeDivisors[j] = Nbr1;
i = _exponents[g];
_exponents[g] = _exponents[j];
_exponents[j] = i;
i = _types[g];
_types[g] = _types[j];
_types[j] = i;
}
}
}
}
/*
*
*/
int PowerCheck(int i) {
BigInteger TestBase, BaseIncrement;
long New;
int maxExpon = (_primeDivisors[i].bitLength() - 1) / 17;
int comp, h, j;
long modulus, modulus2;
int prime2310x1[] = {
2311, 4621, 9241, 11551, 18481, 25411, 32341, 34651, 43891,
50821}; // Primes of the form 2310x+1.
boolean expon2 = true, expon3 = true, expon5 = true;
boolean expon7 = true, expon11 = true;
for (h = 0; h < prime2310x1.length; h++) {
long testprime = prime2310x1[h];
long mod = _primeDivisors[i].mod(BigInteger.valueOf(testprime)).intValue();
if (expon2 && modPow(mod, testprime / 2, testprime) > 1)
expon2 = false;
if (expon3 && modPow(mod, testprime / 3, testprime) > 1)
expon3 = false;
if (expon5 && modPow(mod, testprime / 5, testprime) > 1)
expon5 = false;
if (expon7 && modPow(mod, testprime / 7, testprime) > 1)
expon7 = false;
if (expon11 && modPow(mod, testprime / 11, testprime) > 1)
expon11 = false;
}
boolean ProcessExpon[] = new boolean[maxExpon + 1];
boolean primes[] = new boolean[2 * maxExpon + 3];
for (h = 2; h <= maxExpon; h++) {
ProcessExpon[h] = true;
}
for (h = 2; h < primes.length; h++) {
primes[h] = true;
}
for (h = 2; h * h < primes.length; h++) { // Generation of primes
for (j = h * h; j < primes.length; j += h) { // using Eratosthenes sieve
primes[j] = false;
}
}
for (h = 13; h < primes.length; h++) {
if (primes[h]) {
int processed = 0;
for (j = 2 * h + 1; j < primes.length; j += 2 * h) {
if (primes[j]) {
modulus = _primeDivisors[i].mod(BigInteger.valueOf(j)).
longValue();
if (modPow(modulus, j / h, j) > 1) {
for (j = h; j <= maxExpon; j += h) {
ProcessExpon[j] = false;
}
break;
}
}
if (++processed > 10)
break;
}
}
}
for (int Exponent = maxExpon; Exponent >= 2; Exponent--) {
if (Exponent % 2 == 0 && expon2 == false)
continue; // Not a square
if (Exponent % 3 == 0 && expon3 == false)
continue; // Not a cube
if (Exponent % 5 == 0 && expon5 == false)
continue; // Not a fifth power
if (Exponent % 7 == 0 && expon7 == false)
continue; // Not a 7th power
if (Exponent % 11 == 0 && expon11 == false)
continue; // Not an 11th power
if (ProcessExpon[Exponent] == false)
continue;
New = System.currentTimeMillis();
if (OldTimeElapsed >= 0 &&
OldTimeElapsed / 1000 !=
(OldTimeElapsed + New - Old) / 1000) {
OldTimeElapsed += New - Old;
Old = New;
long t = OldTimeElapsed / 1000;
Util.verbose("Time elapsed: " +
t / 86400 + "d " +
(t % 86400) / 3600 + "h " +
( (t % 3600) / 60) + "m " + (t % 60) +
"s Power exponent: " + Exponent);
}
TestBase = Constants.BigInt0;
BaseIncrement = Constants.BigInt1.shiftLeft(_primeDivisors[i].bitLength() /
Exponent + 1);
while (BaseIncrement.compareTo(Constants.BigInt1) > 0) {
BaseIncrement = BaseIncrement.shiftRight(1);
comp = TestBase.add(BaseIncrement).pow(Exponent).
compareTo(_primeDivisors[i]);
if (comp == 0) {
_primeDivisors[i] = TestBase.add(BaseIncrement);
_exponents[i] *= Exponent;
return 1;
}
if (comp < 0) {
TestBase = TestBase.add(BaseIncrement);
}
}
}
return 0;
}
/*
* Main Factorization routine
*/
public Factorizer(String[] args) throws Exception
{
int j = 0;
BigInteger N, NN, OldPD;
NN = new BigInteger("0");
// parse args
if ( ! parseArgs(args) ) {
throw new Exception("Invalid arguments.\n" + USAGE);
}
EllipticCurve ecManager = new EllipticCurve();
Old = System.currentTimeMillis();
// returns != 1 if Num is composite
long TestComp = SmallFactors.GetSmallFactors(_numToFactor, _primeDivisors, _exponents, _types,0); // facs.getSmallFactors(_numToFactor);
if (TestComp != 1) {
_primeDivisors[NbrFactors] = BigNumOps.BigIntToBigNbr(TestNbr);
_exponents[NbrFactors] = 1;
_types[NbrFactors] = -1; // Unknown
NbrFactors++;
}
factor_loop:
do {
for (int i = 0; i < NbrFactors; i++)
{
// Types[i] == 0 - > Factor is prime, 1 -> Composite, -1 -> Unk
if (_types[i] < 0) { // Unknown
//Util.verbose("Searching for perfect power.");
if (PowerCheck(i) != 0) {
SortFactorsInputNbr();
continue factor_loop;
}
if (_primeDivisors[i].bitLength() <= 33) {
j = 0;
}
else {
//Util.verbose("Before calling prime check routine.");
long oldModularMult = EllipticCurve.lModularMult;
j = PrimeChecker.AprtCle(_primeDivisors[i]);
EllipticCurve.primeModMult += EllipticCurve.lModularMult - oldModularMult;
}
// j == 0 Factor is prime, i -> Composite, -1 -> Unknown
if (j == 0) {
if (_types[i] < - Constants.TYPE_EC) {
_types[i] = -_types[i]; // Prime
}
else if (_types[i] < - Constants.TYPE_SIQS) {
_types[i] = Constants.TYPE_SIQS; // Prime
}
else if (_types[i] < -Constants.TYPE_AURIF) {
_types[i] = Constants.TYPE_AURIF; // Prime
}
else {
_types[i] = 0; // Prime
}
}
else {
if (_types[i] < -Constants.TYPE_EC) {
_types[i] = -Constants.TYPE_EC - _types[i]; // Composite
}
else {
_types[i] = -_types[i]; // Composite
}
}
continue factor_loop;
}
}
for (int i = 0; i < NbrFactors; i++) {
EllipticCurve.EC = _types[i];
if (EllipticCurve.EC > 0 && EllipticCurve.EC < Constants.TYPE_EC &&
EllipticCurve.EC != Constants.TYPE_AURIF && EllipticCurve.EC != Constants.TYPE_SIQS) { // Composite
if (EllipticCurve.EC < Constants.TYPE_SIQS && EllipticCurve.NextEC < Constants.TYPE_SIQS) {
NN = ecManager.fnECM(_primeDivisors[i],i);
if (NN.equals(Constants.BigInt1)) {
NN = QuadraticSieve.FactoringSIQS(_primeDivisors[i]);
}
_types[i] = EllipticCurve.EC;
}
else {
NN = QuadraticSieve.FactoringSIQS(_primeDivisors[i]);
_types[i] = Constants.TYPE_SIQS + 1;
}
InsertNewFactor(NN);
continue factor_loop;
}
}
break;
}
while (true);
// Display computation totals: elapsed time + ECM & QS totals
Util.verbose(totals());
System.gc();
}
/*
* String representation
*/
public String toString() {
return factors() + totals();
}
/*
* Return factorization output of the form: pd(1)^exp(1) * pd(2)^exp(2) * ....
* Where pd = prime divisor, exp = exponent
*/
public String factors() {
StringBuffer b = new StringBuffer();
String exp;
for (int i = 0; i < NbrFactors - 1; i++) {
// disp exps > 1 only
exp = (_exponents[i] > 1) ? "^" + _exponents[i] : "" ;
b.append(_primeDivisors[i] + exp + " * ");
}
exp = (_exponents[NbrFactors - 1] > 1) ? "^" + _exponents[NbrFactors - 1] : "" ;
// append last prime div
b.append(_primeDivisors[NbrFactors - 1] + exp);
return b.toString();
}
/*
* return misc totals: num factors + elapsed time + ECM + QS totals
*/
public String totals() {
String s = "Number of factors=" + NbrFactors + getTimeElapsed() +
QuadraticSieve.getTotals() + EllipticCurve.getEllipticCurveTotals();
return s;
}
/*
* Compute the factorization time
*/
public String getTimeElapsed() {
String totals = null;
long New=System.currentTimeMillis();
if (OldTimeElapsed >= 0) {
OldTimeElapsed += New - Old;
long t = OldTimeElapsed / 1000;
String timeElapsed = t / 86400 + "d " + (t % 86400) / 3600 + "h " + ( (t % 3600) / 60) + "m " + (t % 60) + "s";
totals = "\nFactorization complete in " + timeElapsed;
}
return totals;
}
/**
* Command usage
*/
public void Usage() {
System.out.println(USAGE);
}
/**
* Parse input args
* @param args Command arguments
* @return true of args ok else false.
*/
boolean parseArgs(String[] args) {
for (int i = 0; i < args.length; i++) {
if ( args[i].equals("-n") )
_numToFactor = new BigInteger(args[++i]);
else if ( args[i].equals("-verbose") )
VERBOSE = true;
else if ( args[i].equals("-noverbose") )
VERBOSE = false;
else if ( args[i].equals("-out") ) {
SAVE_2_FILE = true;
FILE_NAME = args[++i];
}
else
return false;
}
return true;
}
/*
* Save factors into into an out stream (file)
*/
public void save(String path) throws Exception {
save(new FileOutputStream(path));
}
public void save(OutputStream os) throws IOException {
os.write(factors().getBytes());
os.close();
}
/*
* Dump out to stdout or a file
*/
public void dumpOutput () throws Exception {
if ( SAVE_2_FILE ) save(FILE_NAME);
else System.out.println(factors());
}
/**
* Main sub
* @param args command arguments
*/
public static void main(String[] args) {
// sample args: -n 11326544366661232376575758854872454522536652252343534523586342467894354935432 -out c:\\temp\\facs.txt
try {
if ( args.length == 0 ) {
System.err.println(USAGE);
return ;
}
Factorizer factorizer = new Factorizer(args);
// dump output: to the console or a file
factorizer.dumpOutput();
}
catch (Exception ex) {
//ex.printStackTrace();
System.err.println(ex);
}
}
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -