Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Page 1 of 2 12 LastLast
Results 1 to 25 of 27

Thread: Dixons factorisation implementation issue

  1. #1
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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;
     
        }
    Last edited by programmer123; November 22nd, 2018 at 12:10 PM.

  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    it seems to hang
    How are you trying to debug the code to see why and where that happens?
    Have you tried adding print statements to see where the execution is going and where the values are changing?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    I have added in a testing section where I check that is getting the right pairs.

    if (res1 && res2 && res3 && res4) {
    //breakpoint here i.e. if this breakpoint is hit the correct pairs are being found. I update t1->t4 accordingly. This testing works for the previous ones but when I tried to do it for the next number (2211744201787, Bound 23) it never hits the breakpoint. I have left it to run for over 2 hours but still the breakpoint never gets hit but no error is thrown. Note: Current t1->t4 values are for the 2211744201787 number. If you adjust them to a previous one you should be able to see that it does work.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    it never hits the breakpoint.
    Have you tried debugging the code to see why not?

    Note: I know nothing about the algorithm you are using.
    I have done lots of debugging.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    Its hard to debug because I don't know at what number of iterations of the for loop will generate those required 4 digits. Which is why I put a check to make sure they are those 4 digits. The fact that it isn't being hit obviously points to those numbers never being generated but I cant see why as I have no issues with that on the previous number examples.

    Currently the code generates 4 digits for x1,x2,y1,y2 and then checks them. To try and sort this issue I altered the code so it built up all the array with numbers that are BSmooth and then iterated and checked through them but it so long to build up the list I changed it back.

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    What is the input to the program to have it work?
    It never ended when I tried this change to code in the main method:
            StringReader sr = new StringReader("224573\n7"); 
            BufferedReader userInput = new BufferedReader(sr); //new InputStreamReader(System.in));
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    If you use the logic from my main, the one you tried would need 224573 as the number and 7 as the bound

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

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    need 224573 as the number and 7 as the bound
    See the code I posted from the main method. I put those numbers as Strings in the StringReader class and passed it to the BufferedReader to read.
    No need to type in at the console. The input data is in the program.

    The code ran too long without any output, so I ended it. The posted code did not work for me.

    Change the code in main to use those statements.
    Also add this print statement in the method as shown:
        public static void FactoriseDixon(String nString, String boundString, long startTime) {
            System.out.println("factoring:" + nString + " with bound="+boundString);  //<<<<  factoring:224573 with bound=7

    Run the program to see if you get the expected results.
    If you don't understand my answer, don't ignore it, ask a question.

  9. #9
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    Have you adjusted the testing params to match the number you are using ?

    i.e. 3163 * 71 = 224573 - took 0 seconds # x1,x2=(1060, 735), y1,y2=(1954, 375) Bound 7
    t1 = 1060
    t2 = 735
    t3 = 1954
    t4 = 375

  10. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    Have you adjusted the testing params to match the number you are using
    No. I expected that the program should handle that.
    If you don't understand my answer, don't ignore it, ask a question.

  11. #11
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    Hopefully this should get the code working for you. All of the others have been listed above. For testing purposes of the first one that "hangs" the values should be x1,x2=(80074177, 27381246816), y1,y2=(147601798, 610385230854), f=(4417313, 500699) (for testing purposes)

  12. #12
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    Sorry, I'd rather that you put the values into the code so that it is easily tested and so that I can be assured that the code I'm executing is the same as what you are using.

    One easy way would be to have a bunch of StringReader statements coded in the main with all but one commented out.
    All needed program data would come from the String in the StringReader's constructor.
    If you don't understand my answer, don't ignore it, ask a question.

  13. #13
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    Testing is just a quick thing i added so those params will quickly need adjusting depending on which which number you are running or you can comment the testing if out if you want to run multiple.

    //        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("224573", "7", startTime); // testing params x1,x2=(1060, 735), y1,y2=(1954, 375)
            //FactoriseDixon("299203", "7", startTime); // testing params x1,x2=(2566, 1890), y1,y2=(3587, 840)
            //FactoriseDixon("1963867", "7", startTime); // testing params x1,x2=(8295, 71680), y1,y2=(9142, 1093750)
            //FactoriseDixon("6207251", "7", startTime); // testing params x1,x2=(24793, 175000), y1,y2=(31619, 393750) 
            //FactoriseDixon("14674291", "7", startTime); // testing params x1,x2=(61733, 10321920), y1,y2=(76102, 9843750) 
            //FactoriseDixon("23128513", "7", startTime); // testing params x1,x2=(4833, 229376), y1,y2=(94367, 653184)
            //FactoriseDixon("254855791", "7", startTime); // testing params x1,x2=(408865, 240045120), y1,y2=(728090, 15002820) 
            //FactoriseDixon("428279361", "5", startTime); // testing params x1,x2=(498829, 62500), y1,y2=(2300861, 160000)
            //FactoriseDixon("159649552547", "17", startTime); // testing params x1,x2=(7667339, 37052003625), y1,y2=(8411639, 30918888000) 
            //FactoriseDixon("189061250479", "19", startTime); // testing params x1,x2=(8123911, 15553518750), y1,y2=(8127929, 80853411870)
     
            //FactoriseDixon("428279361", "5", startTime); //first one that hangs testing params x1,x2=(80074177, 27381246816), y1,y2=(147601798, 610385230854)

  14. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    Those values are just comments. The code needs to be changed to have the values needed for each test be set.
    If you don't understand my answer, don't ignore it, ask a question.

  15. #15
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    public static void main(String args[]) throws IOException {
     
            long startTime = System.currentTimeMillis();
            FactoriseDixon("224573", "7", startTime, 1);
            FactoriseDixon("299203", "7", startTime, 2);
            FactoriseDixon("1963867", "7", startTime, 3);
            FactoriseDixon("6207251", "7", startTime, 4);
            FactoriseDixon("14674291", "7", startTime, 5);
            FactoriseDixon("23128513", "7", startTime, 6);
            FactoriseDixon("254855791", "7", startTime, 7);
            FactoriseDixon("428279361", "5", startTime, 8);
            FactoriseDixon("159649552547", "17", startTime, 9);
            FactoriseDixon("189061250479", "19", startTime, 10);
     
    //        FactoriseDixon("2211744201787", "23", startTime, 11);
    //        FactoriseDixon("7828669742987", "83", startTime, 12);
    //        FactoriseDixon("48560209712519", "79", startTime, 13);
    //        FactoriseDixon("35872004189003", "97", startTime, 14);
    //        FactoriseDixon("737785058178599", "71", startTime, 15);
    //        FactoriseDixon("576460921650883", "397", startTime, 16);
    //        FactoriseDixon("1957432135202107", "229", startTime, 17);
    //        FactoriseDixon("2450609331732137", "487", startTime, 18);
     
        }
     
        public static void FactoriseDixon(String nString, String boundString, long startTime, int TestNo) {
     
            BigInteger n = new BigInteger(nString);
            BigInteger bound = new BigInteger(boundString);
            ArrayList<BigInteger> bases = BuildPrimesList(bound);
            numberPairs(n, bases, startTime, TestNo);
     
        }
     
        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 boolean numberPairs(BigInteger n, ArrayList<BigInteger> base, long startTime, int testNo) {
            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("0");
                            BigInteger t2 = new BigInteger("0");
                            BigInteger t3 = new BigInteger("0");
                            BigInteger t4 = new BigInteger("0");
     
                            switch (testNo) {
                                case 1:
                                    t1 = new BigInteger("1060");
                                    t2 = new BigInteger("735");
                                    t3 = new BigInteger("1954");
                                    t4 = new BigInteger("375");
                                    break;
                                case 2:
                                    t1 = new BigInteger("2566");
                                    t2 = new BigInteger("1890");
                                    t3 = new BigInteger("3587");
                                    t4 = new BigInteger("840");
                                    break;
                                case 3:
                                    t1 = new BigInteger("8295");
                                    t2 = new BigInteger("71680");
                                    t3 = new BigInteger("9142");
                                    t4 = new BigInteger("1093750");
                                    break;
                                case 4:
                                    t1 = new BigInteger("24793");
                                    t2 = new BigInteger("175000");
                                    t3 = new BigInteger("31619");
                                    t4 = new BigInteger("393750");
                                    break;
                                case 5:
                                    t1 = new BigInteger("61733");
                                    t2 = new BigInteger("10321920");
                                    t3 = new BigInteger("76102");
                                    t4 = new BigInteger("9843750");
                                    break;
                                case 6:
                                    t1 = new BigInteger("4833");
                                    t2 = new BigInteger("229376");
                                    t3 = new BigInteger("94367");
                                    t4 = new BigInteger("653184");
                                    break;
                                case 7:
                                    t1 = new BigInteger("408865");
                                    t2 = new BigInteger("240045120");
                                    t3 = new BigInteger("728090");
                                    t4 = new BigInteger("15002820");
                                    break;
                                case 8:
                                    t1 = new BigInteger("498829");
                                    t2 = new BigInteger("62500");
                                    t3 = new BigInteger("2300861");
                                    t4 = new BigInteger("160000");
                                    break;
                                case 9:
                                    t1 = new BigInteger("7667339");
                                    t2 = new BigInteger("37052003625");
                                    t3 = new BigInteger("8411639");
                                    t4 = new BigInteger("30918888000");
                                    break;
                                case 10:
                                    t1 = new BigInteger("8123911");
                                    t2 = new BigInteger("15553518750");
                                    t3 = new BigInteger("8127929");
                                    t4 = new BigInteger("80853411870");
                                    break;
                                case 11:
                                    t1 = new BigInteger("80074177");
                                    t2 = new BigInteger("27381246816");
                                    t3 = new BigInteger("147601798");
                                    t4 = new BigInteger("610385230854");
                                    break;
                                case 12:
                                    t1 = new BigInteger("10893027");
                                    t2 = new BigInteger("1227991077924");
                                    t3 = new BigInteger("16752641");
                                    t4 = new BigInteger("6647539470336");
                                    break;
                                case 13:
                                    t1 = new BigInteger("90259799");
                                    t2 = new BigInteger("37276293529728");
                                    t3 = new BigInteger("96332373");
                                    t4 = new BigInteger("4926032720000");
                                    break;
                                case 14:
                                    t1 = new BigInteger("54601353");
                                    t2 = new BigInteger("3931401743360");
                                    t3 = new BigInteger("81911051");
                                    t4 = new BigInteger("1355492581040");
                                    break;
                                case 15:
                                    t1 = new BigInteger("38413234");
                                    t2 = new BigInteger("6429981558");
                                    t3 = new BigInteger("40121486");
                                    t4 = new BigInteger("134163522490998");
                                    break;
                                case 16:
                                    t1 = new BigInteger("29676345");
                                    t2 = new BigInteger("304224530908142");
                                    t3 = new BigInteger("31151201");
                                    t4 = new BigInteger("393936402091518");
                                    break;
                                case 17:
                                    t1 = new BigInteger("46914861");
                                    t2 = new BigInteger("243572047447214");
                                    t3 = new BigInteger("49285749");
                                    t4 = new BigInteger("471652919288894");
                                    break;
                                case 18:
                                    t1 = new BigInteger("49511948");
                                    t2 = new BigInteger("823663022567");
                                    t3 = new BigInteger("51925520");
                                    t4 = new BigInteger("245650295538263");
                                    break;
                            }
     
                            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));
                                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");
                                                return true;
     
                                            } 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);
                            }
                        }
                    }
                }
            }
            return false;
        }
     
        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;
     
        }



    Note: Updated code, allows running of multiple numbers. Added all tests, data and numbers. Hoping someone may be able to spot where/what the issue is thats making the factorising of 2211744201787 and the subsequent numbers after to hang for a prolonged period of time. Much appreciated.
    Last edited by programmer123; November 22nd, 2018 at 05:19 PM.

  16. #16
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    Why is the switch statement inside the loop? Could the values of t1 - t4 be set one time outside of the loop?

    Why do you think the values of t1 - t4 are correct for the cases where the code fails?
    If you don't understand my answer, don't ignore it, ask a question.

  17. #17
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    Im sorry can we focus on the actual issue I have as like I said previously the testing is just simply something I added to debug and locate the issue. So whether the t1- t4 can be set outside the loop isn't really pertinent to my problem I don't think.

  18. #18
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    Why do you think the values of t1 - t4 are correct for the cases where the code fails?
    If you don't understand my answer, don't ignore it, ask a question.

  19. #19
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    Those were the model answers given to use for testing

    --- Update ---

    Are you experiencing the same issue when running it for 2211744201787?

  20. #20
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    Yes, it runs for a long time.
    If you don't understand my answer, don't ignore it, ask a question.

  21. #21
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    Okay, well do you have any ideas on why/how to solve that issue? Because that is my issue, as you can see by running the 10 previous numbers they output as expected all within half a minute so my underlying logic works. Just need some guidance on how I can solve this because I am all out of ideas.

    if (res1 && res2 && res3 && res4) {
     
                                BigInteger x = (x1.multiply(x1)).multiply(y1.multiply(y1));

    The fact that putting a breakpoint on this line after checking the pairs either shows the pair values expected are not there which I don't understand or that I am not waiting long enough (enough iterations of the for loop) for it get them. Any ideas would be greatly appreciated

  22. #22
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    Do you understand how the algorithm works?
    Have you added some print statements to see what values the code is generating?
    For example after the call to BSmoothCheck print the values of ii, base and pairs.size()
    Are the printed values what are expected?
    If you don't understand my answer, don't ignore it, ask a question.

  23. #23
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    The algorithm comes after my problem and that logic works, my issue is getting/testing if the correct pairs are being retrieved.

    I have added the snippet below for the first of the numbers that seem to hang, my issue is though of course that it hangs forever before it can ever iterate enough times to get to a number bigger than 147600000 (a number I chose as its just a little bit smaller than the actual value so it would print/show the iteration up to that value). This method works for the previous numbers when I adjust the testingNo value.

    for (BigInteger i = number; i.compareTo(n) < 0; i = i.add(BigInteger.ONE)) {
                BigInteger ii = (i.multiply(i)).mod(n);
                //testing 
                BigInteger testingNo = new BigInteger("147600000");
                if(i.compareTo(testingNo) > 0){
                    System.out.println(i + ", " + ii);
                }
                if (BSmoothCheck(ii, base)) {

  24. #24
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,318
    Thanks
    53
    Thanked 2,392 Times in 2,346 Posts

    Default Re: Dixons factorisation implementation issue

    getting/testing if the correct pairs are being retrieved.
    Do their values look correct when you print them?

    it hangs forever
    Do you mean the code is in a loop somewhere? Do you know where the loop is and why the code gets into the loop?
    Add more print statements to show what is happening.
    If you don't understand my answer, don't ignore it, ask a question.

  25. #25
    Junior Member
    Join Date
    Nov 2018
    Posts
    16
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dixons factorisation implementation issue

    It gets the expected values for the 10 previous yes.

    Its not caught up in a loop it just takes a long amount of time to iterate all the way up to that number (for loop starts from sqrt of n, in this case 1487193 and iterates by 1 so to get to 147601798 it will take a significant amount of time), if i print each i, ii value it will take even longer which is why i made it only print when it was close the expected value.

    So my problem I don't think is that its not getting the pairs its that it takes wayyyyy too long to iterate up to get them. So what I wanted help with is to try and minimise this timing lag.

    --- Update ---

    Are you able to offer me any alternatives to the way I am doing it that will stop/limit the time it takes to get the pairs?

Page 1 of 2 12 LastLast

Similar Threads

  1. Implementation problem.
    By AlchemyDesign in forum Java Theory & Questions
    Replies: 7
    Last Post: September 15th, 2014, 06:11 PM
  2. stack implementation
    By mosarwa10 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 12th, 2013, 06:22 PM
  3. Vector implementation
    By poolman81 in forum Collections and Generics
    Replies: 11
    Last Post: June 3rd, 2012, 06:45 AM
  4. Java Issue / Cache issue
    By VisualPK in forum What's Wrong With My Code?
    Replies: 1
    Last Post: April 14th, 2012, 08:43 PM
  5. ArrayList implementation
    By meijuh in forum Collections and Generics
    Replies: 8
    Last Post: March 22nd, 2012, 01:03 PM

Tags for this Thread