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

# Thread: Dixons factorisation implementation issue

1. ## 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 {

System.out.println("Enter number:");
System.out.println("Enter bound:");
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)) {
}
}
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) {
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) {

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

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 {
}
} else {
}
} else {
}
} else {
}
} else {
}
}
}
}
}
}

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

}```

2. ## 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?

3. ## 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. ## 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.

5. ## 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. ## 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");

7. ## 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:");
System.out.println("Enter bound:");
long startTime = System.currentTimeMillis();
FactoriseDixon(nString, boundString, startTime);```

8. ## 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.

9. ## 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. ## 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.

11. ## 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. ## 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.

13. ## 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:");
//        System.out.println("Enter bound:");
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. ## 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.

15. ## 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)) {
}
}
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) {
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) {

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

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 {
}
} else {
}
} else {
}
} else {
}
} else {
}
}
}
}
}
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));
// 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);
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.

16. ## 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?

17. ## 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. ## Re: Dixons factorisation implementation issue

Why do you think the values of t1 - t4 are correct for the cases where the code fails?

19. ## 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. ## Re: Dixons factorisation implementation issue

Yes, it runs for a long time.

21. ## 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. ## 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?

23. ## 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. ## 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.

25. ## 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 Last