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 ; } }