Next: Modular
arithmetic on unlimited Up: Commands Previous: Unlimited precision integer
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 , which is the 12th Mersenne number, and which is
known to be prime.
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
and
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: Modular
arithmetic on unlimited Up: Commands Previous: Unlimited precision integer