ida-genfield.py

#!/usr/bin/env python
#
# This script requires a recent version of python that supports long
# integers (i.e. arbitrary precision integers)

inv = []

# Also see ida.C
field = 65537

def bitrev (v):
    t = v & 1;
    while v:
        t = t << 1
        v = v >> 1
        t = t | (v & 1)
    return t

# Fast modular exponentiation
def expmod (b, e, n):
    a = 1L
    e = bitrev (e)
    while e > 0:
        a = (a * a) % n
        if (e & 1): a = (a * b) % n
        e = e >> 1
    return a

# Main program
import sys

fh = file ("ida-field.C", "w")
fh.write ("/* This file is autogenerated by %s. DO NOT EDIT! */\n" % sys.argv[0])
fh.write ("static const u_long invtable[] = { 0,\n")

buf = "\t"
for x in xrange(1,field):
    # Fermat's little theorem for inverses
    y = expmod (x, field - 2, field)
    assert (((x*y) % field) == 1)
    buf = buf + ("%d, " % y)
    if (len(buf) > 60):
        fh.write (buf)
        fh.write ("\n\t")
        buf = ""
        
fh.write (buf)
fh.write ("0\n};\n")
fh.write ("const u_long * const Ida::inv = (u_long *) &invtable;\n")

fh.close ()