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 [
http://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>