Clarification on multiplication from modular exponentiation precompiled contract

Question

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?

Answer 1

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).