Primes and Factorizations

MuPAD® notebooks will be removed in a future release. Use MATLAB® live scripts instead.

MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.

Operate on Primes

Prime numbers are positive integers larger than 1 that have only two positive integer divisors: 1 and the number itself. In MuPAD®, you can check whether the number is prime by using the isprime function. For example, 809 is a prime number while 888 and 1 are not primes:

isprime(809), isprime(888), isprime(1)

In rare cases, the isprime function can return a false positive result. The function performs the Miller-Rabin primality test and uses 10 independent random bases. For a more accurate (and also slower) method, see Proving Primality.

The sequence of prime numbers is infinite. It starts with 2, 3, 5, 7, 11, 13, 17, and goes on. The ithprime function lets you quickly find and display any entry of this sequence. For example, to find the 100th prime number, enter ithprime(100):

ithprime(100)

To find the prime number that appears in the sequence before a particular value, use the prevprime function. To find the prime number that appears after a particular value, use the nextprime function. For example, find the prime numbers that precede and follow the number 1000:

prevprime(1000), nextprime(1000)

Note

prevprime and nextprime use the probabilistic primality test (the Miller-Rabin test). In rare cases, these functions can return nonprime numbers.

MuPAD stores a precalculated table of the prime numbers up to a certain value. The ifactor function with the PrimeLimit option returns that value:

ifactor(PrimeLimit)

The ithprime function with the PrimeLimit option returns the number of primes in that table:

ithprime(PrimeLimit)

The ithprime function extracts the prime number from this table. To compute larger prime numbers (which MuPAD does not store in the table), ithprime chooses some number as a starting point, and then recursively calls the nextprime function. Although the internal algorithm tries to reduce the number of computation steps, computing huge prime numbers can be very slow:

ithprime(100000000)

Suppose, you want to display a sequence of prime numbers. For the numbers that MuPAD stores in the table, call the ithprime function to find each number in the sequence:

ithprime(i) $ i = 1000..1010

If the numbers exceed the value returned by ifactor(PrimeLimit), MuPAD does not store them. In this case, calling ithprime for each number can be very slow. More efficiently, use ithprime to find the first number in the sequence, and then use nextprime to find all following numbers:

(n := ithprime(3*10^7)), (n := nextprime(n + 1)) $i = 1..10

To find how many prime numbers do not exceed a particular value, use the numlib::pi function:

numlib::pi(2), numlib::pi(3), numlib::pi(20),
numlib::pi(1000), numlib::pi(15.789)

Factorizations

You can represent any integer number as a product of primes. This process is called factoring an integer. To factor an integer, use the ifactor function. For example, factor the number 362880:

ifactor(362880)

Prove Primality

The function numlib::proveprime implements the Atkin-Goldwasser-Kilian-Morain algorithm for proving primality. For information about primality proving and this particular algorithm, see the following papers:

  • Atkin, A. O., and F. Morain. “Elliptic curves and primality proving.” Mathematics of Computation. Vol. 61, Number 203, 1993.

  • Goldwasser, S., and J. Kilian. “Almost all primes can be quickly certified”. Proceedings of the 18th annual ACM symposium on theory of computing. Berkeley, CA, US, 1986, pp. 316-329.

For relatively small prime numbers, numlib::proveprime returns the value TRUE. For composite numbers, the function returns FALSE:

numlib::proveprime(541), numlib::proveprime(243)

For larger prime numbers, numlib::proveprime returns a certificate of primality:

certificate := numlib::proveprime(1299709)

Generated primality certificates provide all data that you need for proving primality of a number by the Atkin-Goldwasser-Kilian-Morain algorithm. You can substitute the numbers into the algorithm and verify the primality of a number. The numlib::checkPrimalityCertificate function can verify the certificate for you:

numlib::checkPrimalityCertificate(certificate)