some FFT Mul questions

as I like programming, and I like math, the mersenne prime search is really interesting for me.
I've implemented my little math lib and I try to improve it, now I'm at the point where I want to optimze my toom-cook mul by the schoenhage–strassen algorithm (I mean, I'll use it for numbers beyond some value), and as a first step I try to grasp the integer multiply (I think the schoenhage–strassen algorithm is just a specialized case of the FFT mul(?)).

so, I've got most of it, but I've some open questions I can't find any answer for (feel free to save your time by just posting related links).

I've implemented my first version based on the summary of this svg:
http://en.wikipedia.org/wiki/File:In...ion_by_FFT.svg

first question is rather to satisfy my theoretical understanding: PowerMod[Length[x], -1, b]; is actually a call to find the multiplicative inverse in the ring of b(337), using the euclid algorithm is the proper way I guess? and if the result is <0, I guess it's correct to bring it within the bounds of the ring, but modulo of something negative is (in this case -42 ->295) will result in -42, is there a proper name for this operation?

2. how to choose b? I found that not all primes >324 work, actually, most don't work, at least the result seem to be wrong. I think my implementation is correct, is it expected that most primes don't work? is there a smarter way than try&error to find working primes?

3. r is 85, as it's the 8th root of unit in 337, but how do I calculate this? atm, I've just a lame loop trying all possible numbers to find the 8th root, is there an algorithm? I can find some info about nth-root calculation and about the root of unity calculation, but the n-th root? (not just for power of 2, or is the NTT transform just working on PO2 sizes, like FFT?)

( 4. the NTT transform in the summary is O(n*n), I shall be able to convert it to a fast O(n*log(n)) version, just like FT->FFT? any concerns?)

5. not really a question, but, if you have any links with good informations on this topic, I'd appreciate if you'd share them with me. I do that all because of my joy of math and I want to fully understand this topic.

[fivemack]

I don't know a name for the operation 'add p until not negative then reduce mod p', but it's the one you need.

To do an NTT on X terms, there has to be an Xth root of unity mod p, which means that (by Lagrange's theorem) p must be ==1 mod X.

To find the Xth root of unity, start with a primitive root mod p, and take the (p-1)/X th power of it ... to check whether some q is a primitive root mod p, check that q^R is not =1 mod p whenever R is a factor of (p-1).

[davieddy]

Originally Posted by fivemack

I don't know a name for the operation 'add p until not negative then reduce mod p', but it's the one you need.

Neither do I, but as many others must do, I find the process very handy in numerous situations.
Anyone care to suggest a name for it?

How about "Division"?

David

[science_man_88]

Originally Posted by fivemack

I don't know a name for the operation 'add p until not negative then reduce mod p', but it's the one you need.

+p*x is what I get from this wording also would p*x reduce to 0*x=0 mod p and hence add nothing to it ?

[jasonp]

I've usually seen it referred to as 'normalization', or 'modular reduction' sometimes. Allowing negative numbers when they aren't strictly necessary, i.e. -p < x < p, is a redundant representation, and removing the redundancy so that -p/2 <= x < p/2 is called balanced representation by Crandall.

[Maximus]

Originally Posted by rapso

3. r is 85, as it's the 8th root of unit in 337, but how do I calculate this? atm, I've just a lame loop trying all possible numbers to find the 8th root, is there an algorithm? I can find some info about nth-root calculation and about the root of unity calculation, but the n-th root?

One way to calculate root of unity is exhaustive search.
Example:
8/2=4.
337=2⁴*21.
Take a number, let it be 2.
Calculate 2^4*21 mod 337 = 1. But must be -1. So 2 is not eligible.
Let take 3.
3^4*21 mod 337 = 336 = -1.
3 is eligible.
Calculate r=3²¹ mod 337 = 252.
So r⁴ mod 337 = 336 = -1. (And r⁸ mod 337 = 1). So r is 8th root of unity in 337.
Other roots of unity are:
r³ mod 337 = 252³ mod 337 = 226;
r⁵ mod 337 = 252⁵ mod 337 = 85;
r⁷ mod 337 = 252⁷ mod 337 = 111.

Originally Posted by rapso

(not just for power of 2, or is the NTT transform just working on PO2 sizes, like FFT?)

Fast NTT like FFT can work not only PO2 size, but on any size. So if size=p1*p2*p3..., then computing complexity of individual iterations is O(p1*p1), O(p2*p2), O(p3*p3), ... So PO2 is preferable.

Originally Posted by rapso

( 4. the NTT transform in the summary is O(n*n), I shall be able to convert it to a fast O(n*log(n)) version, just like FT->FFT? any concerns?)

Fast NTT is similar to FFT, but uses modular arithmetics instead of complex number arithmetics.

[jasonp]

The typical method for calculating a root of unity is to start with numbers modulo p, a prime of the form k*2^n+1 where n is large. Pick a number g < p and then for each unique prime factor q of k*2^n verify that g^((p-1)/q) != 1 mod p. Any g for which you can show this is then a primitive root of order k*2^n, i.e. a root of unity that allows a Fourier-like transform of size k*2^n.

For a transform size smaller than that, say size N, just make g^((p - 1)/N) mod p the root of unity.

For power-of-two sizes a number-theoretic FFT looks a lot like an FFT over the complex numbers, but it doesn't use complex arithmetic. For non-power-of-two sizes I think that it's more complicated, you cannot just take a floating-point FFT and replace the arithmetic operations.

[Maximus]

Originally Posted by Maximus

Calculate 2^4*21 mod 337 = 1. But must be -1. So 2 is not eligible.

Saying more correct, number must not be equal to 1, but needs some additional calculations and longer to explain.

Originally Posted by Maximus

Fast NTT like FFT can work not only PO2 size, but on any size. So if size=p1*p2*p3..., then computing complexity of individual iterations is O(p1*p1), O(p2*p2), O(p3*p3), ... So PO2 is preferable.

I mean one step; one iteration takes O(SIZE*pi) of time.