2

I'm trying to understand what exactly Vitalik means in the following (from here):

Note that adding precompiles for addition and subtraction is not required, as the in-EVM algorithm is efficient enough, and multiplication can be done through this precompile via a * b = ((a + b)**2 - (a - b)**2) / 4.

My understanding is that this is a more efficient way of performing the multiplication, but what exactly is to be passed to the modexp contract in order to achieve multiplication? is it the squaring of (a+b) and (a-b)? And in that case, what should be passed as the modulus value?

2

but what exactly is to be passed to the modexp contract in order to achieve multiplication? is it the squaring of (a+b) and (a-b)?

Yes, exactly that.

To calculate a * b % m you call the precompile once to calculate (a+b)^2 % m and once more to calculate (a-b)^2 % m, then take the difference (adding m if necessary to keep everything positive). This gives you 4 * a * b % m.

To get finally to a * b % m, we need to divide by 4, modulo m. The "proper" way to do this is to find the multiplicative inverse of 4 with respect to m and multiply through by that. This is a bit trickier and it's only possible to do this when m is odd (i.e. co-prime to 4). [But see note at the end]

Example, show that 4 * 5 % 7 = 6

(4 + 5)^2 % 7 = 4
(4 - 5)^2 % 7 = 1
4 - 1 = 3

So we have (4 * (4 * 5)) % 7 = 3. Modulo 7, 2 is an inverse of 4 (since (2 * 4) % 7 = 1). Therefore, multiplying through by two gives finally (4 * 5) % 7 = 6, QED.

And in that case, what should be passed as the modulus value.

The same m as you would have passed in to calculate (a * b) % m.


Note

To divide by four using the normal modular approach as above, we need to multiply through by the inverse of 4 with respect to the modulus, m. This would give us a recursive problem: to do a multiplication would require that we could do a multiplication.

However, I think there is a short-cut that can be used to divide by 4 modulo m. We divide twice by 2 modulo m.

  • If n is even (and less than m), then n / 2 % m is just n / 2 - i.e. shift one bit right.

  • If n is odd, n / 2 % m can be found simply by calculating (n + m) / 2 not modulo (add n and m and shift right one bit).

So, in the example above 3 / 4 % 7 is found as follows:

(3 + 7) / 2 = 5
(5 + 7) / 2 = 6

This is the same as we got before by multiplying through by the inverse of 4 with respect to 7 (which is 2).

  • Awesome! Thank you for this. Where I was going wrong was I was not getting the multiplicative inverse. Perhaps I should request that the document be updated with this information? – riordant Aug 14 '17 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.