Great question! Let's break down exactly how to reverse your build8b function, starting with the theory behind why this is possible, then walking through the implementation step by step.

1. Understand the Composite Structure of build8b #

First, let's expand build8b to see its nested operations clearly:

const build8b = (x) => fetch8( (fetch8(x) + 123) % 256 ^ 101 )

This is a chain of transformations:
x → fetch8(x) → (fetch8(x)+123) mod256 → [that value] ^101 → fetch8([that value]) → final output

To reverse this, we work backwards from the output, applying the inverse of each operation in reverse order.

2. Verify Each Step is a Bijection #

For a function to be invertible, every step must be a bijection—a one-to-one, onto function where each input maps to exactly one output, and every output maps back to exactly one input. Let's confirm each step:

• XOR with a fixed value: XOR is its own inverse (e.g., a ^ b ^ b = a). This is a perfect bijection.
• Modular addition: Adding a constant modulo 256 is invertible—subtract the constant modulo 256 (add 256 first to avoid negative numbers).
• fetch8 function: Let's prove this is a bijection:
  • For x >= 251, fetch8(x) = x (trivially one-to-one).
  • For x <251 (prime o=251):
    • If x <=125, fetch8(x) = x² mod251. Since 251 is prime, quadratic residues here don't collide for distinct x <=125 (because x² ≡ y² mod251 implies x=y or x+y≡0 mod251, but x+y <=250 <251).
    • If x>125, fetch8(x)=251 - (x² mod251). Using Euler's criterion, -1 is not a quadratic residue modulo 251, so these values can't collide with outputs from x<=125.
  • Every output maps to exactly one input—so fetch8 is a bijection, and has an inverse.

3. Implement the Inverse Functions #

Given the small input range (0-255), the easiest way to get fetch8's inverse is to precompute a lookup table:

// First, redefine the original helper functions
const fetch = (x, o) => { 
    if (x >= o) { 
        return x 
    } else { 
        const v = (x * x) % o 
        return (x <= o / 2) ? v : o - v 
    } 
}
const fetch8 = (x) => fetch(x, 251)

// Precompute inverse lookup table for fetch8
const fetch8InvMap = new Array(256);
for (let x = 0; x <= 255; x++) {
    const y = fetch8(x);
    fetch8InvMap[y] = x;
}
const fetch8Inv = (y) => fetch8InvMap[y];

Now, build reverse8b by reversing each step of build8b:

const reverse8b = (output) => {
    // Step 1: Inverse the outer fetch8
    const z = fetch8Inv(output);
    // Step 2: Inverse the XOR with 101
    const a = z ^ 101;
    // Step3: Inverse the (value +123) mod256 (subtract 123, mod256)
    const b = (a - 123 + 256) % 256; // +256 ensures non-negative result
    // Step4: Inverse the inner fetch8 to get original x
    const originalX = fetch8Inv(b);
    return originalX;
}

4. Test It Out #

Let's verify with your example:

console.log(build8b(100)); // Outputs 92
console.log(reverse8b(92)); // Outputs 100

Key Theory Takeaway #

Reversing composite functions relies on bijection chaining: if F(x) = f(g(h(x))), then F⁻¹(y) = h⁻¹(g⁻¹(f⁻¹(y))). For this to work, every individual function (f, g, h) must be a bijection—no two inputs map to the same output, and every possible output is covered.

Your original functions avoid duplicates precisely because they're bijections, which is exactly what makes them invertible.

Content of the question comes from Stack Exchange, asked by Lance Pollard