Elementary Number Theory

on the TI-8x Graphing Calculator


Contents

  1. General
  2. Basic Operations
  3. GCD
  4. Exponentiation - PowMod
  5. Finding Primes - The Sieve of Eratosthenes
  6. Factoring - Pollard Rho
  7. Computing the Order of Integers
  8. Commands

[Prev] [TI Calc Intro] [Next]

General

The Texas Instruments calculators sells a line of programmable hand calculators with set of functions and a simple programming language which is, at a simple level, compatible between calculator models. These programs will run on the TI-86/85/83/82/72.

The TI-8x series of calculators runs on a variant of the old Zilog Z80 processor and supports computations with integers as large as 246. (The display will not display integers this large, converting them to floating point for display, but some simple experiments seems to show that the internal representation is still faithful.) This means that, taking into account multiplication and modular reduction, the largest numbers which can be used in these algorithms is 223=8388608.

These programs can be written and saved on the calculator from PRGM mode, entered by typing the [PRGM] key. The basic functions are entered into a program by finding them in the menu structure, usually in MATH mode. On the TI-85/86 the functions may also be entered by typing their names in directly (case is not important).

Basic Operations

The basic arithmetic operations, +, -, /, are available from the keyboard. The factorial operation, n!, is available from the [PROB] submenu of the [MATH] menu.

The TI86/85 have a modular reduction operator. This can either be typed in directly from the keyboard: MOD(37,5) (case is not important), or found in the [NUM] submenu of the [MATH] menu. For the other calculators the same effect as MOD(n,m) can be gotten by computing n-m*int(n/m) if m is positive.

GCD

GCD is a built-in function for all but the TI-82. The GCD function found in the [MISC] submenu of the [MATH] menu.

An extended GCD algorithm can be implemented with the following program.

Input "N ",N
Input "M ",M
[1,0]->K
[0,1]->L
Repeat (N=0)
int(M/N)->Q
M-N*int(M/N)->M
L-Q*K->L
If (M==0)
Goto XGCDEnd
int (N/M)->Q
N-M*int(N/M)->N
K-Q*L->K
End
M->N
L->K
Lbl XGCDEnd
Disp N,K

Users of the TI-82 may use the following program to compute the basic GCD program. This is written so it can be used as a subroutine in other programs by placing the operands in x and y and expecting the result in x.

Repeat (Y=0)
X-Y*int(X/Y)->X
If (X==0)
Y->X
Return
End
Y-X*int(Y/X)->Y
End
Return

Exponentiation - PowMod

The Russian Peasant method for modular exponentiation can be implemented with the following program:

Input "Modulus ",M
Input "Element ",E
Input "Power ",P
1->A
Repeat (P=0)
If ((P-2*int(P/2))=1)
E*A-M*int(E*A/M)->A
E^2-M*int(E^2/M)->E
iPart (P/2)->P
End
Disp A

Finding Primes - The Sieve of Eratosthenes

The Sieve of Eratosthenes for finding successive primes can be implemented with the following program. The program sieves over the first 255 odd numbers, printing out the primes.

255 -> L
L -> dim(L1)
Fill(0,L1)
For(I,1,L)
If (L1(I)==0)
Then
Disp 2*I+1
For(J,I,L,2*I+1)
1 -> L1(J)
End
End
End
DelVar(L1)

Factoring - Pollard Rho

The Pollard Rho method for factorization can be implemented with the following program:

Input "Number ",M
2->R
5->S
1->F
While (F=1)
R^2+1-M*int((R^2+1)/M)->R
S^2+1-M*int((S^2+1)/M)->S
S^2+1-M*int((S^2+1)/M)->S
gcd(abs(R-S),M)->F
End
Disp F

Computing the Order of Integers

The order of an integer in the group of units mod some other integer (ie the smallest exponent e such that be(mod N)=1) can be computed with the following program:

Input "Modulus ",M
Input "Element ",E
1 -> O
ELT -> A
Repeat (A=1)
E*A-M*int(E*A/M) -> A
ORD+1 -> ORD
End
Disp ORD

Commands


Robert Campbell
Last modified: Oct 6, 2002