ample, assume the composite number N = 35. The values of x2 = Z mod 35 are listed in Table 20.3. We observe from the table that x2 = 1 mod 35 has two nontrivial solutions X1 = 6 and X2 = 29 = -6 mod 35, or, equivalently, X = +6 mod 35. With the solution X1 = 6, we obtain GCD(x1 - 1, N) = GCD(5, 35) = 5 and GCD(x1 + 1, N) = GCD(7, 35) = 7. With the other equivalent solution x2 = 29, we obtain GCD(x2 - 1, N) = GCD(28, 35) = 7 and GCD(x2 + 1, N) = GCD(30, 35) = 5. Thus, any of the solutions yield two GCDs that are both factors of N = 35. As a second example, assume the composite number N = 561. With a tabulating spreadsheet, we find the solutions x2 = 1 mod 561 to be X1 = 67, x2 = 188, X3 = 254, X4 = 307,. X5 = 373, and x6 = 494, or, equivalently, x = +67, +188, +254. We can find GCD(x) + 1, N) by means of the extended Euclidian algorithm. 12 Given two numbers a, b such that a > b, the algorithm can be summarized through the iterated operation: (a,b) (a',b') = (b,a mod ) b), (20.28) which at the stage where b' = 0 yields a' = GCD(a,b). Let us illustrate the algorithm through a basic example. Considering a = 561 and b = 189 for instance, we obtain the following iteration: (561, 189) (a',b') = (189,183) (189, (b) = (183, 6) (183, 6) (a',b') = (6,3) (6,3) a',b') = (3,0). The result obtained in the final iteration (where b = 0) shows that GCD(561, 189) = 3. Using the algorithm and a computing spreadsheet, we easily obtain for the solutions X1, X2, X3: GCD(x1 - 1, N) = GCD(66,561) = 33 GCD(x) + 1, N) = GCD(68, 561) = 17 GCD(x2 - 1, N) = GCD(187, 561) = 187 GCD(x2 + 1, N) = GCD(189, 561) = 3 GCD(x3 - 1, N) = GCD(253, 561) = 11 GCD(x3 + 1, N) = GCD(255, 561) = 51. See, for instance: http://en.wikipedia.org/wiki/Euclidean_algorithm. Shor's factorization algorithm It is readily checked that 561 = 33 X 17 = 3 X = 11 X 51 = 3 X 11 X 17, which shows that GCD(x) 1, N) is always a factor of N. We also observe that given a single solution Xi, one of the two corresponding GCD, i.e., GCD(x) 1, N), is a prime factor of N (namely, 3, 