What Maths is Required for Writing a Quadratic or Number Sieve?

[Zurtex]

I was looking at writing a quadratic or a number sieve over the summer to factor numbers. What areas of maths do I need to know to be able to do this please?

 

[Hurkyl]

The theory behind the quadratic sieve is BY FAR the easiest to understand -- a bright high schooler should be able to understand it.

The theory behind the number field sieve requires a good bit of algebraic number theory if you want to understand all of the details. (I.E. I don't! ) The basic idea doesn't require much abstract algebra, the devil is in the details. However, you need to know even less to implement the sieve -- the messy stuff is needed for setting up the sieve, and for getting from the outputs to the factors.


The quadratic sieve is superior to the number field sieve except on extraordinarily large numbers.


Im summary, I strongly suggest doing the quadratic sieve.

By the way, you might want to write one of the lower powered factoring methods first: say, pollard rho, or the elliptic curve method if you know anything on the topic. They're superior to the quadratic sieve on smaller numbers, and may prove useful when optimizing your quadratic sieve, in case you need to factor something.


(I guess there's something called the "Square form method" or something like that, which is especially good at factoring things that fit into a single machine word -- I'm not sure if that is supposed to be a 32-bit word or a 64-bit word)

 

[Zurtex]

Thanks, I'll get some books out on the subjects you've mentioned. I was looking at eventually factoring numbers with prime factors greater than 35 digits.

 

[shmoe]

Definitely much less background is needed for the quadratic sieve than the number field sieve. Nothing too fancy is needed, modular arithmetic and quadratic residues (in any elementary number theory text if you're not familiar), and a little linear algebra should suffice.

 

[neurocomp2003]

i assume that you understand a lot of programming...if not you got to learn some.
parallel and memory manipulations would be some topics. There's an ebook i have but i can't remember the book name..its something liek "cryptography in C++"

I highly recommend the book by neal koblitz...it was recommended by a prof to me i browsed through it but haven't the $$ to pick it up.
its called "cryptography and number theory" or vice versa

 

[Hurkyl]

Well, yes. If you want to write a good quadratic sieve, you'll need two things:

(1) You'll have to implement fancy optimizations that are based on theory (such as the multiple polynomial QS, and the large and small prime variants)

(2) You'll have to understand some things about how your computer works, and how to optimize to take advantage of that. (and how not to be wasteful!)

For example, I factored a decent sized number (can't remember how big) in 20-something minutes with my first quadratic sieve. A friend of mine factored the same number in about two seconds with his sieve. :tongue:

I played around with a particular optimization on the sieving step (cache-blocking), and it was something like a factor of 6 speed up to do exactly the same operations, just done in a more efficient order.

 

[mathwonk]

my friend carl pomerance is an expert on the quadratic sieve. why not ask him your question?

carlp@bell-labs.com

 

[Zurtex]

Thanks for all your help. I don't know a lot about programming but I've always been very quick to learn any language I've ever come across. I also don't know a lot about the subject area, but this I've found to be the best way to learn for me, just to throw myself straight into a subject.

I've not yet decided which programming language I want to write it in. I've not touched C++ yet, so perhaps I'll go with that as we are supposed to learn it next semester anyway. Also thanks for the processor bit, I’m buying myself a new computer soon and I was looking at buying AMDs new dual core processor the Athlon 64 X2, so I'll see what whizzy things that can do.