mersenne

README

Install: $ go get github.com/cznic/mathutil/mersenne
Godocs:  http://gopkgdoc.appspot.com/pkg/github.com/cznic/mathutil/mersenne

Documentation

Overview

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

Exponent

In this documentatoin 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).

Index

• Variables
• func FromFactorBigInt(d *big.Int, max uint32) (n uint32)
• func HasFactorBigInt(d *big.Int, n uint32) 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 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.