package mersenne

import "k8s.io/kubernetes/Godeps/_workspace/src/github.com/cznic/mathutil/mersenne"

Package mersenne collects utilities related to Mersenne numbers[1] and/or some of their properties.

Exponent

In this documentation the term 'exponent' refers to 'n' of a Mersenne number Mn equal to 2^n-1. This package supports only uint32 sized exponents. New() currently supports exponents only up to math.MaxInt32 (31 bits, up to 256 MB required to represent such Mn in memory as a big.Int).

Links

Referenced from above:

[1] http://en.wikipedia.org/wiki/Mersenne_number

Index ¶

• Variables
• func FromFactorBigInt(d *big.Int, max uint32) (n uint32)
• func HasFactorBigInt(d *big.Int, n uint32) bool
• func HasFactorBigInt2(d, n *big.Int) bool
• func HasFactorUint32(d, n uint32) bool
• func HasFactorUint64(d uint64, n uint32) bool
• func Mod(mod, n *big.Int, exp uint32) *big.Int
• func ModPow(b, e, m uint32) (r *big.Int)
• func ModPow2(e, m uint32) (x uint32)
• func New(n uint32) (m *big.Int)
• func ProbablyPrime(n, a uint32) bool

Variables ¶

var Known map[uint32]int

Known maps the exponent of known Mersenne primes its ordinal number/rank. Ranks > 41 are currently provisional.

var Knowns = []uint32{
	2,
	3,
	5,
	7,
	13,
	17,
	19,
	31,
	61,
	89,

	107,
	127,
	521,
	607,
	1279,
	2203,
	2281,
	3217,
	4253,
	4423,

	9689,
	9941,
	11213,
	19937,
	21701,
	23209,
	44497,
	86243,
	110503,
	132049,

	216091,
	756839,
	859433,
	1257787,
	1398269,
	2976221,
	3021377,
	6972593,
	13466917,
	20996011,

	24036583,
	25964951,
	30402457,
	32582657,
	37156667,
	42643801,
	43112609,
	57885161,
}

Knowns list the exponent of currently (March 2012) known Mersenne primes exponents in order. See also: http://oeis.org/A000043 for a partial list.

Functions ¶

func FromFactorBigInt ¶

func FromFactorBigInt(d *big.Int, max uint32) (n uint32)

FromFactorBigInt returns n such that d | Mn if n <= max and d is odd. In other cases zero is returned.

It is conjectured that every odd d ∊ N divides infinitely many Mersenne numbers. The returned n should be the exponent of smallest such Mn.

NOTE: The computation of n from a given d performs roughly in O(n). It is thus highly recomended to use the 'max' argument to limit the "searched" exponent upper bound as appropriate. Otherwise the computation can take a long time as a large factor can be a divisor of a Mn with exponent above the uint32 limits.

The FromFactorBigInt function is a modification of the original Will Edgington's "reverse method", discussed here: http://tech.groups.yahoo.com/group/primenumbers/message/15061

func HasFactorBigInt ¶

func HasFactorBigInt(d *big.Int, n uint32) bool

HasFactorBigInt returns true if d | Mn, d > 0. Typical run time for a 128 bit factor and a 32 bit exponent is < 75 µs.

func HasFactorBigInt2 ¶

func HasFactorBigInt2(d, n *big.Int) bool

HasFactorBigInt2 returns true if d | Mn, d > 0

func HasFactorUint32 ¶

func HasFactorUint32(d, n uint32) bool

HasFactorUint32 returns true if d | Mn. Typical run time for a 32 bit factor and a 32 bit exponent is < 1 µs.

func HasFactorUint64 ¶

func HasFactorUint64(d uint64, n uint32) bool

HasFactorUint64 returns true if d | Mn. Typical run time for a 64 bit factor and a 32 bit exponent is < 30 µs.

func Mod ¶

func Mod(mod, n *big.Int, exp uint32) *big.Int

Mod sets mod to n % Mexp and returns mod. It panics for exp == 0 || exp >= math.MaxInt32 || n < 0.

func ModPow ¶

func ModPow(b, e, m uint32) (r *big.Int)

ModPow returns b^Me % Mm. Run time grows quickly with 'e' and/or 'm' when b != 2 (then ModPow2 is used).

func ModPow2 ¶

func ModPow2(e, m uint32) (x uint32)

ModPow2 returns x such that 2^Me % Mm == 2^x. It panics for m < 2. Typical run time is < 1 µs. Use instead of ModPow(2, e, m) wherever possible.

func New ¶

func New(n uint32) (m *big.Int)

New returns Mn == 2^n-1 for n <= math.MaxInt32 or nil otherwise.

func ProbablyPrime ¶

func ProbablyPrime(n, a uint32) bool

ProbablyPrime returns true if Mn is prime or is a pseudoprime to base a. Note: Every Mp, prime p, is a prime or is a pseudoprime to base 2, actually to every base 2^i, i ∊ [1, p). In contrast - it is conjectured (w/o any known counterexamples) that no composite Mp, prime p, is a pseudoprime to base 3.

Source Files ¶

mersenne.go