Determine whether a number is a primitive root of a given prime.

primroots.sh

#!/bin/bash
# ncoop 2015/08/13

set -uoe pipefail
IFS=$'\n\t'

usage() {
  cat << EOF
Determine whether a number is a primitive root of a given prime.

usage: $(basename "$0") [[-p | --prime PRIME]] [[-g | --generator GENERATOR]]
where PRIME is a prime number and GENERATOR is a potential primitive root

refer to http://mathworld.wolfram.com/PrimitiveRoot.html
EOF
}

checkint() {
  if [[ ! $1 =~ ^-?[0-9]+$ || $1 -lt 1 ]]; then
    printf "Parameters must be positive integers.\n\n"
    exit 1
  fi
}

checkless() {
if [[ $g -ge $p ]]; then
  printf "Generator must be less than or equal to prime.\n\n"
  exit 1;
fi
}

while [ "${1:-}" != "" ]; do
  case $1 in
    -p | --prime )
    shift; p=${1:-}
    checkint "$p"
    ;;

    -g | --generator )
    shift; g=${1:-}
    checkint "$g"
    ;;

    -h | --help )
    usage; exit
    ;;

    * )
    usage; exit 1
  esac
  shift
done

p=${p:-}
if [[ -z $p ]]; then
  echo -n "Enter a prime number: "; read -r p; checkint "$p"
fi
g=${g:-}
if [[ -z $g ]]; then
  echo -n "Enter a generator:    "; read -r g; checkint "$g"
fi
checkless

declare -i a=1   # accumulator
declare -i w1=${#p}  # left field width
declare -i w2=$((${#g} + 5 + ${#p}))  # right field width
declare -a v=()  # array of resulting values

# header row and separator
printf "%${w1}s  %${w2}s\n" "n" "$g^n % $p"
for ((i=1; i<=$((w1 + w2)); i+=1)); do 
  c="-"
  if [[ $i -eq $w1 ]]; then c+="  "; fi 
  printf -- "$c"
done
echo

is_root=true
is_prime=true
for ((i=1; i<p; i+=1)); do
  let "a = a * g % p"  # multiply and modulus

  d=
  if [[ ${v[a]+isset} ]]; then 
    is_root=false  # already saw this result
    d='duplicate'
  fi
  v[a]=1  # mark result as seen

  f=
  if [[ $((p % i)) -eq 0 && $i -gt 1 ]]; then
    is_prime=false
    f='factor'
  fi

  printf "%${w1}d  %${w1}d  %9s  %s\n" "$i" "$a" "$d" "$f"  # print results
done

echo
if [ "$is_prime" == false ]; then
  echo "$p is not a prime number!"
elif [ "$is_root" == true ]; then
  echo "$g is a primitive root of $p."
else
  echo "$g is not a primitive root of $p."
fi
echo

[ncoop@SG41 Documents]$ ./primroots.sh -p 12 -g 5
 n  5^n % 12
--  --------
 1   5             
 2   1             factor
 3   5  duplicate  factor
 4   1  duplicate  factor
 5   5  duplicate  
 6   1  duplicate  factor
 7   5  duplicate  
 8   1  duplicate  
 9   5  duplicate  
10   1  duplicate  
11   5  duplicate  

12 is not a prime number!