README
¶
Install: $ go get modernc.org/mathutil/mersenne Godocs: http://gopkgdoc.appspot.com/pkg/modernc.org/mathutil/mersenne
Documentation
¶
Overview ¶
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).
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 Mul(a, b uint32) *big.Int
- func New(n uint32) (m *big.Int)
- func ProbablyPrime(n, a uint32) bool
- func Sqr(n uint32) *big.Int
Constants ¶
This section is empty.
Variables ¶
var Known map[uint32]int
Known maps the exponent of known Mersenne primes its ordinal number/rank. Ranks > 47 are currently provisional.
var Knowns = []uint32{
2,
3,
5,
7,
13,
17,
19,
31,
61,
89,
107,
127,
521,
607,
1_279,
2_203,
2_281,
3_217,
4_253,
4_423,
9_689,
9_941,
11_213,
19_937,
21_701,
23_209,
44_497,
86_243,
110_503,
132_049,
216_091,
756_839,
859_433,
1_257_787,
1_398_269,
2_976_221,
3_021_377,
6_972_593,
13_466_917,
20_996_011,
24_036_583,
25_964_951,
30_402_457,
32_582_657,
37_156_667,
42_643_801,
43_112_609,
57_885_161,
74_207_281,
77_232_917,
82_589_933,
136_279_841,
}
Knowns list the exponent of currently (October 2024) 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 recommended 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 HasFactorBigInt2 ¶
HasFactorBigInt2 returns true if d | Mn, d > 0
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