# HG changeset patch
# User Laman
# Date 2017-09-23 16:22:59
# Node ID dae5ae50a2cf06cf3a676b98f1b73db237502a4c
# Parent  9c496886dde98a8a7939ae1da8e39bc528fe2e89

linked to finite field arithmetic explanation at wikipedia

diff --git a/src/gf256.py b/src/gf256.py
--- a/src/gf256.py
+++ b/src/gf256.py
@@ -1,16 +1,15 @@
-"""Arithmetic operations on Galois Field 2**8."""
+"""Arithmetic operations on Galois Field 2**8. See https://en.wikipedia.org/wiki/Finite_field_arithmetic"""
 
 
-def _ffmul(a, b):
-	"""Basic multiplication."""
-	r=0
-	while a!=0:
-		if (a&1)!=0: r^=b
-		t=b&0x80
-		b=(b<<1)&255
-		if t!=0: b^=0x1b
-		a>>=1
-	return r
+def _gfmul(a,b):
+	"""Basic multiplication. Russian peasant algorithm."""
+	res=0
+	while a and b:
+		if b&1: res^=a
+		if a&0x80: a=0xff&(a<<1)^0x1b
+		else: a<<=1
+		b>>=1
+	return res
 
 
 g=3 # generator
@@ -20,12 +19,12 @@ acc=1
 for i in range(256):
 	E[i]=acc
 	L[acc]=i
-	acc=_ffmul(acc, g)
+	acc=_gfmul(acc, g)
 L[1]=0
 inv=[E[255-L[i]] if i!=0 else None for i in range(256)] # multiplicative inverse
 
 
-def ffmul(a, b):
+def gfmul(a, b):
 	"""Fast multiplication. Basic multiplication is expensive. a*b==g**(log(a)+log(b))"""
 	if a==0 or b==0: return 0
 	t=L[a]+L[b]
@@ -40,13 +39,15 @@ def evaluate(coefs,x):
 	res=0
 	xK=1
 	for a in coefs:
-		res^=ffmul(a,xK)
-		xK=ffmul(xK,x)
+		res^=gfmul(a,xK)
+		xK=gfmul(xK,x)
 	return res
 
 
 def getConstantCoef(*points):
-	"""Compute constant polynomial coefficient given the points."""
+	"""Compute constant polynomial coefficient given the points.
+
+	See https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing#Computationally_Efficient_Approach"""
 	k=len(points)
 	res=0
 	for i in range(k):
@@ -55,6 +56,6 @@ def getConstantCoef(*points):
 		for j in range(k):
 			if i==j: continue
 			(xj,yj)=points[j]
-			prod=ffmul(prod, (ffmul(xj,inv[xj^x])))
-		res^=ffmul(y,prod)
+			prod=gfmul(prod, (gfmul(xj,inv[xj^x])))
+		res^=gfmul(y,prod)
 	return res