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
Constants ¶
This section is empty.
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 ¶
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 ¶
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 ¶
HasFactorUint32 returns true if d | Mn. Typical run time for a 32 bit factor and a 32 bit exponent is < 1 µs.
func HasFactorUint64 ¶
HasFactorUint64 returns true if d | Mn. Typical run time for a 64 bit factor and a 32 bit exponent is < 30 µs.
func Mod ¶
Mod sets mod to n % Mexp and returns mod. It panics for exp == 0 || exp >= math.MaxInt32 || n < 0.
func ModPow ¶
ModPow returns b^Me % Mm. Run time grows quickly with 'e' and/or 'm' when b != 2 (then ModPow2 is used).
func ModPow2 ¶
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 ProbablyPrime ¶
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.
Types ¶
This section is empty.
Source Files