# Public domain. import signatures maxmult = 15 # XXX: tune maxmult for b def morebitsclear(u,v): if u == 0 and v == 0: return False while u & 1 == 0 and v & 1 == 0: u /= 2 v /= 2 if u & 1: return False return True def bottom(m): result = 0 for i in range(maxmult + 1): if i & 1: if morebitsclear(m - i,m - result): result = i if morebitsclear(m + i,m - result): result = -i return result def doublescalarmultwithprecomp(m,Pmults,n,Qmults): if m == 0 and n == 0: return signatures.groupelt(0) if m & 1 == 0 and n & 1 == 0: d = doublescalarmultwithprecomp(m / 2,Pmults,n / 2,Qmults) return d + d mbottom = bottom(m) nbottom = bottom(n) d = doublescalarmultwithprecomp(m - mbottom,Pmults,n - nbottom,Qmults) # XXX: eliminate additions of 0 if mbottom > 0: d = d + Pmults[mbottom] if mbottom < 0: d = d - Pmults[-mbottom] if nbottom > 0: d = d + Qmults[nbottom] if nbottom < 0: d = d - Qmults[-nbottom] return d def precomp(P): result = [] PP = P + P for i in range(maxmult + 1): if i == 0: result.append(signatures.groupelt(0)) elif i == 1: result.append(P) elif i == 2: result.append(PP) elif i & 1: result.append(PP + result[i - 2]) else: result.append(False) return result def doublescalarmult(m,P,n,Q): return doublescalarmultwithprecomp(m,precomp(P),n,precomp(Q))