addchain_lengths.py

import subprocess
import Crypto.Random.random as rand

"""
# This file executes experiments to get average addchain lengths

# prerequisite: 
# in the same directory as this python file:
sudo apt-get install golang-go
git clone https://github.com/kwantam/addchain
cd addchain
go build
cd ..

# run an experiment for the parameters at the bottom of this file:
python3 thisfile.py

"""

# flip this flag to 1 to print lots of info
verbose = 0



def addchain_length(bigint):
    # execute the kwantam/addchain code on a given integer
    outstr = subprocess.run(['./addchain/addchain', str(bigint)], capture_output=True, text=True).stdout
    # get number of squarings and non-squarings by counting "sqr" and "*"
    numdbl = outstr.count("sqr")
    numadd = outstr.count("*")
    # strip the output to get shortest addchain
    val = int(outstr.split(':')[-1].split('(')[0].strip())
    method = outstr.split('#')[-1].split(":")[0].strip()
    return val,method,numadd,numdbl


# call addchain_length() on random integers, accumulating statistics
def addchain_length_range(bitlength,numiters):
  # for bitlength=256 and numiters=1000, and ended up with min,max: 297 315
  # for bitlength=128 and numiters=1000, and ended up with min,max: 144 161

  # variables to maintain min and max addchain length
  min_ = 100000000    # big enough so that it is bigger than any addchain length
  max_ = 0

  for i in range(numiters):
    # get random intger of around bitlength
    bigint = rand.getrandbits(bitlength)

    # get addchain length
    val,method,numadd,numdbl = addchain_length(bigint)
    print("iter:",i, "  addchain length:", val, "  min,max:",min_,max_, "  numadd numdbl ratiosqr:",numadd,numdbl,numdbl/val, "  winning method:",method)

    # update new min or max
    if val<min_:
      min_=val
      print("new min")
    if val>max_:
      max_=val
      print("new max")

      

# This algorithm is described in Peter de Rooij, Efficient exponentiation using precomputation and vector addition chains, in Eurocrypt ’94 [28] (1995), 389–399.
# But some people attribute it to Bos and Coster
def bos_coster_multiexponentiation_addition_chain(scalars):

  # flag to allow a scaling factor in each addition, which can be handled more efficiently with a separate addition chain
  scaling_flag = 1

  # enumerate the scalars
  scalars_ = [[scalar,i] for i,scalar in enumerate(scalars)]

  # loop accumulating an addition chain
  addchain=[]
  while 1:

    # sort scalars
    scalars_=sorted(scalars_, key=lambda x: x[0], reverse=True)
    if verbose:
      print(scalars_)

    # done if only largest is nonzero
    if scalars_[1][0]==0:
      break

    # subtract second largest from largest, append this to the addchain possibly with scaling
    if scaling_flag:
      addchain.append([scalars_[0][1],scalars_[1][1],scalars_[0][0]//scalars_[1][0]])
      scalars_[0][0] = scalars_[0][0] - scalars_[1][0]*(scalars_[0][0]//scalars_[1][0])
    else:
      addchain.append([scalars_[0][1],scalars_[1][1],1])
      scalars_[0][0] = scalars_[0][0] - scalars_[1][0]

    if verbose:
      print(addchain[-1])
      print(scalars_[0][0])
      print("___")

  if verbose:
    print("DONE")
    print(addchain)
    print()
    print(len(addchain))

  # if there are also scalings, then get the number of adds for the scalings
  num_scaling_adds = 0
  num_scaling_dbls = 0
  for add in addchain:
    if add[2]>1:
      num_adds,method,numadd,numdbl = addchain_length(add[2])
      num_scaling_adds += numadd
      num_scaling_dbls += numdbl
      if verbose:
        print(add[2],end=" ")

  print("len_addchain,num_scaling_adds,num_scaling_dbls",len(addchain)+num_scaling_adds+num_scaling_dbls,num_scaling_adds,num_scaling_dbls)
  return addchain, len(addchain)+num_scaling_adds+num_scaling_dbls, num_scaling_adds, num_scaling_dbls


# loop over bos_coster_multiexponentiation_addition_chain() on random inputs, accumulating statistics
def bos_coster_multiexponentiation_addition_chain_length_range(bitlength,num_scalars,numiters):

  # variables to maintain min and max addchain length
  min_total = 100000000    # big enough so that it is bigger than any addchain length
  max_total = 0
  min_dbls = 100000000    # big enough so that it is bigger than any addchain length
  max_dbls = 0

  for i in range(numiters):
    # generate random array of scalar, and enumerate them
    scalars = [rand.getrandbits(bitlength) for i in range(num_scalars)]

    # compute addchain
    addchain,len_total,num_scaling_adds,num_scaling_dbls = bos_coster_multiexponentiation_addition_chain(scalars)
    print("iter:",i, "  total len:", len_total, "  total min,max:",min_total,max_total, "  dblslen min,max",min_dbls,max_dbls, "  ratio:",num_scaling_dbls/len_total)

    # update new min or max
    if len_total<min_total:
      min_total=len_total
      print("new min")
    if len_total>max_total:
      max_total=len_total
      print("new max")

    # update new min or max
    if num_scaling_dbls<min_dbls:
      min_dbls=num_scaling_dbls
      print("new min")
    if num_scaling_dbls>max_dbls:
      max_dbls=num_scaling_dbls
      print("new max")


if __name__=="__main__":

  # set parameters
  num_scalars = 1
  bitlength = 256
  numiters = 1000

  if num_scalars==1:
    addchain_length_range(bitlength,numiters)
  else:
    bos_coster_multiexponentiation_addition_chain_length_range(bitlength,num_scalars,numiters)