Provided by: tcllib_1.14-dfsg-1_all

**NAME**

math::numtheory - Number Theory

**SYNOPSIS**

package requireTcl?8.5?package requiremath::numtheory?1.0?math::numtheory::isprimeN?optionvalue...? _________________________________________________________________

**DESCRIPTION**

This package is for collecting various number-theoretic operations, though at the moment it only provides that of testing whether an integer is a prime.math::numtheory::isprimeN?optionvalue...? Theisprimecommand tests whether the integerNis a prime, returning a boolean true value for primeNand a boolean false value for non-primeN. The formal definition of ´prime' used is the conventional, that the number being tested is greater than 1 and only has trivial divisors. To be precise, the return value is one of0(ifNis definitely not a prime),1(ifNis definitely a prime), andon(ifNis probably prime); the latter two are both boolean true values. The case that an integer may be classified as "probably prime" arises because the Miller-Rabin algorithm used in the test implementation is basically probabilistic, and may if we are unlucky fail to detect that a number is in fact composite. Options may be used to select the risk of such "false positives" in the test.1is returned for "small"N(which currently meansN< 118670087467), where it is known that no false positives are possible. The only option currently defined is:-randommrrepetitionswhich controls how many times the Miller-Rabin test should be repeated with randomly chosen bases. Each repetition reduces the probability of a false positive by a factor at least 4. The default forrepetitionsis 4. Unknown options are silently ignored.

**KEYWORDS**

number theory, prime

**CATEGORY**

Mathematics

**COPYRIGHT**

Copyright (c) 2010 Lars Hellström <Lars dot Hellstrom at residenset dot net>