diff --git a/src/shamira/core.py b/src/shamira/core.py
--- a/src/shamira/core.py
+++ b/src/shamira/core.py
@@ -6,6 +6,7 @@ import base64
 import binascii
 
 from . import gf256
+from . import fft
 
 
 class SException(Exception): pass
@@ -15,13 +16,17 @@ class DecodingException(SException): pas
 class MalformedShare(SException): pass
 
 
+def compute_x(n):
+	return fft.precompute_x(fft.ceil_size(n))[:n]
+
+
 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(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
+	# 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)]
+	return fft.evaluate(coefs, n)
 
 
 def generate_raw(secret, k, n):
@@ -31,8 +36,9 @@ def generate_raw(secret, k, n):
 	:param k: number of shares necessary for secret recovery. 1 <= k <= n
 	:param n: (int) number of shares generated. 1 <= n < 255
 	:return: [(i, (bytes) share), ...]"""
+	xs = compute_x(n)
 	shares = [_share_byte(b, k, n) for b in secret]
-	return [(i+1, bytes([s[i] for s in shares])) for i in range(n)]
+	return [(xi, bytes([s[i] for s in shares])) for (i, xi) in enumerate(xs)]
 
 
 def reconstruct_raw(*shares):