## The matrix stage of integer factorization sieves.

Modern general-purpose methods of integer factorization consist of two major stages: Sieving, and linear algebra. In the sieving stage, a large set of "relations" are produced of the form "product of primes = something squared modulo N" (the number field sieve uses prime ideals in a number field, but the general idea is the same). In the linear algebra stage, a combination of relations is found which, when multiplied together, produces an equation of the form "something squared = something else squared modulo N" -- in other words, all of the primes on the left side of the equation are raised to even powers -- and from this it is easy to find factors of N. The linear algebra stage is so named because finding the correct combination of relations to multiply together is equivalent to solving a large sparse system of linear equations modulo 2.
Out of these two stages, the linear algebra is generally considered
to be the harder. Whereas the sieving can be distributed across a large
number of machines, current methods for solving the sparse linear system
(for example, block Lanczos) require tightly-coupled processors:
The time taken to solve a matrix with *n* rows and weight *w*
on a network with interprocessor latency *L* is *O(n w + n L)*,
and with the matrices often having tens of millions of rows, even a
network latency of a millisecond will add hours to the computation.
Clearly, if the size of the matrix can be reduced via some preprocessing,
this will make finding the solution much faster -- as long as the matrix
weight doesn't increase too much.

The oldest method for solving systems of linear equations is Gaussian elimination. Find a non-zero element of the matrix, and add multiples of its row to other rows in order to eliminate all the other non-zero entries in the same column. Unfortunately, this naive method results in the weight of the matrix increasing rapidly -- so-called "catastrophic fill-in". A somewhat more intelligent approach called "Structured Gaussian elimination" is also available; in this method, the matrix is split into two parts, labeled as the "dense" and "sparse" parts, and the pivot used is chosen in order to minimize the increase in the weight of the sparse part. This approach also ends up causing rapid matrix fill-in, but at least makes some useful progress first: Depending upon the source of the original matrix, it can often reduce the matrix size by a factor of 10 or more before it reaches the point where continuing would be disadvantageous due to increasing matrix weight. As a result, structured Gaussian elimination is useful as a method of matrix preprocessing, but not as a method of matrix solution.

Now for the interesting question: Why are we trying to *eliminate*
columns at each stage? What if, instead, we view the problem as one of
lattice reduction, and add rows to each other not with a view to reducing
the number of active columns directly, but instead with the intention of
decreasing the matrix weight?

If we consider the rows of the matrix as zero-one vectors, then any time
the dot product of two rows is more than half of the number of nonzero entries
in the lighter row, we can add the lighter row to the heavier row and
reduce the total matrix weight. Instead of taking a row and adding it to
*all* the other rows with nonzero entries in a particular column,
just add it to a few other rows -- the ones whereby you can decrease the
matrix weight. Of course, this relies upon being able to find rows which
are not too close to orthogonal, but there is a good reason to think that
they might exist: If two medium-sized primes *p* and *q* appear
in a relation which is used to eliminate a large prime in several other
relations, then unless either of those primes also appeared in the other
relations, all of the new relations will contain both of those primes.
As a result, groups of primes tend to "stick together", which increases
the largest dot products of pairs of rows.

Can this sort of approach provide a significant benefit over existing methods? It's too early to be certain, but on some "toy problems" -- matrices arising from applying the quadratic sieve to 18-digit numbers using a factor base of a few thousand primes -- I found that structured Gaussian elimination ended up with catastrophic fill-in (not that filling in a matrix of a few hundred rows is particularly catastrophic), while this lattice reduction approach steadily reduced the matrix weight.

## CBC and CMG reach a tentative deal.

The Canadian Broadcasting Corporation and the Canadian Media Guild have reached an agreement in principle to end the current lockout. I'm not going to recycle news from around the Web, but Tod Maffin of CBCunplugged interviewed one of the CMG's lead negotiators and asked if anyone could produce a transcript of the interview. Without any further ado:
**Tod Maffin**: This is a special edition of CBCunplugged.com, it is late
at night on Sunday -- I guess now currently Monday, October the 3rd --
and on the line is Arnold Amber, with the CMG negotiating team. Arnold,
you must be exhausted.

**Arnold Amber**: Sure am. Yesterday, we worked right through until 6AM Sunday
morning, were back at it already back across the river in Gatineau at noon,
and we finished up now, and I'm just getting back to the Hotel and it's 2
o'clock in the morning. So, a long and hard struggle; many many months.

**TM**: What comes next; what are the next steps? I know that it is an agreement
in principle, so presumably there is still some language text to work out.

**AA**: First of all, the ceremony: We go back to the mediation services of the
Canadian government offices in Gatineau Quebec tomorrow morning; 9:30 we
meet with the labour minister under whose auspices the talks these last
seven days went on; we then will sign an agreement, a memorandum of
agreement; and then we work out perhaps one of the most important things
we're going to do over the next little while, and that is the Return To
Work protocol -- these are the terms and conditions by which all our
members will be reintegrated into the CBC -- and finally, the Canadian
Broadcasting Corporation radio, television, and dot-ca will finally be
able to restore the services that Canadians have used so widely and of
which we heard so much about over the lockout about how much they miss.

**TM**: What pushed the final moment? Did the guild make an offer, did the
labour ministry intervene; what point was the actual tipping point in
this tonight?

**AA**: In my view there were two tipping points. One of them occurred
Mon- uh, Wed- uh, sorry, Saturday morning. Saturday morning, when one
of the mediators, Don Howard (?), stood up in a meeting, two representatives
of the Guild, me and Dan Olsen from the Guild, and two representatives from
the CBC and two mediators, him and Elizabeth MacPherson, the head of the
mediation services, and he suggested a way that we could overcome two or
three issues that still stood out, and drew some things on the board, and
from that we rapidly developed a mechanism for moving forward, and although
Saturday turned out to be a long hard day, that was the first of many tipping
points.

**AA**: The second point was, there's something that I -- you know, I'm one
of the "veteran" if I may put it in slight terms, negotiators with the
CBC, in other words, I've done many many years -- but talking to some of
the younger folks on this negotiating team, I said "you know, you'll find
it very surprising, but until someone says 'yes' across the table,
they often say 'no' very loudly and insistently". All the way up until
8:30, 9 o'clock on Sunday, the CBC was holding firm to various things and
acting in a very certain way; and finally we exchanged paper. The CBC
submitted a list of what it called the "outstanding issues" in the dispute
and their positions about them, and they asked us to do the same; and Dan
Olsen and I got together and wrote up our paper and submitted it to
the CBC, somewhere in the neighbourhood of 9 o'clock. They came back
a little after 11, and their response to our paper was very positive. There
were two more passes between parties to finally work out all the agreements,
and then by about 12:20 Monday morning that was that.

**TM**: Awesome. Well, I know you're exhausted; I'll let you get some sleep and
I really appreciate your time.

**AA**: Before I do go, I just really think that I have to say two things. The
first thing is that this particular dispute has ended now, and what it
established beyond a shadow of a doubt is that at the CBC, public broadcasting
and Canada's national broadcaster, the Guild has been able to reassert the
notion in contract language that a permanent workforce is the heartthrob of
the corporation. We have a cap now on the percentage of contract workers that
the CBC will be allowed to bring in at 9.5 of the permanent workforce.

**AA**: The second thing I want to do is say that, to all our members who
throughout this lockout worked so hard to get the public involved, to get
politicians involved, to created as well incredible imaginative websites,
this is a new modern age labour dispute that our members carried out to
the fullest. Many people had a great time on the line and did some of the
most imaginative and thoughtful things, and it became a work of art, this
labour dispute. I thank that all the people for their support, their
activity, and we couldn't have gotten at the table what we did without
all that help, so I want to thank all of them.

**TM**: Arnold, what city do you live in, out of curiosity?

**AA**: I live right now in Toronto.

**TM**: And when do you think you'll be getting back?

**AA**: Oh, I think I'll be getting back tomorrow some time. I have a religious
holiday on Tuesday, so I'm going to be paying attention to that for once --
it's a burden which has been lifted from our shoulders.

**TM**: I'll bet. And any idea when a ratification vote will happen?

**AA**: We have to develop the language which goes with the principles which
we've developed, and from there we'll be setting our schedule tomorrow
some time.

**TM**: So, do people still remain picketing until the vote has gone through, or
is that still all up in the air?

**AA**: Yes, they continue picketing for a number of reasons. One of them is that
until they're asked to return to work, we're still sort of in this conflict
with the CBC, although it's not real. It's going to be funny to say to them
to relax the picket lines, because in many cases, in many cities, the picket
lines were more like happenings. In Toronto, where I spent some of the time,
because we were negotiating down there for quite a while, the picket line was
basically a series of marching about but there were concerts, there were Yoga
sessions, there were bake-offs, just as there were across the country; but
anyways, we're going to tell them to be even more relaxed picketing over the
next couple of days.

**TM**: Well, I can hear in your voice that you're exhausted, you have a number
of days before you, and I really do appreciate your time Mr. Amber.

**AA**: Thank you very much.

**TM**: Thank you for talking to me.

**AA**: Goodbye.

**TM**: Goodbye.

Note: I cleaned up the interview slightly by removing non-words and mis-spoken words which were immediately corrected, and by correcting some grammar. In Arnold Amber's third paragraph, some of the words and especially names were hard to hear, so I may have gotten them wrong -- I apologize in advance to anyone whose name I transcribed or spelt incorrectly.