What maths is required for ?

  • Thread starter Zurtex
  • Start date

Zurtex

Science Advisor
Homework Helper
1,120
1
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

Staff Emeritus
Science Advisor
Gold Member
14,847
17
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! :biggrin:) 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. :smile:

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

Science Advisor
Homework Helper
1,120
1
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

Science Advisor
Homework Helper
1,992
1
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.
 
i assume that you understand alot of programming...if not you gotta 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

Staff Emeritus
Science Advisor
Gold Member
14,847
17
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.
 
Last edited:

mathwonk

Science Advisor
Homework Helper
10,688
870
my friend carl pomerance is an expert on the quadratic sieve. why not ask him your question?

carlp@bell-labs.com
 

Zurtex

Science Advisor
Homework Helper
1,120
1
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 in to 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.
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top