Quadratic sieve for n = 1100017 1023^2 - n = -53488 = -2^4 * 3343. 1024^2 - n = -51441 = -3 * 13 * 1319. 1025^2 - n = -49392 = -2^4 * 3^2 * 7^3. 1026^2 - n = -47341 = -7 * 6763. 1027^2 - n = -45288 = -2^3 * 3^2 * 17 * 37. 1028^2 - n = -43233 = -3 * 14411. 1029^2 - n = -41176 = -2^3 * 5147. 1030^2 - n = -39117 = -3 * 13 * 17 * 59. 1031^2 - n = -37056 = -2^6 * 3 * 193. 1032^2 - n = -34993 = -7 * 4999. 1033^2 - n = -32928 = -2^5 * 3 * 7^3. 1034^2 - n = -30861 = -3^5 * 127. 1035^2 - n = -28792 = -2^3 * 59 * 61. 1036^2 - n = -26721 = -3^2 * 2969. 1037^2 - n = -24648 = -2^3 * 3 * 13 * 79. 1038^2 - n = -22573 = -22573. 1039^2 - n = -20496 = -2^4 * 3 * 7 * 61. 1040^2 - n = -18417 = -3 * 7 * 877. 1041^2 - n = -16336 = -2^4 * 1021. 1042^2 - n = -14253 = -3 * 4751. 1043^2 - n = -12168 = -2^3 * 3^2 * 13^2. 1044^2 - n = -10081 = -17 * 593. 1045^2 - n = -7992 = -2^3 * 3^3 * 37. 1046^2 - n = -5901 = -3 * 7 * 281. 1047^2 - n = -3808 = -2^5 * 7 * 17. 1048^2 - n = -1713 = -3 * 571. 1049^2 - n = 384 = 2^7 * 3. 1050^2 - n = 2483 = 13 * 191. 1051^2 - n = 4584 = 2^3 * 3 * 191. 1052^2 - n = 6687 = 3^2 * 743. 1053^2 - n = 8792 = 2^3 * 7 * 157. 1054^2 - n = 10899 = 3^2 * 7 * 173. 1055^2 - n = 13008 = 2^4 * 3 * 271. 1056^2 - n = 15119 = 13 * 1163. 1057^2 - n = 17232 = 2^4 * 3 * 359. 1058^2 - n = 19347 = 3 * 6449. 1059^2 - n = 21464 = 2^3 * 2683. 1060^2 - n = 23583 = 3 * 7 * 1123. 1061^2 - n = 25704 = 2^3 * 3^3 * 7 * 17. 1062^2 - n = 27827 = 27827. 1063^2 - n = 29952 = 2^8 * 3^2 * 13. 1064^2 - n = 32079 = 3 * 17^2 * 37. 1065^2 - n = 34208 = 2^5 * 1069. 1066^2 - n = 36339 = 3 * 12113. 1067^2 - n = 38472 = 2^3 * 3 * 7 * 229. 1068^2 - n = 40607 = 7 * 5801. 1069^2 - n = 42744 = 2^3 * 3 * 13 * 137. 1070^2 - n = 44883 = 3^2 * 4987. 1071^2 - n = 47024 = 2^4 * 2939. 1072^2 - n = 49167 = 3^4 * 607. 1073^2 - n = 51312 = 2^4 * 3 * 1069. Take smoothness bound B = 20 1047^2 - n = -3808 = -2^5 * 7 * 17. 1043^2 - n = -12168 = -2^3 * 3^2 * 13^2. 1033^2 - n = -32928 = -2^5 * 3 * 7^3. 1025^2 - n = -49392 = -2^4 * 3^2 * 7^3. 1049^2 - n = 384 = 2^7 * 3. 1061^2 - n = 25704 = 2^3 * 3^3 * 7 * 17. 1063^2 - n = 29952 = 2^8 * 3^2 * 13. +/- 1 1 1 1 0 0 0 2 5 3 5 4 7 3 8 3 0 2 1 2 1 3 2 7 1 0 3 3 0 1 0 13 0 2 0 0 0 0 1 17 1 0 0 0 0 1 0 modulo 2: +/- 1 1 1 1 0 0 0 2 1 1 1 0 1 1 0 3 0 0 1 0 1 1 0 7 1 0 1 1 0 1 0 13 0 0 0 0 0 0 1 17 1 0 0 0 0 1 0 Solve with Gaussian elimination over Z_2: Find that solution space is span of two vectors: 0 1 0 1 1 1 1 1 1 0 0 1 0 0 The first vector corresponds to (1033 * 1025 * 1049)^2 = 2^16 * 3^4 * 7^6 modulo n gcd(1033 * 1025 * 1049 - 2^8* 3^2 * 7^3, 1100017) = 1100017 %Failure !!! The second vector corresponds to (1047 * 1043 * 1033 * 1025 * 1061)^2 = 2^20 * 3^8 * 7^8 * 13^2 * 17^2 modulo n gcd(1047 * 1043 * 1033 * 1025 * 1061 - 2^10 * 3^4 * 7^4 * 13 * 17, 1100017) = 547 %success !!! We find 1100017 = 547 * 2011