See equation 3 of the naive algoritm, because the curve point multiplication with base point P is done only once per batch of signatures it offers at least about 2x the speedup in any case.
They have a problem that the signature is (r, s) which is 2 integers (mod p).
You need to verify
sum(R) = sum(u * G) + sum(v * Q)
or
sum(R) = sum(u) * G + sum(v * Q)
The problem is that you don't have R. The parameter r is the x-coord of R.
R means y^2 = r^3 + a*r + b mod p
That gives you 2 y's for each r value.
They suggest trying all permutations.
If you do a batch of 4, that gives 16 attempts to find R.
sum(u) * G => 3 integer adds and a point multiply
sum(v * Q) => 4 point multiplies and 3 point adds
Each R guess requires 3 point adds and 8 on average means 24 point adds.
It also requires a square root step.
Total
5 point multiplies
27 point adds
Normal:
8 point multiplies
1 point add
The batch method has 3 fewer multiplies but 19 more adds.
What is the relative time for adds and multiplies?
