-
Notifications
You must be signed in to change notification settings - Fork 295
Description
Hey Dmitry,
I have some troubles convincing myself that the modL
function won't suffer from overflows. If you have any references to a more detailed description of modL that would be really helpful! In particular I am concerned with its use here:
Line 788 in 1b61c87
modL(sm.subarray(32), x); |
Two arrays h and d get multiplied to produce x.
Both h and d are Uint8Array(64)
with elements at most 8 bits each and only the first 32 elements non-zero, both elements were reduced mod L
.
The resulting x is of type Float64Array(64)
.
I believe, that the number of bits in each element of the array x is maxed at the following values:
[16, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 19, 19, 19, 19, 18, 18, 17, 16, 0]
, i.e. the bit length |x[0]| <= 16
, |x[1]| <= 17
, etc.
Now, the modL function is called on x. And in this line
Line 729 in 1b61c87
x[j] += carry - 16 * x[i] * L[j - (i - 32)]; |
|x[j]| > 32
, since |16 * x[i] * L[j - (i - 32)]| <= 4 + 21 + 8 = 33
.But during the bit operation on the next line:
Line 730 in 1b61c87
carry = (x[j] + 128) >> 8; |
(x[j] + 128)
will get converted to a 32-bits signed integer (according to https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators, Section Bitwise shift operators). This will act as expected only if the length of the number being shifted is at most 32 bits, but why now will it be the case?