# 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

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.