Rewrite 5x52 normalize method to be faster #24

No description provided.

Nice, this gives an actual measurable speedup for verification a few %.

I'm convinced that it's correct, but it took me a while. Some comments could help (which is equally true for the previous implementation, though...).

In the first block, you reduce a2^256 + b to a \ 0x1000003D1 + b, with b < 2^256. That results in at most 2^256 + (<2^64).

In the second block, you set x to (n >= 2^256 - 0x1000003D1), add x * 0x1000003D1, know that it overflows if x == 1, and remove 2^256 by masking t4. You could add an assert (x == t4 >> 48) before the masking, I think, as the adding of 0x1000003D1 and subtraction of 2^256 should always happen both or neither.

Yes, I think you described it pretty well! I've squashed in some comments now, and added a couple of asserts as suggested.

ACK