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.


# Quick and dirty script to find all finite field orders less than a
# given number.
# See and


echo "q = p^m"


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
        i=$(echo $line | cut -d: -f1)
        base=$(echo $factors | cut -d ' ' -f1)
        power=$(echo $factors | wc -w)
        echo "${i} = ${base}^${power}"
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}%)."



A neat analysis of the factor program included in GNU coreutils is at:

© Copyright 2022, Remington Furman,