How to Build a Signed All Bits Set Comb

Or Putting a Clichéd Interview Question to Work

The Basic Problem

A set of signed-all-bits-set combs for a point B on an elliptic curve (or any group) is a group of data tables. There are 3 parameters: n combs with t teeth and s bits of separation between teeth. As a concrete example, we will consider n = 4, t = 5, and s = 13. We need to build 4 tables that look like this:

index	contents
0	B ⋅ 2⁵² − B ⋅ 2³⁹ − B ⋅ 2²⁶ − B ⋅ 2¹³ − B ⋅ 2⁰
1	B ⋅ 2⁵² − B ⋅ 2³⁹ − B ⋅ 2²⁶ − B ⋅ 2¹³ + B ⋅ 2⁰
2	B ⋅ 2⁵² − B ⋅ 2³⁹ − B ⋅ 2²⁶ + B ⋅ 2¹³ − B ⋅ 2⁰
3	B ⋅ 2⁵² − B ⋅ 2³⁹ − B ⋅ 2²⁶ + B ⋅ 2¹³ + B ⋅ 2⁰
…	…
15	B ⋅ 2⁵² + B ⋅ 2³⁹ + B ⋅ 2²⁶ + B ⋅ 2¹³ + B ⋅ 2⁰

The other 3 tables look the same, but they start at B ⋅ 2⁶⁵, B ⋅ 2¹³⁰, and B ⋅ 2¹⁹⁵

We only need 16 entries in the table rather than 32, because we can negate. If the high bit is 1, we don’t negate. If it is 0, we invert the lower 4 bits of the table index, and then negate the point. This in effect only negates the highest bit.

Start By Repeatedly Doubling

Here is the algorithm for the first step, as pseudocode. There are some shortcuts you can take with this algorithm, but I have left them out for simplicity.

teeth_sets = Array<Point>[4][4]
everything_points = Array<Point>[4](IdentityPoint)

accumulator = B
for (i = 0 to 259)
    if (i % s == 0)
        everything_points[i / (t * s)] *= accumulator
    elif (i % s == 1)
        teeth_number = (i / s) % t
        if (teeth_number != t - 1)
            teeth_sets[i / (t * s)][teeth_number] = accumulator
    accumulator = accumulator * 2

At the end of the loop, we have for each comb the entry with all bits set to positive, and each tooth squared. The squared teeth are important for building out the other 15 entries that go into the table.

Fun with Gray Codes

A Gray Code for n bits is a cyclical arrangement of all n bit strings so that each string differs from its two neighbors by exactly 1 bit. It generally refers to specific such code, call the Reflected Binary Code. We will use the 4-bit gray-code. See Wikipedia for more on Gray Codes

By taking the everything point, and adding or subtracting teeth, we can flip a specific bit in our signed representation. Let’s give an example. The first everything point is B ⋅ 2⁵² + B ⋅ 2³⁹ + B ⋅ 2²⁶ + B ⋅ 2¹³ + B ⋅ 2⁰. The first tooth we saved is B ⋅ 2¹ if we subtract this tooth, we get B ⋅ 2⁵² + B ⋅ 2³⁹ + B ⋅ 2²⁶ + B ⋅ 2¹³ + B ⋅ 2⁰ − B ⋅ 2¹ = B ⋅ 2⁵² + B ⋅ 2³⁹ + B ⋅ 2²⁶ + B ⋅ 2¹³ − B ⋅ 2⁰.

By remembering which direction we need to flip and walking a gray code, we can generate all the entries in each comb.

Putting a Stupid Interview Problem to Work

There’s a programming interview problem floating around the internet that goes something like this:
Given an array of numbers, for each entry, find the product of all other entries. There’s a twist to solve it without using division. It turns out the problem actually has a use in reducing multiple points to affine representations.

In a finite field, division is much more expensive than multiplication. Each of the points in our comb is represented in projective space as (X,Y,Z). For any non-zero scalar λ, the point (λX,λY,λZ) is the same point as (X,Y,Z). We can save space (and therefore lookup time) and store the points as (X/Z,Y/Z,1), where the 1 is implied. In order to do this we need to divide each point by its own Z. Here’s where the interview problem comes in: We want each point to have the same Z. Then we only need to do a single inversion. In order to do this, we have to multiply each point by every Z but its own.

Here’s the solution: Call the result OtherZ. Break the problem into two halves: OtherZBefore and OtherZAfter

Then run two loops (Only first loop shown. Second is analogous)

accumulator = Identity
for (i = 0 to max)
    OtherZBefore[i] = accumulator
    accumulator *= points[i].Z

Then OtherZ[i] = OtherZBefore[i] ⋅ OtherZAfter[i]

Tada! You have a completed comb. Now you can write the data to disk, or print it out and embed it in the source code.