1.1 --- a/linearitytest.py	Sun Dec 21 11:13:27 2008 +0000
     1.2 +++ b/linearitytest.py	Mon Dec 22 13:14:38 2008 +0000
     1.3 @@ -1,10 +1,5 @@
     1.4  import random
     1.5  
     1.6 -# NB a linear function is one in which
     1.7 -# f(x) + f(y) = f(x + y)
     1.8 -# An affine one is one in which 
     1.9 -# f(x) + f(y) = f(x + y) + f(0)
    1.10 -
    1.11  class IsNonLinearException(Exception):
    1.12      pass
    1.13  
    1.14 @@ -28,6 +23,14 @@
    1.15                  break
    1.16          return x, vv
    1.17      
    1.18 +    def useValue(x, vv):
    1.19 +        k, v = self.predict(x)
    1.20 +        if k == 0:
    1.21 +            if v != vv:
    1.22 +                raise IsNonLinearException()
    1.23 +        else:
    1.24 +            self._entries.append((k, v ^ vv))
    1.25 +
    1.26      def gotBasis(self):
    1.27          return len(self._entries) == self._bits
    1.28      
    1.29 @@ -51,22 +54,57 @@
    1.30              if random.randrange(2) == 1:
    1.31                  kk ^= k; vv ^= v
    1.32          if self._f(kk) != vv:
    1.33 -            raise isNonLinearException()
    1.34 +            raise IsNonLinearException()
    1.35  
    1.36      def testLinearity(self):
    1.37 -        self.addLinearTerm()
    1.38 +        if len(self._entries) == 0:
    1.39 +            self.addLinearTerm()
    1.40          while not self.gotBasis():
    1.41              self.addLinearTermAndTest()
    1.42          for i in range(self._bits):
    1.43              self.testTerms()           
    1.44  
    1.45 +# NB a linear function is one in which
    1.46 +# f(x) + f(y) = f(x + y)
    1.47 +# An affine one is one in which 
    1.48 +# f(x) + f(y) = f(x + y) + f(0)
    1.49 +
    1.50 +def testLinearity(bits, f):
    1.51 +    # FIXME: adapt to use useValue
    1.52 +    LinearityTester(bits, f).testLinearity()
    1.53 +
    1.54 +class ZeroTester(object):
    1.55 +    def __init__(self, f):
    1.56 +        self._f = f
    1.57 +        self._zeroes = 0
    1.58 +        self._seenOne = False
    1.59 +    
    1.60 +    def __call__(self, x):
    1.61 +        res = self._f(x)
    1.62 +        if not self._seenOne:
    1.63 +            if res != 0:
    1.64 +                self._seenOne = True
    1.65 +            else:
    1.66 +                self._zeroes += 1
    1.67 +                if self._zeroes > 6:
    1.68 +                    raise IsConstantException()
    1.69 +        return res
    1.70 +
    1.71 +def testLinearityOrZero(bits, f):
    1.72 +    testLinearity(bits, ZeroTester(f))
    1.73 +    
    1.74 +def testAffineness(bits, f):
    1.75 +    # FIXME: adapt to use known vals where available    
    1.76 +    x = random.randrange(1<<bits)
    1.77 +    v = f(x)
    1.78 +    testLinearityOrZero(bits, lambda xx: v^f(x^xx))
    1.79 +
    1.80  #def doLinearityTest(f, bits):
    1.81  #    counts = [0, 0]
    1.82  #    for i in 
    1.83  
    1.84  if __name__ == "__main__":
    1.85 -    lt = LinearityTester(20, lambda x: (x ^ (x >>1))&1)
    1.86 -    lt.testLinearity()
    1.87 -    lt = LinearityTester(20, lambda x: (x & (x >>1))&1)
    1.88 -    lt.testLinearity()
    1.89 +    testLinearity(20, lambda x: (x ^ (x >>1))&1)
    1.90 +    testAffineness(20, lambda x: 1^(x ^ (x >>1))&1)
    1.91 +    #testLinearity(20, lambda x: (x & (x >>1))&1)
    1.92