next up previous
Next: Modular arithmetic on unlimited Up: Commands Previous: Unlimited precision integer

Advanced algebraic operations on unlimited precision integers

In addition to the basic operation commands, several commands of ALG48 perform advanced algebraic computations on unlimited precision integers.

The integer argument(s) for all these commands, except FCTR, can be given (in any combination) as (integer) real numbers, unlimited precision binary integers, or strings representing the number in decimal. Here are some examples of the primality testing commands. The first number below is tex2html_wrap_inline1894 , which is the 12th Mersenne number, and which is known to be prime.

eqnarray691

eqnarray701

Because of its use as a simplification command, FCTR leaves real numbers unchanged and will only factor integers given as binary integers or as strings. If the number is given as a binary integer FCTR returns a list with the prime factors. If the number is given as a string, the factors are given in a symbolic form. For instance

displaymath1890

and

displaymath1891

FCTR uses advanced integer factorization algorithms and can factor relatively large numbers. However no ``efficient'' (polynomial-time) algorithm is known for factoring arbitrarily large integers and it is widely believed that no such algorithm can exist. Thus FCTR will factor completely only reasonably small numbers (up to 20-30 digits) or larger numbers that consist only of small factors. To avoid running forever, if FCTR does not make any progress after one minute it returns the number unfactored (or only partially factored). As always, you can also abort the computation by pressing the CANCEL (ON) key.

In the contrary, the primality testing algorithm (used by PRIM?, PRIM+ and PRIM-) can handle very large numbers. However the algorithm is randomized and might, with very low probability, say that a number is prime when it is not (but will never say that a number is not prime when in fact it is).


next up previous
Next: Modular arithmetic on unlimited Up: Commands Previous: Unlimited precision integer

Claude-Nicolas Fiechter (fiechter@cs.pitt.edu), 12 May 1998