Comment

Comment by adonovan

You can think of a Galois field as a specially chosen permutation of a set of numbers such as 0-255 and a redefinition or remapping of the arithmetic operators + - * / such that each one is reversible: if a op b = c, then given c and b you can find a by applying the inverse of op. (In normal arithmetic of course, multiplication and division aren't reversible because of zero.) The actual operators aren't ADD SUB MUL DIV, but they are like them in the sense that they are easy to implement in a hardware ALU as functions over bit patterns.

This unlocks all kinds of clever techniques. For example, it lets you efficiently compute a "rolling" hash of every n-byte substring of a document, by simply sliding an n-byte window across the document one byte at a time, multiplying the previous hash by the incoming byte and dividing by the outgoing byte. This has lots of applications in cryptography, compression, searching, and so on.

parent adonovan 4 years ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton