# Programs by Type

## CALCULATIONS

 Carmichael function car(m) car [m] Chinese Remainder Theorem crt [a1 m1 a2 m2] convert decimal to rational d2r [x] convert rational to decimal r2d [a q] determinant modulo m detmodm discrete logarithm base g of a modulo p ind [g a p] factor n by trial division factor [n] by p - 1 method p-1 [n [a]] by rho method rho [n [c]] find next prime getnextp [x] greatest common divisor gcd [b c] index base g of a modulo p ind [g a p] Jacobi symbol (P/Q) jacobi [P Q] Lucas functions Un, Vn modulo m lucas [n [a b] m] multiply residue classes modulo m mult [a b m] order of a modulo m order [a m [c]] phi function phi [n] pi(x) pi [x] power ak modulo m power [a k m] primitive root of prime p primroot [p [a]] prove primality of p provep [p] reduce ax2 + bxy + cy2 reduce a b c represent n as a sum of s k-th powers sumspwrs [n s k] roots of ax = b (mod m) lincon [a b m] f(x) = 0 (mod pj) hensel P(x) = 0 (mod m) polysolv x2 = a (mod p) sqrtmodp [a p] Ax = b in integers simlinde square root modulo p sqrtmodp [a p] strong pseudoprime test of m base a spsp [[a] m]

## DEMONSTRATIONS

 Chinese Remainder Theorem crtdem determinants modulo m detdem discrete logarithm base g of a modulo p inddem [g a p] Euclidean algorithm eualgdelm [b c] factorization by p - 1 method p-1dem by rho method rhodem [n] greatest common divisors fastgcd, slowgcd (see also Euclidean algorithm) heapsort algorithm hsortdem index base g of a modulo p inddem [g a p] Jacobi symbol (P/Q) jacobdem [P Q] linear congruence ax = b (mod m) lncndem [a b m] Lucas functions lucasdem [n [a b] m] multiplication of residue classes multdem1, multdem2, multdem3 order of a modulo m orderdem [a m [c]] powering algorithm pwrdem1a [a k m] pwrdem1b [a k m] pwrdem2 [a k m] RSA encryption rsa, rsapars square root modulo p sqrtdem [a p] strong pseudoprime test of m base a spspdem[[a] m]

## TABLES

 arithmetic functions arfcntab base conversions for integers basestab binary quadratic forms reduced forms qformtab forms equivalent to f(x,y) reduce binomial coefficients modulo m pascalst class numbers clanotab congruential arithmetic cngartab discrete logarithms indtab factorials modulo m fctrltab Farey fractions fareytab, fractab greatest common divisors gcdtab indices indtab intersection of arithmetic progressions intaptab Jacobi symbols jacobtab least prime factor factab linear combinations lncomtab Lucas functions lucastab Pascal's triangle modulo m pascalst order of a modulo m ordertab powers of a modulo m powertab representations as sums of powers sumspwrs, wrngtab roots of f(x) = 0 (mod pj) hensel P(x) = 0 (mod m) polysolv