# Public domain.

import sys
import random
import signatures
import doublescalarmult

c = 5
twoc = 2**c
# XXX: tune c and twoc for b

def digits(n):
  result = []
  while n != 0:
    nk = n % twoc
    n /= twoc
    if nk + nk >= twoc:
      nk -= twoc
      n += 1
    result.append(nk)
  return result

def verifybatch(smvector):
  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

  s = [digits(n) for n in scalars]
  words = max([len(d) for d in s])

  needmultiples = [0] * len(scalars)
  for j in range(len(scalars)):
    for i in range(len(s[j])):
      if s[j][i] > needmultiples[j]:
        needmultiples[j] = s[j][i]
      if -s[j][i] > needmultiples[j]:
        needmultiples[j] = -s[j][i]
  needmultiples[0] = 2**c - 1

  multiples = [False,points]
  for i in range(2,2**c):
    newmultiples = [i <= needmultiples[j] and points[j] + multiples[i - 1][j] for j in range(len(points))]
    multiples.append(newmultiples)

  savedsum = dict()

  def precompute(i,left,right):
    if right == left + 1:
      result = signatures.groupelt(0)
      for j in range(left + left + 1,right + right + 1):
        if len(s[j]) > i:
          digit = s[j][i]
          if digit > 0:
            result = result + multiples[digit][j]
          elif digit < 0:
            result = result - multiples[-digit][j]
    else:
      middle = (left + right) / 2
      result = precompute(i,left,middle) + precompute(i,middle,right)
    savedsum[(i,left,right)] = result
    return result

  for i in range(words):
    precompute(i,0,len(smvector))

  def doit(left,right,V):
    scalars[0] = 0
    for i in range(left,right):
      sm = smvector[i]
      R,S,A,M = sm[0],sm[1],sm[2],sm[3]
      scalars[0] = (scalars[0] - S * randomizers[i]) % signatures.l
    s[0] = digits(scalars[0])
    if not V:
      V = signatures.groupelt(0)
      for i in reversed(range(words)):
        for j in range(c):
          V = V + V
        V = V + savedsum[(i,left,right)]
        for j in [0]:
          if len(s[j]) > i:
            digit = s[j][i]
            if digit > 0:
              V = V + multiples[digit][j]
            elif digit < 0:
              V = V - multiples[-digit][j]
    if V.x == 0:
      return [True] * (right - left),V
    if right >= left + 2:
      middle = (left + right) / 2
      leftresults,leftV = doit(left,middle,False)
      rightresults,rightV = doit(middle,right,V - leftV)
      return leftresults + rightresults,V
    return [False],V

  results,V = doit(0,len(smvector),False)
  return results

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