# Number Theory in Bash

I've been studying error correction codes, specfically the book Error Correction Coding: Mathematical Methods and Algorithms 1st Ed. by Todd K. Moon.

The order (number of elements) of any finite field (aka Galois field)
is a power of a prime number. I was curious how many integers were
valid orders for a finite field and I knew I could quickly list them
all by parsing the output of the `factor`

command.^{1} That led to
the following hack.

#!/bin/bash # Quick and dirty script to find all finite field orders less than a # given number. # See https://oeis.org/A000961 and https://oeis.org/A246655. limit=${1:-1000} echo "q = p^m" gf_count=0 while read line ; do factors=$(echo $line | cut -d: -f2) num_uniq_factors=$(echo $factors | tr ' ' '\n' | uniq | wc -w) if [ $num_uniq_factors = 1 ] ; then ((gf_count++)) i=$(echo $line | cut -d: -f1) base=$(echo $factors | cut -d ' ' -f1) power=$(echo $factors | wc -w) echo "${i} = ${base}^${power}" fi done < <(seq "$limit" | factor) gf_percent=$(echo "2k 100 ${gf_count} * ${limit} / p" | dc) echo -n "${gf_count} Galois fields of order less than or equal to ${limit} " echo "(${gf_percent}%)."

## Footnotes:

^{1}

A neat analysis of the `factor`

program included in GNU
coreutils is at:
https://www.maizure.org/projects/decoded-gnu-coreutils/factor.html.