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