Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Math/CS 467 (Lesieutre)

Homework 9

Problem 1. This whole problem set deals with factoring 9991 using the quadratic sieve. (Yes, you can see the factorization right away: it’s 9991 = 100² − 3² = 97 · 103, but let’s use the algorithm to understand how it works.)

We are going to use the bound B = 30 on our primes.

a) First, find the factor base. This is all primes p such that p ≤ B and = 1. You probably want to use your Jacobi symbol implementation.

b) How many primes are in your factor base? How many values of ri are we going to need to guarantee that some product of them is a perfect square? Explain.

Problem 2. We will start looking for r values at = 100. Make a list of 41 r values, all r from 100 up to 140. For each r value, we compute s(r) = ln(r² − n) and store all of these in another list.

For each prime p in the factor base, we identify all the values of r for which r² − n is a multiple of p. Then we subtract log(p) from s(r) for each of these r-values.

a) For p = 11, which values of r in our list will have r² − n a multiple of 11? (Hint: Tonelli’s algorithm would tell you that 9991 ≡ 3 mod 11, and we have 5² ≡ 3 mod 11.)

b) After the process of subtracting log(p) is complete, we find the “good” r values by looking for entries in the s(r) list which are close to 0.

One such r value is r = 101. What was the initial value of s(r)? For which p would we subtract log p from s(r)? What is the final value of s(r)?

c) Consider the value r = 116. What was the final value of s(r) here? Is this still a good r value to include in our list?

Problem 3. Now we take the numbers output by the sieve and start trying to multiply them together. The list of r’s produced by my sieving procedure was:

r = 100, 101, 104, 109, 115, 116, 118, 129, 137.

(There are actually a couple more r that would work (r = 107, for example), but the sieve missed them due to large prime powers. That’s OK: it doesn’t really matter, and doing a more careful search would slow the algorithm down!)

a) For each of those r values, we need to represent the exponents of the factorization as a vector, and then assemble all the vectors as the columns of a matrix. What matrix do you get?

b) To figure out which r values to multiply together to get a perfect square, we need to find a combination of the columns in which all the entries are even.

To do this, you take your matrix M, reduce it mod 2, perform row reduction mod 2, and then read off the solutions. One solution vector you obtain in this way is

v = [0 0 0 1 1 1 0 0 0]

Using this vector, which r values do we multiply together to get x? What is the value of x mod n?

c) What y value do we obtain from this solution vector? (y will a product of powers of some primes in our factor base, reduced mod n.) Check that x² ≡ y² mod n, as needed.

d) Finally we use Kraitchik’s algorithm. Compute gcd(x − y, n). Did you find a factor?