If you're asking what programming language to use, then it's not asking for that, but if doing that helps, then I guess Java would work.

For each part, use the data provided to find values of a and b satisfying a2 b2 (mod N ), and then compute gcd(N, a b) in order to find a nontrivial factor of N, as we did in Examples 3.36 and 3.37.

3.6. Factorization via difference of squares 139 1. Relation Building: Find many integers a1, a2, a3,.. . , ar with the al (mod N) factors as a product of property that the quantity ci small primes 2. Elimination: Take a product ci, cia . ..Ci, of some of the ci's so that every prime appearing in the product appears to an even power. Then Cii Ci2 Ci, . b2 is a perfect square 3. GCD Computation: Let a ai.aiz.. ai, and compute the greatest common divisor d = gcd(N, a-b). Since there is a reasonable chance that d is a nontrivial factor of N. Table 3.4: A three step factorization procedure Erample 3.36. We ach for integerswihthe propat each mod N be Ea ample 3.36. We factor N 914387 using the procedure described in Ta- ble 3.4. We first search for integers a with the property that a2 mod N is a product of small primes. For this example, we ask that each a2 mod N be a product of primes in the set {2,3,5,7,11). Ignoring for now the question of how to find such a, we observe that 18692 750000 (mod 914387) 19092-901120 (mod 914387) 33872 499125 (mod 914387) and and and 750000 24.3.56, 901120 -214-5-11, 499125 = 3-53, 113. None of the numbers on the right is a square, but if we multiply them together, then we do get a square. Thus 18692 . 19092 . 33872-750000 . 901120-499125 (mod 914387) (24 . 3 . 56)(214-5-11)(3-53, 113) (20-3-55-112)2 5808000002 1642552 (mod 914387). (mod 914387) We further note that 1869-1909-3387 9835 (mod 914387), so we compute gcd (914387,9835 - 164255) - gcd (914387,154420) 1103 Hooray! We have factored 914387 = 1103-829 3.6. Factorization via difference of squares 139 1. Relation Building: Find many integers a1, a2, a3,.. . , ar with the al (mod N) factors as a product of property that the quantity ci small primes 2. Elimination: Take a product ci, cia . ..Ci, of some of the ci's so that every prime appearing in the product appears to an even power. Then Cii Ci2 Ci, . b2 is a perfect square 3. GCD Computation: Let a ai.aiz.. ai, and compute the greatest common divisor d = gcd(N, a-b). Since there is a reasonable chance that d is a nontrivial factor of N. Table 3.4: A three step factorization procedure Erample 3.36. We ach for integerswihthe propat each mod N be Ea ample 3.36. We factor N 914387 using the procedure described in Ta- ble 3.4. We first search for integers a with the property that a2 mod N is a product of small primes. For this example, we ask that each a2 mod N be a product of primes in the set {2,3,5,7,11). Ignoring for now the question of how to find such a, we observe that 18692 750000 (mod 914387) 19092-901120 (mod 914387) 33872 499125 (mod 914387) and and and 750000 24.3.56, 901120 -214-5-11, 499125 = 3-53, 113. None of the numbers on the right is a square, but if we multiply them together, then we do get a square. Thus 18692 . 19092 . 33872-750000 . 901120-499125 (mod 914387) (24 . 3 . 56)(214-5-11)(3-53, 113) (20-3-55-112)2 5808000002 1642552 (mod 914387). (mod 914387) We further note that 1869-1909-3387 9835 (mod 914387), so we compute gcd (914387,9835 - 164255) - gcd (914387,154420) 1103 Hooray! We have factored 914387 = 1103-829