How to compute parity bytes instead of parity numbers?
Matrix elements must obey a particular interface.
They must belong to a field.
We want a field with 256 elements.
What is a field?
interfaceField<T> {staticZero: T, One: T
plus(b: T): T // a \oplus ba⊕b
negate(): T // -a−a
times(b: T): T // a \otimes ba⊗b
reciprocate(): T // a^{-1}a−1, for a \ne 0a≠0
equals(b: T): bool // a = ba=b
}
// a \ominus ba⊖b
minus(b: T): T => this.plus(b.negate())
// a \oslash ba⊘b
dividedBy(b: T): T => this.times(b.reciprocate())
Field 📜interface contract📜
Identities: a⊕0=a⊗1=a.
Inverses: a⊕−a=0, and if a≠0,
👉a⊗a−1=1👈.
Associativity: (a⊕b)⊕c=a⊕(b⊕c), (a⊗b)⊗c=a⊗(b⊗c).
Commutativity: a⊕b=b⊕a, a⊗b=b⊗a.
Distributivity: a⊗(b⊕c)=(a⊗b)⊕(a⊗c).
Rational numbers (i.e., fractions) form a field: (p/q)−1=q/p.
Integers don’t form a field, since only 1 and −1
have reciprocals.
Integers mod p form a field with p elements, only when p is prime, e.g. field of 257 elements.
🤓 Math fact 🤓: Given an integer 0<a<257, there is exactly one 0<b<257 such that (a⋅b)mod257=1. (Can replace 257 with any prime number p).
reciprocate() => {
if (this === 0) { thrownewError("Division by zero"); }
for (let i = 0; i < 257; i += 1) {
if ((this * i) % 257 === 1) { return i; }
}
thrownewError("Shouldn't get here!");
}
If speed is a problem, build a table.
Field of 257 elements gets us close…
Problem: 256 isn’t a prime number!
Does this mean we cannot make a field of 256 elements?
No!
We can’t just do so based on standard integer arithmetic.
Binary carry-less arithmetic
Let a=23 and b=54.
Then, with binary carry-less addition,
a = 23 = 10111b
^ b = 54 = 110110b
-------
100001b
so a⊕b=100001b=33.
Binary carry-less addition is just bitwise xor!
So is binary carry-less subtraction, since a ^ a = 0.
Let a=23 and b=54.
Then, with carry-less arithmetic,
so a⊗b=1111100010b=994.
Let a=55 and b=19. Then, with carry-less arithmetic,
11b
--------
b = 19 = 10011b )110111b = 55 = a
^ 10011
-----
10001
^ 10011
-----
10b
so a⊘b=11b=3
with remainder 10b=3.
Important subtlety: we don’t
stop when the remainder is less than the divisor, but when
it has fewer digits than the divisor.
Properties of (carry-less) mod
mod by 256≤n<512⇒n possible remainders.
clmod by 256≤n<512⇒256 possible remainders.
Very interesting…clmod by prime number 256≤p<512?
What are prime numbers?
An integer p>1 that cannot be expressed as p=a⋅b, for a,b>1.
Multiplication operation determines the prime numbers.
Want a “carry-less” prime number between 256 and 512!
283 is such a number. (Coincidentally, it’s also a regular prime.)
Field of 256 elements
…is just binary carry-less arithmetic mod 283.
classField256ElementimplementsField<Field256Element> {
static Zero = 0, One = 1
plus(b) => (a ^ b)
negate() => a
times(b): => clmod(clmul(a, b), 283)
reciprocate() => // next slide
equals(b) => (a === b)
}
🤓 Math fact 🤓: Given an integer 0<a<256, there is a 0<b<256 such that (a⊗b)clmod283=1.
reciprocate() => {
if (this === 0) { thrownewError("Division by zero"); }
for (let i = 0; i < 256; i += 1) {
if (clmod(clmul(this, i), 283) === 1) { return i; }
}
thrownewError("Shouldn't get here!");
}
The full algorithm
Do everything with Field256Element, i.e. bytes with carry-less arithmetic mod 283.
In particular, compute P like:
P=((3⊕0)−1(4⊕0)−1(3⊕1)−1(4⊕1)−1(3⊕2)−1(4⊕2)−1)=(3−14−12−15−116−1)=(246203141821123)