BigPrimeFactor: Factors BigInteger Numbers
M. Gallant 10/09/2000
The ability to create objects from classes in the Java API
can be used to extend the capability of Windows scripts.
Since the MS Java API is resident on any PC with IE4+ installed,
developers can leverage the capability contained therein.
The following script instantiates a Java object which contains
a method BigPrimeFactor.getPrimeFactors(String somenumber)
to return the factorization of any large number. The method also
returns the BigInteger.isProbablePrime(40) value which indicates
the probabability of prime estimate (1-1/2^40) (false if composite).
To use the Java class, compile the Java source code, and place the
resultant BigPrimeFactor.class
class file in the classpath (for example: C:\Windows\Java\Classes)
BigPrime.vbs
'****************************************************************
' File: BigPrime.vbs (WSH for VBscript)
' Author: (c) M. Gallant 10/09/2000
'
' Calculates prime factors of any big integer
' Uses Java class "BigPrimeFactor" which must be in classpath.
'****************************************************************
Option Explicit
Const ptext = "Enter a number > 1 to factor:"
Const ttext = "Big Integer Factorization -- M. Gallant"
Dim WshShell, oJPrimes
DIM number, primeinfo, again
set WshShell = WScript.CreateObject("WScript.Shell")
set oJPrimes = GetObject("java:BigPrimeFactor") 'Instantiate Java object via moniker.
Do While True
number = InputBox(ptext, ttext)
primeinfo = oJPrimes.getPrimeFactors(number)
again = WshShell.Popup(primeinfo & vbCrLf & vbCrLf & "Continue?",0, _
ttext, vbInformation + vbYesNo)
If again = vbNo Then Exit Do
Loop
'----------------- End Script -------------------------------
BigPrimeFactor.java (Java class)
/* bigfactor implements prime factoring for arbitrary-precision
numbers using Java 1.1+ BigInteger class
M. Gallant 10/09/2000 */
import java.util.*;
import java.math.BigInteger;
public class BigPrimeFactor {
static final BigInteger zero = new BigInteger("0") ;
static final BigInteger one = new BigInteger("1") ;
static final BigInteger two = new BigInteger("2") ;
static final BigInteger three = new BigInteger("3") ;
public static void main(String args[]) {
BigPrimeFactor bpf = new BigPrimeFactor() ;
for (int i = 0; i < args.length; i++)
System.out.println(bpf.getPrimeFactors(args[i])+"\r\n") ;
}
public String getPrimeFactors(String stringnumber) {
StringBuffer strbuf = new StringBuffer() ;
try {
BigInteger number = new BigInteger(stringnumber);
if (number.compareTo(zero) <= 0)
return("***** Select a number >1 *****");
strbuf.append("isProbablePrime (10^12:1) " + number.isProbablePrime(40)+"\r\n\r\n");
strbuf.append(number + " = ");
Vector factors = getFactors(number);
for (int j = 0; j < factors.size(); j++) {
if (j != 0)
strbuf.append(" * ");
strbuf.append("" + (BigInteger) factors.elementAt(j));
}
strbuf.append("\r\n");
strbuf.append(verifyFactors(number, factors)) ;
}
catch (NumberFormatException e) {
strbuf.append("***** Not a number! *****") ;
}
return strbuf.toString() ;
}
private Vector getFactors(BigInteger number) { // number should be positive
Vector factors = new Vector();
while (number.mod(two).compareTo(zero) == 0) {
// System.out.println("New factor: " + two) ;
number=number.divide(two);
factors.addElement(two);
}
BigInteger limit = bigRoot(number).add(one);
// System.out.println("Initial search limit: " + limit) ;
factor:
for (BigInteger i = three; i.compareTo(limit) <= 0; i=i.add(two)) {
while (number.mod(i).compareTo(zero) == 0) {
// System.out.println("New factor: " + i) ;
number=number.divide(i) ;
factors.addElement(i);
if (number.compareTo(one) == 0)
break factor;
limit = bigRoot(number).add(one);
}
}
if (number.compareTo(one) != 0 || factors.size() == 0)
factors.addElement(number);
return factors;
}
private BigInteger bigRoot(BigInteger number) {
BigInteger result = zero ;
BigInteger oldRoot ;
BigInteger newRoot ;
BigInteger zero=new BigInteger("0") ;
BigInteger two =new BigInteger("2") ;
BigInteger num = number ;
newRoot = num.shiftRight(num.bitLength()/2) ;
do {
oldRoot = newRoot ;
newRoot = oldRoot.multiply(oldRoot).add(num).divide(oldRoot).divide(two) ;
} while(newRoot.subtract(oldRoot).abs().compareTo(two)>0) ;
return newRoot;
}
private String verifyFactors(BigInteger number, Vector factors) {
String status = "" ;
BigInteger check = one; //initialize check product of factors.
for(int k = 0; k < factors.size() ; k++)
check = check.multiply((BigInteger) factors.elementAt(k)) ;
if(check.compareTo(number) ==0)
status = "Factor Verification OK ---------" ;
else
status = "!!!!! Problem with verifying product of factors !!!!!";
return status ;
}
}