Circular convolution of binary vectors (mod 2) using NTT

Let x, y be vectors of length n, with entries either 1 or 0. I want to efficiently compute the circular convolution

(x * y) mod 2

Where each component of the result is taken mod 2.

I know how to do it using a Fast Fourier Transform (multiply Fourier transforms of x and y. transform back. Do the "mod 2") However, this uses floating point calculations to solve a discrete problem and for large n (I'm interested in n ~ 10^7) it might lead to rounding errors. I expect there is a better way to do this using the number theoretic transform (NTT) but unfortunately I'm not familiar with number theory or NTT.

I looked at this website. Following the procedure there,

1. let's say n = 10^7. I need
2. a modulus M (use 10^7).
3. a prime N=kn+1 for some k. (use N = 3 * 10^7 + 1)
4. a root ω≡g^k mod N , where g is a generator (e.g. ω=2744)
5. Do the transform, etc.

Question

This seems promising. However, I would need 32-bit integers to store each bit during this calculation? Also, this is not making use of the fact that I only need results modulo 2. Is there a way to make use of this to simplify the procedure? Since I don't know the number theory, this is not obvious to me.

I'm not asking for a full solution, only for an argument if my "mod 2" significantly simplifies the implementation (both in terms of difficulty to implement the necessary algorithms as well as computational resources).

Another question: If it's not possible to simplify using "mod 2", do you think it would still pay off to use NTT, as opposed to just throwing a well-known FFT library at the floating point problem?

For the NTT, your procedure looks correct. Yes, you would need 32-bit integers for each bit in your original vector. Unfortunately, there's not a lot you can do there to make use of the fact that the end result is mod 2, since you need a root of order 10^7. You may be able to shrink that number by a couple factors of two (and doing the standard DFT for a few base levels of recursion), but it wouldn't change much, relatively speaking.

Note, for your FFT implementation, I believe you could use integer arithmetic since its mod 2, but I'm not convinced it would be at all efficient. See this math stackexchange answer for details.