[CST-2] Advanced Algorithms - Big number arithmetic

[jarvis_dan]

I was looking through my lecture notes for the big-number arithmetic
section, and I think I can follow as far as converting between
coefficient and point value representations of polynomials via the DFT.
But then my notes say the following after introducing the FFT:

let w=2
	choose modulus M such that w^n = 1 (mod M)
	but no value k can have w^k = 1 (mod M) for k<n
let w^(n/2) = -1 (mod M)
Try M = 2^(n/2) + 1
	_________________
	|___|___|___|___| bits ~ n^2/8
	
	total number of bits here is n/2
	each section has size n/4

So 		_________________
	b	|___|___|___|___|

	total number of bits here is sqrt(b)	
	each section has size sqrt(b)

				 sqrt(b) easy
				  /      /
sqrt(b)*log(sqrt(b))	(+, *, 2^k) mod M
				    /
				  sqrt(b)

...more stuff involving modulus = 2^z + 1

...then the conclusion that M(b) = sqrt(b)*M(sqrt(b)) + blog(b)

Can anybody reply and add some comments to make it make some sense (erm,
e.g. where does b come from), is this supposed to be the final step of
implementing the FFT, if so, what does it mean?

Ta

Dan