[ Tcllib Home | Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

# math::numtheory(n) 1.0 tcllib "Tcl Math Library"

## 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. Please also report any ideas for enhancements you may have for either package and/or documentation.

## Keywords

number theory, prime

## Category

Mathematics

## Copyright

Copyright © 2010 Lars Hellström <Lars dot Hellstrom at residenset dot net>