numtheory (3)

NAME

math::numtheory - Number Theory

SYNOPSIS

package require Tcl ?8.5?

package require math::numtheory ?1.0?

math::numtheory::isprime N ?option value ...?

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::isprime N ?option value ...?

The isprime command tests whether the integer N is a prime, returning a boolean true value for prime N and a boolean false value for non-prime N. 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 of 0 (if N is definitely not a prime), 1 (if N is definitely a prime), and on (if N is 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. 1 is returned for "small" N (which currently means N < 118670087467), where it is known that no false positives are possible.

The only option currently defined is:

-randommr repetitions

which 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 for repetitions is 4.

Unknown options are silently ignored.

BUGS, IDEAS, FEEDBACK

This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the category math :: numtheory of the Tcllib Trackers [core.tcl.tk/tcllib/reportlist] Please also report any ideas for enhancements you may have for either package and/or documentation.

KEYWORDS

number theory, prime

CATEGORY

Mathematics

COPYRIGHT

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