Factoring whole numbers
Factoring whole numbers has become a very important topic because of the invention of the RSA (for Rivest, Shamir, and Adleman) cryptosystem. The design of RSA uses two facts:
(1) There are very efficient ways of finding very “long” prime numbers, and of checking whether a given long number is prime or not. (We call a whole number “long” when it has thirty or more decimal digits.)
(2). But at present there is no efficient way to factor a long whole number that is the product of a few long primes. This may seem strange, but efficient methods that show that a number is composite show it indirectly without producing any factors.
But because the topic is popular, it is worthwhile to have a simple algorithm implemented on a TI-84 calculator that allows student to factor whole numbers up to one million.
We define two functions.
The first function is an auxiliary function Y1, which depends on two variables, X and N, and returns the value 1(meaning “true”) when a whole number N is a factor of a whole number X.
Comments
X–int(X/N)N computes the remainder of division of X by N. And the operation = returns one when this remainder is zero.
The second function Y2, which uses Y1, checks which whole numbers N between 2 and √(X) are factors of X, and returns the largest of them. In the case when X is prime, there is no such number, and Y2, returns zero.
Comments
Y1*N returns N when N is a factor of X, and zero otherwise. The operation seq creates a list of these numbers N, or 0, starting with N = 2 and going up to √(X). Finally, operation max selects the biggest number from the list.
For example,
Y2(1394) ENTER
returns 34, because 34 is the biggest factor of 1394 = 34*41 smaller than
√(1394) = 37.336.
This function is easy to understand and is a convenient tool for constructing “trees of factors”.
Example.
Tree of factors
So 215441 = 17*19*23*29
Lesson Index