Optimization of the non native arithmetics for pseudo-Mersenne primes.

[DDT92]

For pseudo-Mersenne primes, i.e., primes of the form p = 2^n - c with c negligible compared to 2^n, we have that, for any decomposition x = x_hi * 2^n + x_lo, then x is equivalent to x_hi * c + x_lo modulo p. Note that we do not need that the decomposition is "normal", i.e. x_lo < 2^n, so it works for a NonNativeFieldMulResultGadget, which has oversized limbs.

We can save many constraints in the following parts of the computation:

• allocation of k in the reduce function, due to the fact that x_hi * c + x_lo is much smaller than x;
• product k * p, which requires - since k fits in a limb- num_limbs linear constraints and not anymore num_limbs^2.
• group_and_check_equality: we have less groups.
  I would expect 40% less constraints for multiplication + reduction.

It would be more natural to remove the distinction between NonNativeFieldGadget and NonNativeFieldMulResult, as suggested by @UlrichHaboeck75 in his issue about refactoring non-native field gadgets, before implementing the pseudo-Mersenne reduction.
It would be better also to move to a representation of the non native gadget as a pair (limbs, limbs_max) instead of (limbs,num_adds) which we have now, as explained in my comment to @UlrichHaboeck75 issue.

For more details look at our google doc.