All pastes #258919 Raw Edit

Someone

public text v1 · immutable
#258919 ·published 2006-11-26 22:52 UTC
rendered paste body
import java.math.BigInteger;
import java.math.BigDecimal;

public class RSACracker {
    public static final BigInteger RSA_MODULUS_202 = new BigInteger(
        "7162900525229798032761816791230527296329313291232324"+
        "2902378492635012082079728940539290656365223631636210"+
        "00728841182238772712427862772219676577293600221789"
    );  //Replace with your own key
    public static final BigInteger ZERO = BigInteger.valueOf(0),
                                   ONE = BigInteger.valueOf(1),
                                   TWO = BigInteger.valueOf(2),
                                   FOUR = BigInteger.valueOf(4);
    
    
    public static void main(String[] args) {
        new RSACracker(RSA_MODULUS_202);
    }
    
    
    public FermatFactorizationMethod(final BigInteger i) {
        if(i.mod(TWO).equals(ZERO))
            return;

        BigInteger maxKValue = i.add(ONE).divide(TWO);
        BigInteger kSearch = sqrt(new BigDecimal(i), 25).toBigInteger();
        while(kSearch.pow(2).compareTo(i) < 1 && kSearch.compareTo(maxKValue) == -1)
            kSearch = kSearch.add(ONE);
        
        
        System.out.println("k = "+ kSearch);

        BigInteger iterationDifference;
        for(; kSearch.compareTo(maxKValue) == -1; kSearch = kSearch.add(ONE)) {
            try {
                BigInteger factorBase = sqrt(new BigDecimal(kSearch.pow(2).subtract(i)), 25).toBigIntegerExact();
                
                System.out.println(i +" = ("+ (kSearch.subtract(factorBase)) +")("+ (kSearch.add(factorBase)) +")");
                break;
            } catch(ArithmeticException e) {}
        }
    }
    
    public static final BigDecimal sqrt(final BigDecimal originalValue, int divisionScale) {
        int maxIterations = 50;

        if(originalValue.compareTo(new BigDecimal(ZERO)) == -1) {
            throw new ArithmeticException("Square root of a negative number.");
        }

        if(maxIterations < 1)
            return originalValue;

        BigDecimal lastValue = new BigDecimal(ZERO),
                   sqrtValue = getInitialApproximation(originalValue),
                   errorValue = null;

        int currentIteration = 0;
        boolean isCalculating = true;
        while(isCalculating) {
            lastValue = sqrtValue;
            sqrtValue = originalValue.divide(sqrtValue, divisionScale, BigDecimal.ROUND_HALF_UP);
            sqrtValue = sqrtValue.add(lastValue);
            sqrtValue = sqrtValue.divide(new BigDecimal(TWO), divisionScale, BigDecimal.ROUND_HALF_UP);
            errorValue = originalValue.subtract(sqrtValue.multiply(sqrtValue));

            if(++currentIteration == maxIterations) {
                isCalculating = false;
            } else if(lastValue.equals(sqrtValue)) {
                isCalculating = errorValue.abs().compareTo(new BigDecimal(ONE)) > -1;
            }
        }
        return sqrtValue;
    }

    private static final BigDecimal getInitialApproximation(final BigDecimal originalValue) {
        int totalIntegerDigits = originalValue.toBigInteger().toString().length();
        if ((totalIntegerDigits % 2) == 0) {
            totalIntegerDigits--;
        }
        totalIntegerDigits /= 2;

        return new BigDecimal(ONE).movePointRight(totalIntegerDigits);
    }
}