LinkBack URL
About LinkBacks
Dixons factorisation implementation issue
New to using Java and I am running into an issue when trying to implement my Dixons factorisation method. Currently works for numbers of a certain size and bound but when I use higher numbers and bounds it seems to hang and never return a result even after an extensive amount of time.
I have listed my timings log of my current results (along w/ the higher numbers and bounds I am struggling with) and my code. Was wondering if anyone had an idea what I can do to speed up or sort this issue, from my understanding my logic seems to work as it gets the expected pairs and f1,f2 values for lower numbers just cant work out whats going on when using larger ones?
Was hoping someone with more experience would be able to spot what I am doing wrong and point me in the right direction. Happy to clarify/explain further if anyone has questions.
Cheers
--------
3163 * 71 = 224573 - took 0 seconds # x1,x2=(1060, 735), y1,y2=(1954, 375) Bound 7
433 * 691 = 299203 - took 0 seconds # x1,x2=(2566, 1890), y1,y2=(3587, 840) Bound 7
941 * 2087 = 1963867 - took 0 seconds # x1,x2=(8295, 71680), y1,y2=(9142, 1093750) Bound 7
857 * 7243 = 6207251 - took 0 seconds # x1,x2=(24793, 175000), y1,y2=(31619, 393750) Bound 7
2267 * 6473 = 14674291 - took 0 seconds # x1,x2=(61733, 10321920), y1,y2=(76102, 9843750) Bound 7
3821 * 6053 = 23128513 - took 0 seconds # x1,x2=(4833, 229376), y1,y2=(94367, 653184) Bound 7
500699 * 509 = 254855791 - took 0 seconds # x1,x2=(408865, 240045120), y1,y2=(728090, 15002820) Bound 7
7513673 * 57 = 428279361 - took 2 seconds # x1,x2=(498829, 62500), y1,y2=(2300861, 160000) Bound 5
346201 * 461147 = 159649552547 - took 11 seconds # x1,x2=(7667339, 37052003625), y1,y2=(8411639, 30918888000) Bound 17
372299 * 507821 = 189061250479 - took 12 seconds # x1,x2=(8123911, 15553518750), y1,y2=(8127929, 80853411870) Bound 19
Higher numbers code struggles with:-
2211744201787, Bound 23
7828669742987, Bound 83
48560209712519, Bound 79
35872004189003, Bound 97
737785058178599, Bound 71
576460921650883, Bound 397
1957432135202107, Bound 229
2450609331732137, Bound 487
----------------------------public static void main(String args[]) throws IOException { BufferedReader userInput = new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter number:"); String nString = userInput.readLine(); System.out.println("Enter bound:"); String boundString = userInput.readLine(); long startTime = System.currentTimeMillis(); FactoriseDixon(nString, boundString, startTime); } public static void FactoriseDixon(String nString, String boundString, long startTime) { BigInteger n = new BigInteger(nString); BigInteger bound = new BigInteger(boundString); ArrayList<BigInteger> bases = BuildPrimesList(bound); numberPairs(n, bases, startTime); } public static ArrayList<BigInteger> BuildPrimesList(BigInteger bound) { ArrayList<BigInteger> base = new ArrayList<>(); //i <= bound for (BigInteger i = BigInteger.valueOf(2); i.compareTo(bound) <= 0; i = i.add(BigInteger.ONE)) { if (isPrime(i)) { base.add(i); } } return base; } public static boolean isPrime(BigInteger n) { for (BigInteger i = BigInteger.valueOf(2); i.compareTo(n) < 0; i = i.add(BigInteger.ONE)) { if (n.mod(i).equals(BigInteger.ZERO)) { return false; } } return true; } public static void numberPairs(BigInteger n, ArrayList<BigInteger> base, long startTime) { LinkedList<BigInteger> pairs = new LinkedList<>(); BigInteger number = getIntSqrt(n); for (BigInteger i = number; i.compareTo(n) < 0; i = i.add(BigInteger.ONE)) { BigInteger ii = (i.multiply(i)).mod(n); if (BSmoothCheck(ii, base)) { if (pairs.size() < 2) { pairs.add(i); pairs.add(ii); } else { for (int a = pairs.size() - 1; a >= 0; a -= 2) { BigInteger x1 = pairs.get(a - 1); BigInteger x2 = pairs.get(a); BigInteger y1 = i; BigInteger y2 = ii; //testing BigInteger t1 = new BigInteger("80074177"); BigInteger t2 = new BigInteger("27381246816"); BigInteger t3 = new BigInteger("147601798"); BigInteger t4 = new BigInteger("610385230854"); boolean res1 = t1.equals(x1); boolean res2 = t2.equals(x2); boolean res3 = t3.equals(y1); boolean res4 = t4.equals(y2); if (res1 && res2 && res3 && res4) { BigInteger x = (x1.multiply(x1)).multiply(y1.multiply(y1)); //putting breakpoint here to check pairs are found BigInteger y = (x2.multiply(y2)); BigInteger modx = x.mod(n); BigInteger mody = y.mod(n); if ((modx.equals(mody))) { BigInteger sqrtx = getIntSqrt(x); BigInteger sqrty = getIntSqrt(y); if (x.equals(sqrtx.multiply(sqrtx)) && y.equals(sqrty.multiply(sqrty))) { BigInteger f1 = n.gcd(sqrtx.subtract(sqrty)); BigInteger f2 = n.gcd(sqrtx.add(sqrty)); if (!(f1.equals(BigInteger.ONE) || f2.equals(BigInteger.ONE))) { if (f1.multiply(f2).equals(n)) { //true long endTime = System.currentTimeMillis(); System.out.println(f1 + " * " + f2 + " = " + n + " - took " + ((endTime - startTime) / 1000) + " seconds"); System.exit(0); } else { pairs.add(i); pairs.add(ii); } } else { pairs.add(i); pairs.add(ii); } } else { pairs.add(i); pairs.add(ii); } } else { pairs.add(i); pairs.add(ii); } } else { pairs.add(i); pairs.add(ii); } } } } } } public static boolean BSmoothCheck(BigInteger ii, ArrayList<BigInteger> base) { BigInteger check = ii; while (true) { for (int p = 0; p < base.size(); p++) { BigInteger value = base.get(p); if (ii.mod(value).equals(BigInteger.ZERO)) { ii = ii.divide(value); if (ii.equals(BigInteger.ONE)) { return true; } } } if (ii.equals(check)) { return false; } check = ii; } } private static BigInteger getIntSqrt(BigInteger x) { BigInteger s; // final result BigInteger currentRes = BigInteger.valueOf(0); // init value is 0 BigInteger currentSum = BigInteger.valueOf(0); // init value is 0 BigInteger sum = BigInteger.valueOf(0); String xS = x.toString(); // change input x to a string xS int lengthOfxS = xS.length(); int currentTwoBits; int i = 0; // index if (lengthOfxS % 2 != 0) {// if odd length, add a dummy bit xS = "0".concat(xS); // add 0 to the front of string xS lengthOfxS++; } while (i < lengthOfxS) { // go through xS two by two, left to right currentTwoBits = Integer.valueOf(xS.substring(i, i + 2)); i += 2; // sum = currentSum*100 + currentTwoBits sum = currentSum.multiply(BigInteger.valueOf(100)); sum = sum.add(BigInteger.valueOf(currentTwoBits)); // subtraction loop do { currentSum = sum; // remember the value before subtract // in next 3 lines, we work out currentRes = sum - 2*currentRes - 1 sum = sum.subtract(currentRes); currentRes = currentRes.add(BigInteger.valueOf(1)); // currentRes++ sum = sum.subtract(currentRes); } while (sum.compareTo(BigInteger.valueOf(0)) >= 0); // stop when sum < 0 currentRes = currentRes.subtract(BigInteger.valueOf(1)); // go one step back currentRes = currentRes.multiply(BigInteger.valueOf(10)); } s = currentRes.divide(BigInteger.valueOf(10)); // go one step back return s; }
Reply With Quote
