cr50: compress array of prime deltas

The array storing deltas between sequential prime numbers could be
compressed, as the vast majority of the values in the array does not
require more than 4 buts to store.

The new storage format is as follows:

 - each differential value (difference between two consecutive primes)
   is halved and stored in 4 bits, two halved values are packed per
   byte.

 - I the first one of of the two sequential halved values exceeds 0xf,
   it is stored in the array followed by a zero, stored as is (without
   halving), thus taking two bytes.

 - if the second one of the two sequential halved values exceeds 0xf,
   both values are stored in the array as is, both prepended by zeros,
   thus taking 4 bytes.

The code calculating the sequential primes parses the array according
to this format. Storing the primes in this format allows to shave from
the image size 1848 bytes.

BRANCH=cr50
BUG=b:65253310, b:65287300
TEST=verified that test_rsa test from the tpmtest suite passes.

     verified that the list of prime numbers printed out when
     PRINT_PRIMES is defined and test_rsa is ran is the same before
     and after this patch.

Change-Id: Ifdc2858a48f868ef816ccb4e351d9f60703d16e7
Signed-off-by: Vadim Bendebury <vbendeb@chromium.org>
Reviewed-on: https://chromium-review.googlesource.com/664253
Reviewed-by: Nagendra Modadugu <ngm@google.com>
(cherry picked from commit a7d440eaeced82229922ab2fe90f49f4dcf0d242)
Reviewed-on: https://chromium-review.googlesource.com/828418

1 files changed, 225 insertions, 273 deletions

diff --git a/chip/g/dcrypto/bn.c b/chip/g/dcrypto/bn.c
index f03db85c61..5c92f82fda 100644
--- a/chip/g/dcrypto/bn.c
+++ b/chip/g/dcrypto/bn.c
@@ -815,272 +815,208 @@ int bn_modinv_vartime(struct LITE_BIGNUM *dst, const struct LITE_BIGNUM *src,
 	return 1;
 }
 
-#define NUM_PRIMES 4095
 #define PRIME1 3
 
-/* First NUM_PRIMES worth of primes starting with PRIME1.  The entries
- * are a delta / 2 encoding, i.e.:
- *     prime(x) = prime(x - 1) + (PRIME_DELTAS[x] * 2)
+/*
+ * The array below is an encoding of the first 4096 primes, starting with
+ * PRIME1. Using 4096 of the first primes results in at least 5% improvement
+ * in running time over using the first 2048.
+ *
+ * Most byte entries in the array contain two sequential differentials between
+ * two adjacent prime numbers, each differential halved (as the difference is
+ * always even) and packed into 4 bits.
  *
- * Using 4096 of the first primes results in a 5-10% improvement in
- * running time over using the first 2048. */
-const uint8_t PRIME_DELTAS[NUM_PRIMES] = {
-	    0,  1,  1,  2,  1,  2,  1,  2,  3,  1,  3,  2,  1,  2,  3,
-	3,  1,  3,  2,  1,  3,  2,  3,  4,  2,  1,  2,  1,  2,  7,  2,
-	3,  1,  5,  1,  3,  3,  2,  3,  3,  1,  5,  1,  2,  1,  6,  6,
-	2,  1,  2,  3,  1,  5,  3,  3,  3,  1,  3,  2,  1,  5,  7,  2,
-	1,  2,  7,  3,  5,  1,  2,  3,  4,  3,  3,  2,  3,  4,  2,  4,
-	5,  1,  5,  1,  3,  2,  3,  4,  2,  1,  2,  6,  4,  2,  4,  2,
-	3,  6,  1,  9,  3,  5,  3,  3,  1,  3,  5,  3,  3,  1,  3,  3,
-	2,  1,  6,  5,  1,  2,  3,  3,  1,  6,  2,  3,  4,  5,  4,  5,
-	4,  3,  3,  2,  4,  3,  2,  4,  2,  7,  5,  6,  1,  5,  1,  2,
-	1,  5,  7,  2,  1,  2,  7,  2,  1,  2, 10,  2,  4,  5,  4,  2,
-	3,  3,  7,  2,  3,  3,  4,  3,  6,  2,  3,  1,  5,  1,  3,  5,
-	1,  5,  1,  3,  9,  2,  1,  2,  3,  3,  4,  3,  3, 11,  1,  5,
-	4,  5,  3,  3,  4,  6,  2,  3,  3,  1,  3,  6,  5,  9,  1,  2,
-	3,  1,  3,  2,  1,  2,  6,  1,  3, 17,  3,  3,  4,  9,  5,  7,
-	2,  1,  2,  3,  4,  2,  1,  3,  6,  5,  1,  2,  1,  2,  3,  6,
-	6,  4,  6,  3,  2,  3,  4,  2,  4,  2,  7,  2,  3,  1,  2,  3,
-	1,  3,  5, 10,  3,  2,  1, 12,  2,  1,  5,  6,  1,  5,  4,  3,
-	3,  3,  9,  3,  2,  1,  6,  5,  6,  4,  8,  7,  3,  2,  1,  2,
-	1,  5,  6,  3,  3,  9,  1,  8,  1, 11,  3,  4,  3,  2,  1,  2,
-	4,  3,  5,  1,  5,  7,  5,  3,  6,  1,  2,  1,  5,  6,  1,  8,
-	1,  3,  2,  1,  5,  4,  9, 12,  2,  3,  4,  8,  1,  2,  4,  8,
-	1,  2,  4,  3,  3,  2,  6,  1, 11,  3,  1,  3,  2,  3,  7,  3,
-	2,  1,  3,  2,  3,  6,  3,  3,  7,  2,  3,  6,  4,  3,  2, 13,
-	9,  5,  4,  2,  3,  1,  3, 11,  6,  1,  8,  4,  2,  6,  7,  5,
-	1,  2,  4,  3,  3,  2,  1,  2,  3,  4,  2,  1,  3,  5,  1,  5,
-	4,  2,  7,  5,  6,  1,  3,  2,  1,  8,  7,  2,  3,  4,  3,  2,
-	9,  4,  5,  3,  3,  4,  5,  6,  7,  2,  3,  3,  1, 14,  1,  5,
-	4,  2,  7,  2,  4,  6,  3,  6,  2,  3, 10,  5,  1,  8, 13,  2,
-	1,  6,  3,  2,  6,  3,  4,  2,  4, 11,  1,  2,  1,  6, 14,  1,
-	3,  3,  3,  2,  3,  1,  6,  2,  6,  1,  5,  1,  8,  1,  8,  3,
-	10, 8,  4,  2,  1,  2,  1, 11,  4,  6,  3,  5,  1,  2,  3,  1,
-	3,  5,  1,  6,  5,  1,  5,  7,  3,  2,  3,  4,  3,  3,  8,  6,
-	1,  2,  7,  3,  2,  4,  5,  4,  3,  3, 11,  3,  1,  5,  7,  2,
-	3,  9,  1,  5,  7,  2,  1,  5,  7,  2,  4,  9,  2,  3,  1,  2,
-	3,  1,  6,  2, 10, 11,  6,  1,  2,  3,  3,  1,  3, 11,  1,  3,
-	8,  3,  6,  1,  3,  6,  8,  1,  2,  3,  7,  2,  1,  9, 12,  5,
-	3,  1,  5,  1,  5,  1,  5,  3,  1,  5,  1,  5,  3,  4, 15,  5,
-	1,  5,  4,  3,  5,  9,  3,  6,  6,  1,  9,  3,  2,  3,  3,  9,
-	1,  5,  7,  3,  2,  1,  2, 12,  1,  6,  3,  8,  4,  3,  3,  9,
-	8,  1,  2,  3,  1,  3,  3,  5,  3,  6,  6,  9,  1,  3,  2,  9,
-	4, 12,  2,  1,  2,  3,  1,  6,  2,  7, 15,  5,  3,  6,  7,  3,
-	5,  6,  1,  2,  3,  4,  3,  5,  1,  2,  7,  3,  3,  2,  3,  1,
-	5,  1,  8,  6,  4,  9,  2,  3,  6,  1,  3,  3,  3, 14,  3,  7,
-	2,  4,  5,  4,  6,  9,  2,  1,  2, 12,  6,  3,  1,  8,  3,  3,
-	7,  5,  7,  2, 15,  3,  3,  3,  4,  3,  2,  1,  6,  3,  2,  1,
-	3, 11,  3,  1,  2,  9,  1,  2,  6,  1,  3,  2, 13,  3,  3,  2,
-	4,  5, 16,  8,  1,  3,  2,  1,  2,  1,  5,  7,  3,  2,  4,  5,
-	3, 10,  2,  1,  3, 15,  2,  4,  5,  3,  3,  4,  3,  6,  2,  3,
-	1,  3,  2,  3,  1,  5,  1,  8,  3, 10,  2,  6,  7, 14,  3, 10,
-	2,  9,  4,  3,  2,  3,  7,  3,  3,  5,  1,  5,  6,  4,  5,  1,
-	5,  4,  6,  5, 12,  1,  2,  4,  3,  2,  4,  9,  5,  3,  3,  1,
-	3,  5,  6,  1,  5,  3,  3,  3,  4,  3,  5,  3,  1,  3,  3,  3,
-	5,  4, 12,  3, 11,  1,  9,  2,  4,  5, 15,  4,  9,  2,  1,  5,
-	3,  1,  3,  2,  9,  4,  6,  9,  8,  3,  1,  6,  3,  5,  1,  5,
-	1,  3,  5,  7,  2, 12,  1,  8,  1,  5,  1,  5, 10,  2,  1,  2,
-	4,  8,  3,  3,  1,  6,  8,  4,  2,  3, 15,  1,  5,  1,  3,  2,
-	3,  3,  4,  3,  2,  6,  3,  4,  6,  2,  7,  6,  5, 12,  3,  6,
-	3,  1, 11,  4,  9,  5,  3,  7,  2,  1,  3,  5,  4,  3,  2,  3,
-	15, 7,  5,  1,  6,  5,  1,  8,  1,  9, 12,  9,  3,  8,  9,  3,
-	1,  9,  2,  3,  1,  5,  4,  5,  3,  3,  4,  2,  3,  1,  5,  1,
-	6,  2,  3,  3,  1,  6,  2,  7,  9,  2,  3, 10,  2,  4,  3,  2,
-	4,  2,  7,  3,  2,  7,  6,  2,  1, 15,  2, 12,  3,  3,  6,  6,
-	7,  3,  2,  1,  2,  9,  3,  6,  4,  3,  2,  6,  1,  6, 15,  8,
-	1,  3, 11,  7,  3,  5,  6,  3,  1,  2,  4,  5,  3,  3, 12,  7,
-	3,  2,  4,  6,  9,  5,  1,  5,  1,  2,  3, 10,  3,  2,  7,  2,
-	1,  2,  7,  3,  6, 12,  5,  3,  4,  5,  1, 15,  2,  3,  1,  6,
-	2,  7,  3, 17,  6,  4,  3,  5,  1,  2, 10,  5,  4,  8,  1,  5,
-	7,  2,  1,  6,  3,  8,  3,  4,  2,  4,  2,  3,  4,  3,  3,  6,
-	3,  2,  3,  3,  4,  9,  2, 10,  2,  6,  1,  5,  3,  1,  5,  6,
-	1,  2, 10,  3, 15,  3,  2,  4,  5,  6,  3,  1, 14,  1,  3,  2,
-	1,  8,  6,  1,  3,  5,  4, 12,  6,  3,  9,  3,  2,  7,  3,  2,
-	6,  4,  3,  6,  2,  3,  6,  3,  6,  1,  8, 10,  2,  1,  5,  9,
-	4,  2,  7,  2,  1,  3, 11,  3,  7,  3,  3,  5,  3,  1,  5,  1,
-	2,  1, 11,  1,  2,  3,  3,  6,  3,  7,  5,  6,  3,  4,  2, 18,
-	7,  6,  3,  2,  3,  1,  6,  3,  6,  8,  1,  5,  4, 11,  1,  6,
-	3,  2,  3,  9,  1,  6,  3,  2,  6,  4,  3,  6,  2,  3,  6,  3,
-	1,  6,  6,  2,  7,  3,  8,  3,  1,  5,  4,  9,  3, 17,  1, 14,
-	1, 11,  3,  1,  5,  6,  1,  3,  2,  4, 11,  3,  1,  5,  4,  2,
-	3,  4,  2,  6,  9,  6, 10,  2,  3,  3,  4,  2,  1,  8,  6,  1,
-	5,  4,  5,  1,  2,  3,  7,  6, 11,  4, 14,  1,  2, 10,  2,  1,
-	2,  7,  5,  6,  1,  6,  8,  1, 14,  4, 11,  4,  2,  3,  3,  7,
-	2,  4,  6,  3,  3,  2, 10,  2,  9,  1,  6,  3,  2,  3,  7,  9,
-	5,  4,  5, 16,  3,  5,  3,  3,  1,  3,  8,  3,  1,  6,  3, 14,
-	1,  5,  4,  8,  3,  4,  3,  5, 12, 10,  5,  1,  5,  1,  6,  2,
-	3, 10,  2,  1,  6,  9,  5,  1,  5,  1,  2, 10,  8, 13,  2,  4,
-	3,  2,  6,  3,  4,  6,  6,  3,  2,  4, 11,  1,  8,  7,  5,  3,
-	6,  6,  7,  3,  2, 10,  2,  6,  3,  1,  3,  3,  8,  4, 11,  1,
-	14, 4,  3,  2, 10,  2,  6, 12, 10,  2,  4,  5,  1,  8,  1,  6,
-	6, 17,  1,  2,  3,  6,  3,  3,  4,  3,  2,  1,  3, 12,  2, 10,
-	5,  3,  3,  7,  2,  3,  3,  1,  6,  3,  5,  1,  5,  3, 10,  2,
-	13, 2,  1,  3, 11,  1, 12,  2,  3,  1,  2,  3, 12,  3,  4,  2,
-	1, 17,  3,  4,  8,  6,  1,  5,  1,  5,  3,  4,  2,  4,  6, 11,
-	3,  7,  2, 13,  2,  1,  6,  5,  4,  2,  4,  6,  2,  7,  3,  8,
-	3,  4,  2,  3,  3,  4,  3,  5,  6,  1,  3,  3,  8,  4,  3,  3,
-	6,  5,  1,  3,  9,  2,  3,  3,  3,  6,  9,  4,  3,  5,  4,  9,
-	2,  7,  3,  9,  5,  4,  5,  6,  1,  3,  6,  6, 18,  2,  3,  4,
-	2,  3,  1,  2,  9,  6,  3,  4,  3,  3,  2,  9,  1,  2,  1, 12,
-	2,  3,  3,  7, 15,  3,  2,  3,  6,  3, 10,  2,  4,  2,  4,  3,
-	3,  2, 15,  1,  5,  6,  4,  5,  4, 12,  3,  6,  2,  7,  2,  3,
-	1, 14,  7,  8,  1,  6,  3,  2, 10,  5,  3,  3,  3,  4,  5,  6,
-	7,  5,  7,  8,  7,  5,  7,  3,  8,  3,  4,  3,  8, 10,  5,  1,
-	3,  2,  1,  2,  6,  1,  5,  1,  3, 11,  3,  1,  2,  9,  4,  5,
-	4, 11,  1,  5,  9,  7,  2,  1,  2,  9,  1,  2,  3,  4,  5,  1,
-	15, 2, 15,  1,  5,  1,  9,  2,  9,  3,  7,  5,  1,  2, 10, 18,
-	3,  2,  3,  7,  2, 10,  5,  7, 11,  3,  1, 15,  6,  5,  9,  1,
-	2,  7,  3, 11,  9,  1,  6,  3,  2,  4,  2,  4,  3,  5,  1,  6,
-	9,  5,  7,  8,  7,  2,  3,  3,  1,  3,  2,  1, 14,  1, 14,  3,
-	1,  2,  3,  7,  2,  6,  7,  8,  7,  2,  3,  4,  3,  2,  3,  3,
-	3,  4,  2,  4,  2,  7,  8,  4,  3,  2,  6,  4,  8,  1,  5,  4,
-	2,  3, 13,  3,  5,  4,  2,  3,  6,  7, 15,  2,  7, 11,  4,  6,
-	2,  3,  4,  5,  3,  7,  5,  3,  1,  5,  6,  6,  7,  3,  3,  9,
-	5,  3,  4,  9,  2,  3,  1,  3,  5,  1,  5,  4,  3,  3,  5,  1,
-	9,  5,  1,  6,  2,  3,  4,  5,  6,  7,  6,  2,  4,  5,  3,  3,
-	10, 2,  7,  8,  7,  5,  4,  5,  6,  1,  9,  3,  6,  5,  6,  1,
-	2,  1,  6,  3,  2,  4,  2, 22,  2,  1,  2,  1,  5,  6,  3,  3,
-	7,  2,  3,  3,  3,  4,  3, 18,  9,  2,  3,  1,  6,  3,  3,  3,
-	2,  7, 11,  6,  1,  9,  5,  3, 13, 12,  2,  1,  2,  1,  2,  7,
-	2,  3,  3,  4,  8,  6,  1, 21,  2,  1,  2, 12,  3,  3,  1,  9,
-	2,  7,  3, 14,  9,  7,  3,  5,  6,  1,  3,  6, 15,  3,  2,  3,
-	3,  7,  2,  1, 12,  2,  3,  3, 13,  5,  9,  3,  4,  3,  3, 15,
-	2,  6,  6,  1,  8,  1,  3,  2,  6,  9,  1,  3,  2, 13,  6,  3,
-	6,  2, 12, 12,  6,  3,  1,  6, 14,  4,  2,  3,  6,  1,  9,  3,
-	2,  3,  3, 10,  8,  1,  3,  3,  9,  5,  3,  1,  2,  4,  3,  3,
-	12, 8,  3,  4,  5,  3,  7, 11,  4,  8,  3,  1,  6,  2,  1, 11,
-	4,  9, 17,  1,  3,  9,  2,  3,  3,  4,  5,  4,  9,  3,  2,  1,
-	2,  4,  8,  1,  6,  6,  3,  9,  2,  3,  3,  3,  1,  3,  6,  5,
-	10, 6,  9,  2,  3,  1,  8,  1,  5,  7,  2, 15,  1,  5,  6,  1,
-	12, 3,  8,  4,  5,  1,  6, 11,  3,  1,  8, 10,  5,  1,  6,  6,
-	9,  5,  6,  3,  1,  5,  1,  3,  5,  9,  1,  6,  3,  2,  3,  1,
-	12, 14, 1,  2,  1,  5,  1,  8,  6,  4, 11,  1,  3,  2,  1,  5,
-	3,  10, 6,  5,  4,  6,  3,  3,  3,  2,  9,  1,  2,  6,  9,  1,
-	6,  3,  2,  1,  8,  6,  6,  7,  2,  4,  9,  2,  6,  7,  3,  3,
-	2,  4,  3,  2, 10,  6,  5,  7,  2,  1,  8,  1,  6, 15,  2,  3,
-	12, 10, 12, 5,  4,  6,  5,  6,  3,  6,  6,  3,  4,  8,  7,  3,
-	2,  3, 18, 10,  5, 15,  6,  1,  2,  1, 14,  6,  7,  3, 11,  4,
-	2,  9,  3,  7,  9,  2,  3,  1,  3, 17,  9,  1,  8,  3,  9,  1,
-	12, 2,  1,  3,  6,  3,  6,  5,  4,  3,  8,  6,  4,  5,  7, 20,
-	3,  1,  3,  2,  6,  7,  2,  1,  2,  1,  2,  4,  3,  5,  3,  3,
-	1,  3,  3,  3,  6,  3, 12,  5,  1,  5,  3,  6,  3,  3,  7,  3,
-	3, 26, 10,  3,  5,  1,  5,  4,  5,  6,  6,  1,  3,  2,  7,  8,
-	4,  6,  3, 11,  1,  5,  4,  3, 11,  1, 11,  3,  4,  5,  6,  6,
-	1,  5,  3,  6,  1,  2,  7,  5,  1,  3,  9,  2,  6,  4,  9,  6,
-	3,  3,  2,  3,  3,  7,  2,  1,  6,  6,  2,  3,  9,  9,  6,  1,
-	8,  6,  4,  9,  5, 13,  2,  3,  4,  3,  3,  2,  1,  5, 10,  2,
-	3,  4,  2, 10,  5,  1, 17,  1,  2, 12,  1,  6,  6,  5,  3,  1,
-	6, 15,  3,  6,  8,  6,  1, 11,  9,  6,  7,  5,  1,  6,  6,  2,
-	1,  2,  3,  6,  1,  8,  9,  1, 20,  4,  8,  3,  4,  5,  1,  2,
-	9,  4,  5,  4,  6,  2,  9,  1,  9,  5,  1,  2,  1,  2,  4, 14,
-	1,  3, 11,  6,  3,  7,  9,  2,  3,  4,  3,  3,  5,  4,  2,  1,
-	9,  5,  3, 10, 11,  4,  3, 15,  2,  1,  2,  9,  3, 15,  1,  2,
-	4,  3,  2,  3,  6,  7, 17,  7,  3,  2,  1,  3,  2,  7,  2,  1,
-	3, 14,  1,  2,  3,  4,  5,  1,  5,  1,  5,  1,  2, 15,  1,  6,
-	6,  5,  9,  6,  7,  5,  1,  6,  3,  5,  3,  7,  6,  2,  7,  2,
-	9,  1,  5,  4,  2,  4,  5,  6,  9,  9,  4,  3,  9,  8,  7,  3,
-	3,  5,  7,  2,  3,  1,  6,  6,  2,  3,  3,  6,  1,  8,  1,  6,
-	3,  2,  7,  3,  2,  1,  6,  9,  2, 18,  9,  6,  6,  1,  2,  1,
-	2,  4,  6,  2, 18,  3,  9,  1,  6,  5,  3,  6, 12,  4,  3,  3,
-	8,  6,  1,  9,  5, 10,  5,  1,  3,  9,  2,  1, 20,  3,  1,  8,
-	1,  2,  4,  9,  5,  6,  3,  1,  5,  4,  2,  3,  6,  1,  5,  9,
-	4,  3,  2, 10,  2,  3, 18,  3,  1,  5,  3, 12,  3,  7,  8,  3,
-	9,  1,  5, 10,  5,  4,  3,  2,  3,  1,  5,  1,  6,  2,  1,  2,
-	4,  5,  3,  6,  9,  7,  6,  8,  4,  3,  8,  4,  2,  1,  3,  9,
-	12, 9,  5,  6,  1,  2,  7,  5,  3,  3,  3,  9,  6,  1, 14,  9,
-	7,  8,  6,  7, 12,  6, 11,  3,  1,  5,  4,  2,  1,  2,  7,  6,
-	3,  2,  3,  7,  2,  1,  2, 15,  3,  1,  3,  5,  1, 15, 11,  1,
-	2,  3,  4,  3,  3,  8,  6,  6,  3,  4,  2,  1, 12,  6,  2,  3,
-	4,  3,  3,  5,  1,  3,  6, 14,  7,  3,  2,  6,  4,  3,  6,  2,
-	3,  7,  3,  6,  5,  3,  3,  4,  3,  3,  2,  1,  2,  4,  6,  2,
-	7,  9,  5,  1,  8,  3, 10,  3,  5,  4,  2, 15, 18,  6,  4, 11,
-	6,  1,  3,  6,  8,  3,  3,  1,  9,  2, 13,  2,  4,  9,  5,  4,
-	5,  3,  7,  2, 10, 11,  9,  6,  4, 14,  6,  3,  3,  4,  3,  6,
-	12, 8,  7,  2,  7,  6,  3,  5,  6, 10,  3,  2,  4,  9,  6,  9,
-	5,  1,  2, 10,  5,  7,  2,  3,  1,  5, 12,  9,  1,  2, 10,  8,
-	7,  5,  7,  3,  2,  3, 10,  3,  5,  3,  1,  6,  3, 15,  5,  4,
-	3,  2,  3,  4, 20,  1,  2,  1,  6,  9,  2,  3,  4,  5,  3,  9,
-	9,  1,  6,  8,  4,  3,  2,  3,  3,  1, 26,  7,  2, 10,  8,  1,
-	2,  3,  6,  1,  3,  6,  6,  3,  2,  7,  5,  3,  3,  7,  5,  7,
-	8,  4,  3,  6,  2,  4, 11,  3,  1,  9, 11,  3,  1,  9,  3,  8,
-	7,  5,  3,  6,  1,  3,  2,  4,  9,  6,  8,  1,  2,  7,  2,  4,
-	6,  6, 15,  8,  4,  2,  1,  3, 11,  6,  4,  5,  3,  3,  3,  7,
-	3,  9,  5,  6,  1,  5,  1,  2, 13,  2,  6,  4,  2,  9,  4,  5,
-	7,  8,  3,  3,  4,  5,  3,  4,  3,  6,  5, 10,  5,  4,  2,  6,
-	13, 9,  2,  6,  9,  3, 15,  3,  4,  3, 11,  6,  1,  2,  3,  3,
-	1,  5,  1,  2,  3,  3,  1,  3, 11,  9,  3,  9,  6,  4,  6,  3,
-	5,  6,  1,  8,  1,  5,  1,  5,  9,  3, 10,  2,  1,  3, 11,  3,
-	3,  9,  3,  7,  6,  8,  1,  3,  3,  2,  7,  6,  2,  1,  9,  8,
-	18, 6,  3,  7, 14,  1,  6,  3,  6,  3,  2,  1,  8, 15,  4, 12,
-	3, 15,  5,  1,  9,  2,  3,  6,  4, 11,  1,  3, 11,  9,  1,  5,
-	1,  5, 15,  1, 14,  3,  7,  8,  3, 10,  8,  1,  3,  2, 16,  2,
-	1,  2,  3,  1,  6,  2,  3,  3,  6,  1,  3,  2,  3,  4,  3,  2,
-	10, 2, 16,  5,  4,  8,  1, 11,  1,  2,  3,  4,  3,  8,  7,  2,
-	9,  4,  2, 10,  3,  6,  6,  3,  5,  1,  5,  1,  6, 14,  6,  9,
-	1,  9,  5,  4,  5, 24,  1,  2,  3,  4,  5,  1,  5, 15,  1, 18,
-	3,  5,  3,  1,  9,  2,  3,  4,  8,  7,  8,  3,  7,  2, 10,  2,
-	3,  1,  5,  6,  1,  3,  6,  3,  3,  2,  6,  1,  3,  2,  6,  3,
-	4,  2,  1,  3,  9,  5,  3,  4,  6,  3, 11,  1,  3,  6,  9,  2,
-	7,  3,  2, 10,  3,  8,  4,  2,  4, 11,  4,  6,  3,  3,  8,  6,
-	9, 15,  4,  2,  1,  2,  3, 13,  2,  7, 12, 11,  3,  1,  3,  5,
-	3,  7,  3,  3,  6,  5,  3,  1,  6,  5,  6,  4,  9,  9,  5,  3,
-	4,  8,  3,  3,  4,  8, 10,  2,  1,  5,  1,  5,  6,  3,  4,  3,
-	5, 10,  5,  9, 13,  2,  3, 15,  1,  2,  4,  3,  6,  6,  9,  2,
-	4, 11,  3,  1,  6, 17,  3,  9,  6,  3,  1, 14,  7,  8,  7,  2,
-	7,  6,  2,  3,  3,  1, 18,  2,  3, 10,  6, 12,  3, 11,  1,  8,
-	9,  6,  6,  9,  1,  3,  3,  3,  2,  3,  7,  2,  1, 11,  4,  6,
-	3,  5,  3,  4,  6,  9,  6,  3,  5,  1, 11,  7,  3,  3,  2,  9,
-	3, 10, 11,  1,  6, 12,  2,  9,  9,  1, 11,  1,  2,  6,  4,  6,
-	5,  7,  2,  1,  9,  8, 19,  3,  3,  3,  6,  5,  3,  6,  4,  3,
-	2,  3,  7, 15,  3,  5,  4, 11,  3,  4,  6,  5,  1,  5,  1,  3,
-	5,  1,  5,  6,  9, 10,  3,  2,  4, 11,  3,  3, 15,  3,  7,  3,
-	6,  6,  3,  5,  1,  5, 15,  1,  8,  4,  2,  1,  3,  9,  2,  1,
-	3,  2, 13,  2,  4,  3,  5,  1,  2,  3,  4,  2,  3, 15,  6,  1,
-	3,  3,  2, 10, 11,  4,  2,  1,  2, 36,  4,  2,  4, 11,  1,  2,
-	7,  5,  1,  2, 10,  3,  5,  9,  3, 10,  8,  3,  4,  3,  2, 10,
-	6, 11,  1,  2,  1,  6,  5,  9,  1, 11,  3,  9, 15,  1,  5,  7,
-	5,  4,  8, 25,  3,  5,  4,  5,  6,  3,  9,  1, 11,  3,  1,  2,
-	3,  4,  3,  3,  5,  9,  1, 11,  1,  8,  7,  5,  3,  1,  6,  5,
-	10, 2,  7,  3,  2, 18,  1,  2,  3,  6,  1,  2,  7,  6,  3,  2,
-	3,  1,  3,  2, 10,  5,  1,  5,  3,  6,  1, 12,  6,  6,  3,  3,
-	2, 12,  1,  2, 12,  1,  3,  2,  3,  4,  8,  3,  1,  5,  6,  7,
-	3, 17,  3,  7,  3,  2,  1, 15, 11,  4,  2,  3,  4,  2,  1, 14,
-	1,  3,  2, 13,  9, 11,  1,  3,  8,  3,  1,  8,  6,  1,  6,  2,
-	3,  3,  7,  5,  3,  4,  6,  2,  9,  1,  5,  4,  8,  3,  3, 15,
-	1,  5,  9,  1,  5,  4,  2,  4,  6, 12, 20,  1,  6,  5,  3,  6,
-	1,  6,  2,  1,  2,  3,  9,  7,  6,  3,  2,  7, 15,  2,  4,  5,
-	4,  3,  5,  9,  4,  2,  7,  8,  3,  4,  2,  3,  1,  5,  1,  6,
-	2,  1,  2,  3,  4,  2,  3, 16, 12,  5,  4,  9,  5,  1,  3,  5,
-	1,  2,  9,  3,  6,  1,  8,  1, 11,  3,  3,  4,  9,  2,  9,  6,
-	4,  3,  2, 10,  3, 15, 11,  6,  1,  3,  9,  2, 31,  2,  1,  6,
-	3,  5,  1,  6,  6, 14,  1,  2,  7, 11,  3,  1,  3,  3,  5,  7,
-	2,  1,  5,  3,  4,  5,  7,  5,  3,  1,  6, 11,  9,  4,  5,  9,
-	6,  1,  6,  2,  6,  1,  5,  1,  3,  9,  3,  3, 17,  3,  1,  6,
-	2,  3,  9,  9,  1,  8,  3,  3,  4,  3,  5,  9,  4,  5,  4,  5,
-	1,  2,  9, 13,  6, 11,  1,  2,  1, 11,  3,  3,  7,  8,  3, 10,
-	5,  6,  1,  9, 21,  2, 12,  1,  3,  5,  6,  1,  3,  5,  4,  2,
-	3,  6,  6,  4,  2,  3,  6, 15, 10,  3, 12,  3,  5,  6,  1,  5,
-	10, 3,  3,  2,  6,  7,  5,  9,  6,  4,  3,  6,  2,  7,  5,  1,
-	6, 15,  8,  1,  6,  3,  2,  1,  2,  3, 13,  2,  9,  1,  2,  3,
-	7, 27,  3, 26,  1,  8,  3,  3,  6, 13,  2,  1,  3, 11,  3,  1,
-	6,  6,  3,  5,  9,  1,  6,  6,  5,  9,  6,  3,  4,  3,  5,  3,
-	4,  2,  1,  2, 10, 12,  3,  3,  5,  7,  5,  1, 11,  3,  7,  5,
-	13, 2,  9,  4,  6,  6,  5,  6,  3,  4,  8,  3,  4,  3,  3, 11,
-	1,  5, 10,  5,  3, 22,  9,  3,  5,  1,  2,  3,  7,  2, 13,  2,
-	1,  6,  5,  4,  2,  4,  6,  2,  6,  4, 11,  4,  3,  5,  9,  3,
-	3,  4,  3,  6,  2,  4,  9,  5,  6,  3,  6,  1,  3,  2,  1,  8,
-	6,  6,  7,  5,  7,  3,  5,  6,  1,  6,  3,  2,  3,  1,  6,  2,
-	13, 3,  9,  3,  5,  3,  1,  9,  5,  4,  2, 13,  5, 10,  3,  8,
-	10, 6,  5,  4,  5,  1,  8,  3, 10,  5, 10,  2, 15,  1,  2,  4,
-	8,  1,  9,  2,  1,  3,  5,  9,  6,  7,  9,  3,  8, 10,  3,  2,
-	4,  3,  2,  3,  6,  4,  5,  1,  6,  3,  2,  1,  3,  5,  1,  8,
-	6,  7,  5,  3,  4,  3, 14,  1,  3,  9, 15, 17,  1,  8,  6,  1,
-	9,  8,  3,  4,  5,  4,  5,  4,  5, 22,  3,  3,  2, 10,  2,  1,
-	2,  7, 14,  4,  3,  8,  7, 15,  3, 15,  2,  7,  5,  3,  3,  4,
-	2,  9,  6,  3,  1, 11,  6,  4,  3,  6,  2,  7,  2,  3,  1,  2,
-	9, 10,  3,  8, 19,  8,  1,  2,  3,  1, 20, 21,  7,  2,  3,  1,
-	12, 5,  3,  1,  9,  5,  6,  1,  8,  1,  3,  8,  3,  4,  2,  1,
-	5,  3,  4,  5,  1,  9,  8,  4,  6,  9,  6,  3,  6,  5,  3,  3
+ * If a halved differential value exceeds 0xf (and as such does not fit into 4
+ * bits), a zero is placed in the array followed by the value literal (no
+ * halving).
+ *
+ * If out of two consecutive differencials only the second one exceeds 0xf,
+ * the first one still is put into the array in its own byte prepended by a
+ * zero.
+ */
+const uint8_t PRIME_DELTAS[] = {
+	  1,  18,  18,  18,  49,  50,  18,  51,  19,  33,  50,  52,
+	 33,  33,  39,  35,  21,  19,  50,  51,  21,  18,  22,  98,
+	 18,  49,  83,  51,  19,  33,  87,  33,  39,  53,  18,  52,
+	 51,  35,  66,  69,  21,  19,  35,  66,  18, 100,  36,  35,
+	 97, 147,  83,  49,  53,  51,  19,  50,  22,  81,  35,  49,
+	 98,  52,  84,  84,  51,  36,  50,  66, 117,  97,  81,  33,
+	 87,  33,  39,  33,  42,  36,  84,  35,  55,  35,  52,  54,
+	 35,  21,  19,  81,  81,  57,  33,  35,  52,  51, 177,  84,
+	 83,  52,  98,  51,  19, 101, 145,  35,  19,  33,  38,  19,
+	  0,  34,  51,  73,  87,  33,  35,  66,  19, 101,  18,  18,
+	 54, 100,  99,  35,  66,  66, 114,  49,  35,  19,  90,  50,
+	 28,  33,  86,  21,  67,  51, 147,  33, 101, 100, 135,  50,
+	 18,  21,  99,  57,  24,  27,  52,  50,  18,  67,  81,  87,
+	 83,  97,  33,  86,  24,  19,  33,  84, 156,  35,  72,  18,
+	 72,  18,  67,  50,  97, 179,  19,  35, 115,  33,  50,  54,
+	 51, 114,  54,  67,  45, 149,  66,  49,  59,  97, 132,  38,
+	117,  18,  67,  50,  18,  52,  33,  53,  21,  66, 117,  97,
+	 50,  24, 114,  52,  50, 148,  83,  52,  86, 114,  51,  30,
+	 21,  66, 114,  70,  54,  35, 165,  24, 210,  22,  50,  99,
+	 66,  75,  18,  22, 225,  51,  50,  49,  98,  97,  81, 129,
+	131, 168,  66,  18,  27,  70,  53,  18,  49,  53,  22,  81,
+	 87,  50,  52,  51, 134,  18, 115,  36,  84,  51, 179,  21,
+	114,  57,  21, 114,  21, 114,  73,  35,  18,  49,  98, 171,
+	 97,  35,  49,  59,  19, 131,  97,  54, 129,  35, 114,  25,
+	197,  49,  81,  81,  83,  21,  21,  52, 245,  21,  67,  89,
+	 54,  97, 147,  35,  57,  21, 115,  33,  44,  22,  56,  67,
+	 57, 129,  35,  19,  53,  54, 105,  19,  41,  76,  33,  35,
+	 22,  39, 245,  54, 115,  86,  18,  52,  53,  18, 115,  50,
+	 49,  81, 134,  73,  35,  97,  51,  62,  55,  36,  84, 105,
+	 33,  44,  99,  24,  51, 117, 114, 243,  51,  67,  33,  99,
+	 33,  59,  49,  41,  18,  97,  50, 211,  50,  69,   0,  32,
+	129,  50,  18,  21, 115,  36,  83, 162,  19, 242,  69,  51,
+	 67,  98,  49,  50,  49,  81, 131, 162, 103, 227, 162, 148,
+	 50,  55,  51,  81,  86,  69,  21,  70,  92,  18,  67,  36,
+	149,  51,  19,  86,  21,  51,  52,  53,  49,  51,  53,  76,
+	 59,  25,  36,  95,  73,  33,  83,  19,  41,  70, 152,  49,
+	 99,  81,  81,  53, 114, 193, 129,  81,  90,  33,  36, 131,
+	 49, 104,  66,  63,  21,  19,  35,  52,  50,  99,  70,  39,
+	101, 195,  99,  27,  73,  83, 114,  19,  84,  50,  63, 117,
+	 22,  81, 129, 156, 147, 137,  49, 146,  49,  84,  83,  52,
+	 35,  21,  22,  35,  49,  98, 121,  35, 162,  67,  36,  39,
+	 50, 118,  33, 242, 195,  54, 103,  50,  18, 147, 100,  50,
+	 97, 111, 129,  59, 115,  86,  49,  36,  83,  60, 115,  36,
+	105,  81,  81,  35, 163,  39,  33,  39,  54, 197,  52,  81,
+	242,  49,  98, 115,   0,  34, 100,  53,  18, 165,  72,  21,
+	114,  22,  56,  52,  36,  35,  67,  54,  50,  51,  73,  42,
+	 38,  21,  49,  86,  18, 163, 243,  36,  86,  49, 225,  50,
+	 24,  97,  53,  76,  99, 147,  39,  50, 100,  54,  35,  99,
+	 97, 138,  33,  89,  66, 114,  19, 179, 115,  53,  49,  81,
+	 33, 177,  35,  54,  55,  86,  52,   0,   4,   0,  36, 118,
+	 50,  49,  99, 104,  21,  75,  22,  50,  57,  22,  50, 100,
+	 54,  35,  99,  22,  98, 115, 131,  21,  73,   0,   6,   0,
+	 34,  30,  27,  49,  86,  19,  36, 179,  21,  66,  52,  38,
+	150, 162,  51,  66,  24,  97,  84,  81,  35, 118, 180, 225,
+	 42,  33,  39,  86,  22, 129, 228, 180,  35,  55,  36,  99,
+	 50, 162, 145,  99,  35, 121,  84,   0,  10,   0,  32,  53,
+	 51,  19, 131,  22,  62,  21,  72,  52,  53, 202,  81,  81,
+	 98,  58,  33, 105,  81,  81,  42, 141,  36,  50,  99,  70,
+	 99,  36, 177, 135,  83, 102, 115,  42,  38,  49,  51, 132,
+	177, 228,  50, 162, 108, 162,  69,  24,  22,   0,  12,   0,
+	 34,  18,  54,  51,  67,  33,  60,  42,  83,  55,  35,  49,
+	 99,  81,  83, 162, 210,  19, 177, 194,  49,  35, 195,  66,
+	  0,   2,   0,  34,  52, 134,  21,  21,  52,  36, 107,  55,
+	 45,  33, 101,  66,  70,  39,  56,  52,  35,  52,  53,  97,
+	 51, 132,  51, 101,  19, 146,  51,  54, 148,  53,  73,  39,
+	 57,  84,  86,  19, 102,   0,  36,  35,  66,  49,  41,  99,
+	 67,  50, 145,  33, 194,  51, 127,  50,  54,  58,  36,  36,
+	 51,  47,  21, 100,  84, 195,  98, 114,  49, 231, 129,  99,
+	 42,  83,  51,  69, 103,  87, 135,  87,  56,  52,  56, 165,
+	 19,  33,  38,  21,  19, 179,  18, 148,  84, 177,  89, 114,
+	 18, 145,  35,  69,  31,  47,  21,  25,  41,  55,  81,  42,
+	  0,  36,  50,  55,  42,  87, 179,  31, 101, 145,  39,  59,
+	145,  99,  36,  36,  53,  22, 149, 120, 114,  51,  19,  33,
+	225, 227,  18,  55,  38, 120, 114,  52,  50,  51,  52,  36,
+	 39, 132,  50, 100, 129,  84,  35, 211,  84,  35, 103, 242,
+	123,  70,  35,  69,  55,  83,  21, 102, 115,  57,  83,  73,
+	 35,  19,  81,  84,  51,  81, 149,  22,  35,  69, 103,  98,
+	 69,  51, 162, 120, 117,  69,  97, 147, 101,  97,  33,  99,
+	 36,   0,   4,   0,  44,  33,  33,  86,  51, 114,  51,  52,
+	  0,   6,   0,  36, 146,  49,  99,  51,  39, 182,  25,  83,
+	220,  33,  33,  39,  35,  52, 134,   0,   2,   0,  42,  33,
+	 44,  51,  25,  39,  62, 151,  53,  97,  54, 243,  35,  55,
+	 33, 194,  51, 213, 147,  67,  63,  38,  97, 129,  50, 105,
+	 19,  45,  99,  98, 204,  99,  22, 228,  35,  97, 147,  35,
+	 58, 129,  51, 149,  49,  36,  51, 200,  52,  83, 123,  72,
+	 49,  98,  27,  73,   0,  34,  19, 146,  51,  69,  73,  50,
+	 18,  72,  22,  99, 146,  51,  49,  54,  90, 105,  35,  24,
+	 21, 114, 241,  86,  28,  56,  69,  22, 179,  24, 165,  22,
+	105,  86,  49,  81,  53, 145,  99,  35,  28, 225,  33,  81,
+	134,  75,  19,  33,  83, 166,  84,  99,  51,  41,  18, 105,
+	 22,  50,  24, 102, 114,  73,  38, 115,  50,  67,  42, 101,
+	114,  24,  22, 242,  60, 172,  84, 101,  99, 102,  52, 135,
+	 50,   0,   6,   0,  36, 165, 246,  18,  30, 103,  59,  66,
+	147, 121,  35,  19,   0,  34, 145, 131, 145, 194,  19,  99,
+	101,  67, 134,  69,   0,  14,   0,  40,  49,  50, 103,  33,
+	 33,  36,  53,  51,  19,  51,  99, 197,  21,  54,  51, 115,
+	  0,   6,   0,  52, 163,  81,  84,  86,  97,  50, 120,  70,
+	 59,  21,  67, 177, 179,  69, 102,  21,  54,  18, 117,  19,
+	146, 100, 150,  51,  35,  55,  33, 102,  35, 153,  97, 134,
+	 73,  93,  35,  67,  50,  21, 162,  52,  42,  81,   0,  34,
+	 18, 193, 102,  83,  22, 243, 104,  97, 185, 103,  81, 102,
+	 33,  35,  97, 137,   0,   2,   0,  40,  72,  52,  81,  41,
+	 69,  70,  41,  25,  81,  33,  36, 225,  59,  99, 121,  35,
+	 67,  53,  66,  25,  83, 171,  67, 242,  18, 147, 241,  36,
+	 50,  54,   0,  14,   0,  34, 115,  33,  50, 114,  19, 225,
+	 35,  69,  21,  21,  18, 241, 102,  89, 103,  81,  99,  83,
+	118,  39,  41,  21,  66,  69, 105, 148,  57, 135,  51,  87,
+	 35,  22,  98,  51,  97, 129,  99,  39,  50,  22, 146,   0,
+	 36, 150,  97,  33,  36,  98,   0,  36,  57,  22,  83, 108,
+	 67,  56,  97, 149, 165,  19, 146,   0,   2,   0,  40,  49,
+	129,  36, 149,  99,  21,  66,  54,  21, 148,  50, 162,   0,
+	  6,   0,  36,  49,  83, 195, 120,  57,  21, 165,  67,  35,
+	 21,  22,  33,  36,  83, 105, 118, 132,  56,  66,  19, 156,
+	149,  97,  39,  83,  51, 150,  30, 151, 134, 124, 107,  49,
+	 84,  33,  39,  99,  35, 114,  18, 243,  19,  81, 251,  18,
+	 52,  51, 134,  99,  66,  28,  98,  52,  51,  81,  54, 231,
+	 50, 100,  54,  35, 115, 101,  51,  67,  50,  18,  70,  39,
+	149,  24,  58,  53,  66,   0,  30,   0,  36, 100, 182,  19,
+	104,  51,  25,  45,  36, 149,  69,  55,  42, 185, 100, 230,
+	 51,  67, 108, 135,  39,  99,  86, 163,  36, 150, 149,  18,
+	165, 114,  49,  92, 145,  42, 135,  87,  50,  58,  53,  49,
+	 99, 245,  67,  35,   0,   8,   0,  40,  18,  22, 146,  52,
+	 83, 153,  22, 132,  50,  51,   0,   2,   0,  52, 114, 168,
+	 18,  54,  19, 102,  50, 117,  51, 117, 120,  67,  98,  75,
+	 49, 155,  49, 147, 135,  83,  97,  50,  73, 104,  18, 114,
+	 70, 111, 132,  33,  59, 100,  83,  51, 115, 149,  97,  81,
+	 45,  38,  66, 148,  87, 131,  52,  83,  67, 101, 165,  66,
+	109, 146, 105,  63,  52,  59,  97,  35,  49,  81,  35,  49,
+	 59, 147, 150,  70,  53,  97, 129,  81,  89,  58,  33,  59,
+	 51, 147, 118, 129,  51,  39,  98,  25,   0,  16,   0,  36,
+	 99, 126,  22,  54,  50,  24, 244, 195, 245,  25,  35, 100,
+	177,  59, 145,  81,  95,  30,  55, 131, 168,  19,   0,   4,
+	  0,  32,  33,  35,  22,  35,  54,  19,  35,  67,  42,   0,
+	  4,   0,  32,  84, 129, 177,  35,  67, 135,  41,  66, 163,
+	102,  53,  21,  22, 230, 145, 149,  69,   0,  48,  18,  52,
+	 81,  95,   0,   2,   0,  36,  53,  49, 146,  52, 135, 131,
+	114, 162,  49,  86,  19,  99,  50,  97,  50,  99,  66,  19,
+	149,  52,  99, 177,  54, 146, 115,  42,  56,  66,  75,  70,
+	 51, 134, 159,  66,  18,  61,  39, 203,  49,  53,  55,  51,
+	101,  49, 101, 100, 153,  83,  72,  51,  72, 162,  21,  21,
+	 99,  67,  90,  89, 210,  63,  18,  67, 102, 146,  75,  49,
+	  0,  12,   0,  34,  57,  99,  30, 120, 114, 118,  35,  49,
+	  0,  36,  35, 166, 195, 177, 137, 102, 145,  51,  50,  55,
+	 33, 180,  99,  83,  70, 150,  53,  27, 115,  50, 147, 171,
+	 22, 194, 153,  27,  18, 100, 101, 114,  25,   0,  16,   0,
+	 38,  51,  54,  83, 100,  50,  55, 243,  84, 179,  70,  81,
+	 81,  53,  21, 105, 163,  36, 179,  63,  55,  54,  99,  81,
+	 95,  24,  66,  19, 146,  19,  45,  36,  53,  18,  52,  35,
+	246,  19,  50, 171,  66,  18,   0,  72,  66,  75,  18, 117,
+	 18, 163,  89,  58, 131,  67,  42, 107,  18,  22,  89,  27,
+	 57, 241,  87,  84,   0,  16,   0,  50,  53,  69,  99, 145,
+	179,  18,  52,  51,  89,  27,  24, 117,  49, 101, 162, 115,
+	  0,   4,   0,  36,  18,  54,  18, 118,  50,  49,  50, 165,
+	 21,  54,  28, 102,  51,  44,  18, 193,  50,  52, 131,  21,
+	103,   0,   6,   0,  34,  55,  50,  31, 180,  35,  66,  30,
+	 19,  45, 155,  19, 131,  24,  97,  98,  51, 117,  52,  98,
+	145,  84, 131,  63,  21, 145,  84,  36, 108,   0,  40,  22,
+	 83,  97,  98,  18,  57, 118,  50, 127,  36,  84,  53, 148,
+	 39, 131,  66,  49,  81,  98,  18,  52,  35,   0,  32, 197,
+	 73,  81,  53,  18, 147,  97, 129, 179,  52, 146, 150,  67,
+	 42,  63, 182,  19, 146,   0,  62,  33,  99,  81, 102, 225,
+	 39, 179,  19,  53, 114,  21,  52,  87,  83,  22, 185,  69,
+	150,  22,  38,  21,  19, 147,   0,   6,   0,  34,  49,  98,
+	 57, 145, 131,  52,  53, 148,  84,  81,  41, 214, 177,  33,
+	179,  55, 131, 165,  97,   0,  18,   0,  42,  44,  19,  86,
+	 19,  84,  35, 102,  66,  54, 250,  60,  53,  97,  90,  51,
+	 38, 117, 150,  67,  98, 117,  22, 248,  22,  50,  18,  61,
+	 41,  18,  55,   0,  54,   0,   6,   0,  52,  24,  51, 109,
+	 33,  59,  49, 102,  53, 145, 102,  89,  99,  67,  83,  66,
+	 18, 172,  51,  87,  81, 179, 117, 210, 148, 102,  86,  52,
+	131,  67,  59,  21, 165,   0,   6,   0,  44, 147,  81,  35,
+	114, 210,  22,  84,  36,  98, 100, 180,  53, 147,  52,  54,
+	 36, 149,  99,  97,  50,  24, 102, 117, 115,  86,  22,  50,
+	 49,  98, 211, 147,  83,  25,  84,  45,  90,  56, 166,  84,
+	 81, 131, 165, 162, 241,  36, 129, 146,  19,  89, 103, 147,
+	138,  50,  67,  35, 100,  81,  99,  33,  53,  24, 103,  83,
+	 67, 225,  57,   0,  30,   0,  34,  24,  97, 152,  52,  84,
+	 84,   0,  10,   0,  44,  51,  42,  33,  39, 228,  56, 127,
+	 63,  39,  83,  52,  41,  99,  27, 100,  54,  39,  35,  18,
+	154,  56,   0,  38, 129,  35,   0,   2,   0,  40,   0,  42,
+	114,  49, 197,  49, 149,  97, 129,  56,  52,  33,  83,  69,
+	 25, 132, 105,  99, 101,  51,
 };
 
 static uint32_t bn_mod_word16(const struct LITE_BIGNUM *p, uint16_t word)
@@ -1253,18 +1189,34 @@ int DCRYPTO_bn_generate_prime(struct LITE_BIGNUM *p)
 
 	/* Save on trial division by marking known composites. */
 	bn_init(&composites, composites_buf, sizeof(composites_buf));
-	for (i = 0; i < sizeof(PRIME_DELTAS) / sizeof(PRIME_DELTAS[0]); i++) {
+	for (i = 0; i < ARRAY_SIZE(PRIME_DELTAS); i++) {
 		uint16_t rem;
+		uint8_t unpacked_deltas[2];
+		uint8_t packed_deltas = PRIME_DELTAS[i];
+		int k;
+		int m;
+
+		if (packed_deltas) {
+			unpacked_deltas[0] = (packed_deltas >> 4) << 1;
+			unpacked_deltas[1] = (packed_deltas & 0xf) << 1;
+			m = 2;
+		} else {
+			i += 1;
+			unpacked_deltas[0] = PRIME_DELTAS[i];
+			m = 1;
+		}
 
-		prime += (PRIME_DELTAS[i] << 1);
-		print_primes(prime);
-		rem = bn_mod_word16(p, prime);
-		/* Skip marking odd offsets (i.e. even candidates). */
-		for (j = (rem == 0) ? 0 : prime - rem;
-		     j < bn_bits(&composites) << 1;
-		     j += prime) {
-			if ((j & 1) == 0)
-				bn_set_bit(&composites, j >> 1);
+		for (k = 0; k < m; k++) {
+			prime += unpacked_deltas[k];
+			print_primes(prime);
+			rem = bn_mod_word16(p, prime);
+			/* Skip marking odd offsets (i.e. even candidates). */
+			for (j = (rem == 0) ? 0 : prime - rem;
+			     j < bn_bits(&composites) << 1;
+			     j += prime) {
+				if ((j & 1) == 0)
+					bn_set_bit(&composites, j >> 1);
+			}
 		}
 	}