Optimizing multiplication of two polynomials in GF(2^32)
For the time output in main():


Use std::clock_t as opposed to clock_t in C++.
You could have another variable, endTime, for the ending time.
The computed time could also have its own variable, elapsedTime, to be printed.
Only the clock time needs to be cast to a double, not the macro as well.  You should also use static_cast&lt;&gt;() as this is C++.


Example with changes:

std::clock_t startTime = std::clock();

// ...

std::clock_t endTime = std::clock();

double elapsedTime = static_cast&lt;double&gt;(endTime - startTime) / CLOCKS_PER_SEC;

std::cout &lt;&lt; elapsedTime;


But, since you're using C++11, consider utilizing the &lt;chrono&gt; library instead. Unlike &lt;ctime&gt;, it is more C++-oriented but still contains some &lt;ctime&gt; aspects.

Side-notes:


For std::time, 0 can be replaced with nullptr in C++11.
Consider renaming N to something more descriptive.  Using a constant in place of a magic number is nice, but you can increase readability by using a better name.
Since only your test program uses those first four libraries, they should just be in that file.
You don't need those typedefs in your first file; they are already defined in &lt;cstdint&gt;.


Specific questions:


  Currently, I am using many temporary variables. I could try to help the compiler by removing many of them, but this way the code should be more readable and easier for someone to modify.


I would rely on the compiler to handle this, as it should be able to optimize them out.  But you're right; readability and maintainability are also important.  They can always be adjusted accordingly.

You can also maintain these two things by:


avoiding single-character variable names
keeping variables as close in scope as possible


You seem to do well with the second point, but not so much the first.  I've already addressed this in the side-notes, but this is a problem throughout the first file.  By using more descriptive names, it'll be much easier for others to understand your code and make any needed modifications.