Quote from: prezbo on January 22, 2014, 04:57:20 PM

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?