Editing Finite field arithmetic (section)

== Program examples ==
=== C programming example ===
Here is some [[C (programming language)|C]] code which will add and multiply numbers in the characteristic 2  finite field of order 2<sup>8</sup>, used for example by Rijndael algorithm or Reed–Solomon, using the [[Ancient Egyptian multiplication#Russian peasant multiplication|Russian peasant multiplication algorithm]]:

<syntaxhighlight lang="c">
/* Add two numbers in the GF(2^8) finite field */
uint8_t gadd(uint8_t a, uint8_t b) {
	return a ^ b;
}

/* Multiply two numbers in the GF(2^8) finite field defined 
 * by the modulo polynomial relation x^8 + x^4 + x^3 + x + 1 = 0
 * (the other way being to do carryless multiplication followed by a modular reduction)
 */
uint8_t gmul(uint8_t a, uint8_t b) {
	uint8_t p = 0; /* accumulator for the product of the multiplication */
	while (a != 0 && b != 0) {
        if (b & 1) /* if the polynomial for b has a constant term, add the corresponding a to p */
            p ^= a; /* addition in GF(2^m) is an XOR of the polynomial coefficients */

        if (a & 0x80) /* GF modulo: if a has a nonzero term x^7, then must be reduced when it becomes x^8 */
            a = (a << 1) ^ 0x11b; /* subtract (XOR) the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
        else
            a <<= 1; /* equivalent to a*x */
        b >>= 1;
	}
	return p;
}
</syntaxhighlight>

This example has [[Timing attack|cache, timing, and branch prediction side-channel]] leaks, and is not suitable for use in cryptography.

=== D programming example ===
This [[D (programming language)|D]] program will multiply numbers in Rijndael's finite field and generate a [[Netpbm format#PGM example|PGM]] image:
<syntaxhighlight lang="D">
/**
Multiply two numbers in the GF(2^8) finite field defined
by the polynomial x^8 + x^4 + x^3 + x + 1.
*/
ubyte gMul(ubyte a, ubyte b) pure nothrow {
    ubyte p = 0;

    foreach (immutable ubyte counter; 0 .. 8) {
        p ^= -(b & 1) & a;
        auto mask = -((a >> 7) & 1);
        // 0b1_0001_1011 is x^8 + x^4 + x^3 + x + 1.
        a = cast(ubyte)((a << 1) ^ (0b1_0001_1011 & mask));
        b >>= 1;
    }

    return p;
}

void main() {
    import std.stdio, std.conv;
    enum width = ubyte.max + 1, height = width;

    auto f = File("rijndael_finite_field_multiplication.pgm", "wb");
    f.writefln("P5\n%d %d\n255", width, height);
    foreach (immutable y; 0 .. height)
        foreach (immutable x; 0 .. width) {
            immutable char c = gMul(x.to!ubyte, y.to!ubyte);
            f.write(c);
        }
}</syntaxhighlight>

This example does not use any branches or table lookups in order to avoid side channels and is therefore suitable for use in cryptography.