fftype

finite-field arithmetic within the type system

Start by installing dependencies with yarn or npm i. To run a function, assign its result to a type and simply "hover over" that type to see the results of "running" that function with some input.

Implementations

We have the following existing implementations:

• int4: 4-Bit Non-Negative Integers
• int5: 5-Bit Non-Negative Integers
• gf5: Galois Field of order 5
• gf13: Galois Field of order 13

To use an implementation, simply export them at source.d.ts.

Writing an implementation

When writing an implementation for a new field of order $p$, one must do the following:

• Let $k$ be the minimum number of bits required to represent $p$.
• Implement $k+1$ bits bitwise arithmetic.
• Define the type of order in $k+1$ bits.
• Define the type of field elements in $k+1$ bits.

For example, consider the Galois Field of order 5. The number 5 is representable with 3 bits as 101, so:

• We must implement 4-bit arithmetic.
• We define type Ford = [0, 1, 0, 1] which is 5 in bitwise representation.
• We implement the field type type Felt = [0, 1, 0, 0] | [0, 0, Bit, Bit] which covers all bitwise representation of numbers 0, 1, 2, 3, 4.

As another example, consider the Galois Field of order 13. The number 13 is representable with 4 bits as 1101, so:

• We must implement 5-bit arithmetic.
• We define type Ford = [0, 1, 1, 0, 1] which is 13 in bitwise representation.
• We implement the field type type Felt = [0, 1, 1, 0, 0] | [0, 1, 0, Bit, Bit] | [0, 0, Bit, Bit, Bit] which covers all bitwise representation of numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.

Testing

Tests are done via @type-challenges/utils, you can run them via yarn test. Note that testing is simply compiling everything and see if you get any errors.

Status

• Bitwise Operations
  • Addition
  • Subtraction
  • Rotations
  • Shifting
  • Fills
  • Logic
• Finite Field Arithmetic
  • Addition
  • Additive Inverse
  • Multiplication
  • Multiplicative Inverse
  • Subtraction via Additive Inverse
  • Division via Multiplicative Inverse
  • Quotient
  • Modulus
  • Remainder
  • Comparators

Any help is appreciated...

Resources

• Building Complex Types
• Tail Recursion in TS