# Public domain.

import sys
import heapq
import random
import signatures
import doublescalarmult

def multiscalarmult(scalars,points):
  x = zip([-n for n in scalars],points)
  heapq.heapify(x)
  while len(x) > 1:
    np1 = heapq.heappop(x)
    np2 = heapq.heappop(x)
    n1,p1 = -np1[0],np1[1]
    n2,p2 = -np2[0],np2[1]
    p2 += p1
    n1 -= n2
    if n1 > 0: heapq.heappush(x,(-n1,p1))
    heapq.heappush(x,(-n2,p2))
  np1 = heapq.heappop(x)
  n1,p1 = -np1[0],np1[1]
  return p1 * n1

def verifybatch(smvector):
  results = []
  randomizers = [random.randrange(2**signatures.b) for i in range(len(smvector))]

  points = [signatures.B]
  scalars = [0]
  for i in range(len(smvector)):
    sm = smvector[i]
    R,S,A,M = sm[0],sm[1],sm[2],sm[3]
    h = signatures.inthash(str(R) + str(A) + M)
    points.append(signatures.groupelt(R))
    scalars.append(randomizers[i])
    points.append(signatures.groupelt(A))
    scalars.append((h * randomizers[i]) % signatures.l)
    scalars[0] = (scalars[0] - S * randomizers[i]) % signatures.l

  if multiscalarmult(scalars,points).x == 0:
    return [True] * len(smvector)

  for sm in smvector:
    R,S,A,M = sm[0],sm[1],sm[2],sm[3]
    h = signatures.inthash(str(R) + str(A) + M)
    checkR = doublescalarmult.doublescalarmult(S,signatures.B,(-h) % signatures.l,signatures.groupelt(A))
    results.append(R == checkR.x)
  return results

signatures.benchmark(verifybatch,int(sys.argv[1]))