# 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): 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]) result = signatures.groupelt(0) for i in reversed(range(words)): for j in range(c): result = result + result result = result + savedsum[(i,left,right)] for j in [0]: 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] if result.x == 0: return [True] * (right - left) if right >= left + 2: middle = (left + right) / 2 return doit(left,middle) + doit(middle,right) return [False] return doit(0,len(smvector)) signatures.benchmark(verifybatch,int(sys.argv[1]))