Most of what I know is from Shamir’s brief description. Other information on the web that I have found about the algorithm is even briefer. For now however, you may find Åsbrink & Brynielsson’s description better.
There are several senses of understanding the algorithm: After I came to think that I could write the program several questions remain which puzzle me:
The scheme to factor n is to solve the equation y2 = z2 (mod n) non trivially. The trivial solutions are where y = z (mod n) or y = −z (mod n). This is why non trivial solutions factor n.
It is easy and sometimes useful when thinking about arithmetic modulo n to imagine that there are only n integers. Such notions confuse the arguments here and confused me for a while. I will use C’s notation “y%n” to denote the positive remainder of dividing y by n. Shamir denotes this by “y (mod n)” but that is at odds with some mathematical conventions that seem to designate an equivalence class by such notation.
We choose a factor base of small primes. Indeed we choose the set of all of the primes less than some number, perhaps a hundred thousand primes each less than several million. We will need to find many numbers yi such that yi2%n is a product of our small primes. If we can find more yi’s than there are members of our factor base then we shall see that we win!
Here is how to find the yi’s.
Here is how we solve y2 = z2 (mod n) by knowing enough yi’s .