diff --git a/readme.md b/readme.md
--- a/readme.md
+++ b/readme.md
@@ -21,22 +21,22 @@ Benchmark results, all values mean _seco
     </tr>
     <tr>
         <td>2 / 3 (a Raspberry Pi 3)</td>
-        <td>8.32e-05</td>
+        <td>6.08e-05</td>
         <td>0.000435</td>
     </tr>
     <tr>
         <td>2 / 3 (a laptop)</td>
-        <td>1.09e-05</td>
+        <td>8.7e-06</td>
         <td>7.17e-05</td>
     </tr>
     <tr>
         <td>254 / 254 (a Raspberry Pi 3)</td>
-        <td>0.414</td>
+        <td>0.226</td>
         <td>0.0314</td>
     </tr>
     <tr>
         <td>254 / 254 (a laptop)</td>
-        <td>0.0435</td>
+        <td>0.0209</td>
         <td>0.00347</td>
     </tr>
 </table>
diff --git a/src/shamira/core.py b/src/shamira/core.py
--- a/src/shamira/core.py
+++ b/src/shamira/core.py
@@ -19,7 +19,7 @@ def _share_byte(secret_b, k, n):
 	if not k<=n<255:
 		raise InvalidParams("Failed k<=n<255, k={0}, n={1}".format(k, n))
 	# we might be concerned with zero coefficients degenerating our polynomial, but there's no reason - we still need k shares to determine it is the case
-	coefs = [int(secret_b)]+[int(b) for b in os.urandom(k-1)]
+	coefs = [int(b) for b in os.urandom(k-1)]+[int(secret_b)]
 	points = [gf256.evaluate(coefs, i) for i in range(1, n+1)]
 	return points
 
diff --git a/src/shamira/gf256.py b/src/shamira/gf256.py
--- a/src/shamira/gf256.py
+++ b/src/shamira/gf256.py
@@ -41,12 +41,13 @@ def gfmul(a, b):
 def evaluate(coefs, x):
 	"""Evaluate polynomial's value at x.
 
-	:param coefs: [a0, a1, ...]."""
+	:param coefs: [an, ..., a1, a0]."""
 	res = 0
-	xk = 1
-	for a in coefs:
-		res ^= gfmul(a, xk)
-		xk = gfmul(xk, x)
+
+	for a in coefs:  # Horner's rule
+		res = gfmul(res, x)
+		res ^= a
+
 	return res
 
 
diff --git a/src/shamira/tests/test_condensed.py b/src/shamira/tests/test_condensed.py
--- a/src/shamira/tests/test_condensed.py
+++ b/src/shamira/tests/test_condensed.py
@@ -52,7 +52,7 @@ class TestCondensed(TestCase):
 		coefs = [random.randint(0, 255) for i in range(k)]
 		points = [(j, evaluate(coefs, j)) for j in range(1, 256)]
 		random.shuffle(points)
-		return (get_constant_coef(*points[:m]), coefs[0])
+		return (get_constant_coef(*points[:m]), coefs[-1])
 
 	def test_generate_reconstruct_raw(self):
 		for (k, n) in [(2, 3), (254, 254)]:
diff --git a/src/shamira/tests/test_gf256.py b/src/shamira/tests/test_gf256.py
--- a/src/shamira/tests/test_gf256.py
+++ b/src/shamira/tests/test_gf256.py
@@ -26,8 +26,8 @@ class TestGF256(TestCase):
 		for x in range(256):
 			(a0, a1, a2, a3) = (x, x>>1, x>>2, x>>3)
 			self.assertEqual(evaluate([17], x), 17)  # constant polynomial
-			self.assertEqual(evaluate([a0, a1, a2, a3], 0), x)  # any polynomial at 0
-			self.assertEqual(evaluate([a0, a1, a2, a3], 1), a0^a1^a2^a3)  # polynomial at 1 == sum of coefficients
+			self.assertEqual(evaluate([a3, a2, a1, a0], 0), x)  # any polynomial at 0
+			self.assertEqual(evaluate([a3, a2, a1, a0], 1), a0^a1^a2^a3)  # polynomial at 1 == sum of coefficients
 
 	def test_get_constant_coef(self):
 		weights = compute_weights((1, 2, 3))
@@ -60,7 +60,7 @@ class TestGF256(TestCase):
 
 		(xs, ys) = zip(*points[:m])
 		weights = compute_weights(xs)
-		return (get_constant_coef(weights, ys), coefs[0])
+		return (get_constant_coef(weights, ys), coefs[-1])
 
 
 if __name__=='__main__':