Module _gmp.gmpz¶

GMP Integers¶

Object mpz¶

class _gmp.gmpz.mpz([int|float|str[, base=0]|mpz])¶

Parameters:

(optional) –

This argument is either an int, a float, a str, or a mpz.

float: must fit into a C double.
str: base must be 0 or in range [2-62].

Returns:

A new mpz object.

Raises:

TypeError, ValueError, OverflowError –

Some examples of mpz object construction:

>>> z = mpz() # C equiv.: mpz_t z; mpz_init(z);
>>> z = mpz(2026)
>>> z = mpz(3.14) # C equiv.: mpz_t z; mpz_init_set_d(3.14);
>>> z = mpz('10001011', 2) # C equiv.: mpz_t z; mpz_init_set_str('10001011', 2);
>>> u = mpz(z)
>>> print(u)
2026

Properties of the mpz object¶

Operators¶

Operation	Result	Notes
x + y	sum of x and y	(1)
x - y	difference of x and y	(1)
x * y	product of x and y	(1)
x // y	floored quotient of x and y	(1)
x % y	remainder of `x / y`	(1)
-x	x negated
+x	x unchanged
abs(x)	absolute value of x
int(x)	x converted to Python integer
divmod(x, y)	the pair `(x // y, x % y)`	(1)
pow(x, y, z=None)	x ** y (mod z) if z != None	(2)
x ** y	x to the power y	(3)

Notes:

The operands x and y are either instances of mpz or int.
All operands are either instances of mpz or int, except for z, which can be Ǹone, then pow(x, y, None) is equivalent to x ** y. In the latter case, y must be an instance of int that must fit into a C unsigned long.
Operand x is an instance of mpz and y is an instance of int that must fit into a C unsigned long.

Note

All corresponding in-place operators are therefore available, namely: +=, -=, *=, etc.

Number Theoretic Functions¶

Note

In the following, z denotes a generic mpz object.

z.probab_prime_p([reps=24])¶

Python wrapper for GNU MP mpz_probab_prime_p() function.

Parameters:: reps – Number of Miller=Rabin probabilistic primality tests. Must be in range [15-50], otherwise raises ValueError.
Returns:: 2 if z is definitely prime, returns 0 if z is probably prime (\(p\leq4^{=reps}\)), or returns 0 if z is composite.
Raises:: TypeError, ValueError –

z.nextprime()¶

Python wrapper for GNU MP mpz_nextprime() function.

Returns:: next prime greater than z.

z.prevprime()¶

Python wrapper for GNU MP mpz_prevprime() function.

Returns:: (p, n) where p is the greatest prime less than z or None (if it doesn’t exist) and n is either 0 if p is None, 1 if p is probably prime, or 2 if p is definitely prime.

z.sqrt()¶

Python wrapper for GNU MP mpz_sqrt() function.

Returns:: \(\lfloor\sqrt z\rfloor\)
Raises:: GMPErrSqrtOfNegative –

z.sqrtrem()¶

Python wrapper for GNU MP mpz_sqrtrem() function.

Returns:: (root, rem), where root is \(\lfloor\sqrt z\rfloor\) and rem is \((z-root^2)\).
Raises:: GMPErrSqrtOfNegative –

z.root(n)¶

Python wrapper for GNU MP mpz_root() function.

Parameters:: n – an instance of int that must fit into a C unsigned long.
Returns:: (r, b), where r is \(\lfloor\sqrt[n]z\rfloor\) and b a bool whose value is True if the computation was exact, False otherwise.
Raises:: TypeError, GMPErrSqrtOfNegative –

z.rootrem(n)¶

Python wrapper for GNU MP mpz_rootrem() function.

Parameters:: n – an instance of int that must fit into a C unsigned long.
Returns:: (root, rem), where root is \(\lfloor\sqrt[n]z\rfloor\) and rem is \((z-root^n)\).
Raises:: TypeError, GMPErrSqrtOfNegative –

z.perfect_power_p()¶

Python wrapper for GNU MP mpz_perfect_power_p() function.

Returns:: True if z is a perfect power, False otherwise.

z.perfect_square_p()¶

Python wrapper for GNU MP mpz_perfect_square_p() function.

Returns:: True if z is a perfect square, False otherwise.

Bitwise Operations¶

Operation	Result	Notes
x \| y	bitwise or of x and y	(1)
x ^ y	bitwise exclusive or of x and y	(1)
x & y	bitwise and of x and y	(1)
x << n	x shifted left by n bits	(2)
x >> n	x shifted right by n bits	(2)
~x	the bits of x inverted

Notes:

The operands x and y are either instances of mpz or int.
Operand x is an instance of mpz and n is an instance of int that must fit into a C unsigned long.

Note

All corresponding in-place operators are therefore available, namely: |=, ^=, &=, <<= and >>=.

Other Bitwise Operations¶

Let z be an instance of mpz, then the following methods are applicable to z:

z.setbit(bit_index)¶

Python wrapper for GNU MP mpz_setbit() function. Set bit bit_index in z.

Parameters:: bit_index – a int that must fit into a C unsigned long.
Returns:: None.

z.clrbit(bit_index)¶

Python wrapper for GNU MP mpz_clrbit() function. Clear bit bit_index in z.

Parameters:: bit_index – a int that must fit into a C unsigned long.
Returns:: None.

z.combit(bit_index)¶

Python wrapper for GNU MP mpz_combit() function. Complement bit bit_index in z.

Parameters:: bit_index – a int that must fit into a C unsigned long.
Returns:: None.

z.tstbit(bit_index)¶

Python wrapper for GNU MP mpz_combit() function. Test bit bit_index in z and return False or True accordingly.

Parameters:: bit_index – a int that must fit into a C unsigned long.
Returns:: True or False.

z.popcount()¶

Python wrapper for GNU MP mpz_popcount() function.

Returns:: If z > 0, returns the number of 1 bits in the binary representation of z. If z < 0, the number of 1 is infinite, and the return value is the largest possible value of a unsigned long.

z.scan0(starting_bit=0)¶

Python wrapper for GNU MP mpz_scan0() function. Scan z, starting from bit starting bit, towards more significant bits, until the first 0 bit is found. Return the index of the found bit.

Parameters starting_bit:: a int that must fit into a C unsigned long.
Returns:: The index of the found bit.
Raises:: TypeError –

z.scan1(starting_bit=0)¶

Python wrapper for GNU MP mpz_scan0() function. Scan z, starting from bit starting bit, towards more significant bits, until the first 1 bit is found. Return the index of the found bit.

Parameters starting_bit:: a int that must fit into a C unsigned long.
Returns:: The index of the found bit.
Raises:: TypeError –

Some examples:

>>> z = mpz()
>>> z.setbit(31)
>>> print(z)
2147483648
>>> z.clrbit(31)
>>> print(z)
0
>>> z.combit(15)
>>> print(z, z.tstbit(15))
32768 True
>>> z = mpz(0x8fffffff)
>>> print(z.popcount()
29
>>> print((-z).popcount())
18446744073709551615
>>> z = mpz(0x8fffff)
>>> print(z.scan0())
20
>>> z = mpz(1 << 32)
>>> print(z.scan1())
32

Miscellaneous methods¶

Let z be an instance of mpz:

z.sizeinbase(base=10)¶

Python wrapper for GNU MP mpz_sizeinbase() function.

Parameters:: base – a int in range [2-62].
Returns:: The size of z measured in number of digits in the given base.
Raises:: TypeError, ValueError –

z.get_str(base=10)¶

Python wrapper for GNU MP mpz_get_str() function.

Parameters:: base – a int in interval [2, 62] or in interval [-36, -2].
Returns:: The conversion of z to a string (str) of digits in base base.
Raises:: TypeError, ValueError –

Note

The prefix 0b (respectively: 0o, 0x) is added when the base is 2 (respectively: 8, 16).

>>> z = mpz(2000)
>>> print(z.get_str(7))
5555
>>> print(z.get_str(16))
0x7d0
>>> print(z.get_str(2))
0b11111010000

Comparisons and Booleans¶

Let x and y be two objects that are either instances of mpz or int. Then all comparison operations are valid: x < y, x <= y, x > y, x >= y, x == y, x != y.

Instructions such as if x: and if not x: are valid and have their usual meaning.

Some examples:

>>> x = mpz(10)
>>> y = mpz(5)
>>> x < y
False
>>> x == 2 * y
True
>>> -y >= -5
True
>>> 11 > x
True
>>> -2 * -y == x
True

Attributes¶

Note

In the following, z denotes a generic mpz object.

z.sgn¶: z.sgn is the sign of z: +1 if z > 0, 0 if z == 0, and −1 if z < 0.

z.is_even¶: z.is_even is True if z is even, False otherwise.

z.is_odd¶: z.is_odd is True if z is odd, False otherwise.

z.is_pow_of_2¶: z.is_pow_of_2 is True if z is a power of 2, False otherwise.

Module Methods¶

_gmp.gmpz.gcd(z1, z2)¶

Python wrapper for GNU MP mpz_gcd() function.

Parameters z1, z2:: z1 and z2 are either instances of mpz or int.
Returns:: The greatest common divisor of z1 and z2.
Raises:: TypeError –

_gmp.gmpz.gcdext(z1, z2)¶

Python wrapper for GNU MP mpz_gcdext() function.

Parameters z1, z2:: z1 and z2 are either instances of mpz or int.
Returns:: (g, s, t) where g is the greatest common divisor of z1 and z2 and the pair (s, t) that satisfies the equation: \(g=sz_1+tz_2\).
Raises:: TypeError –

>>> print(gcdext(1728, 356))
(4, 41, -199) # 4 = 41*1728 - 199*356

_gmp.gmpz.lcm(z1, z2)¶

Python wrapper for GNU MP mpz_lcm() function.

Parameters z1, z2:: z1 and z2 are either instances of mpz or int.
Returns:: The least common multiple of z1 and z2.
Raises:: TypeError –

_gmp.gmpz.divisible_p(z, d)¶

Python wrapper for GNU MP mpz_divisible_p() and mpz_divisible_ui_p() functions.

Parameters z, d:: z and d are either instances of mpz or int.
Returns:: True if z is exactly divisible by d, False otherwise.
Raises:: TypeError –

_gmp.gmpz.divisible_2exp_p(z, d)¶

Python wrapper for GNU MP mpz_divisible_2exp_p() function.

Parameters z, d:: z is either an instance of mpz or int. d is a int that must fit into a C unsigned long.
Returns:: True if z is exactly divisible by \(2^d\), False otherwise.
Raises:: TypeError –

_gmp.gmpz.congruent_p(z, c, d)¶

Python wrapper for GNU MP mpz_congruent_p() and mpz_congruent_ui_p() functions.

Parameters z, c, d:: z, c and d are either instances of mpz or int.
Returns:: True if z is congruent to c modulo d, False otherwise.
Raises:: TypeError –

_gmp.gmpz.congruent_2exp_p(z, c, d)¶

Python wrapper for GNU MP mpz_congruent_2exp_p() function.

Parameters z, c, d:: z and c are either instances of mpz or int. d is a int that must fit into a C unsigned long.
Returns:: True if z is congruent to c modulo \(2^d\), False otherwise.
Raises:: TypeError –

_gmp.gmpz.jacobi(a, b)¶

Python wrapper for GNU MP mpz_jacobi() function.

Parameters a, b:: a and b are instances of mpz or int. b must be odd, otherwise ValueError is raised.
Returns:: The jacobi symbol \(\left(\dfrac{a}{b}\right)\) of a and b.
Raises:: TypeError, ValueError –

_gmp.gmpz.legendre(a, b)¶

Python wrapper for GNU MP mpz_legendre() function.

Parameters a, b:: a and b are instances of mpz or int. b must be an odd positive prime, otherwise ValueError is raised.
Returns:: The legendre symbol \(\left(\dfrac{a}{b}\right)\) of a and b.
Raises:: TypeError, ValueError –

_gmp.gmpz.kronecker(a, b)¶

Python wrapper for GNU MP mpz_kronecker(), mpz_kronecker_si(), mpz_kronecker_ui(), mpz_si_kronecker() and mpz_ui_kronecker() functions.

Parameters a, b:: a and b are instances of mpz or int.
Returns:: The kronecker symbol \(\left(\dfrac{a}{b}\right)\) of a and b.
Raises:: TypeError –

_gmp.gmpz.invert(a, b)¶

Python wrapper for GNU MP mpz_invert() function.

Parameters a, b:: a and b are instances of mpz or int . b cannot be zero, otherwise ValueError is raised.
Returns:: The inverse of a modulo b or None if it does not exist.`
Raises:: TypeError, ValueError –

Some examples:

>>> z = mpz(2026)
>>> print(invert(1013, z))
None
>>> print(invert(-11, z))
1105

_gmp.gmpz.fac_ui(n)¶

Python wrapper for GNU MP mpz_fac_ui() function.

Parameters n:: a int that must fit into a C unsigned long.
Returns:: \(n!\), the factorial of n.
Raises:: TypeError –

_gmp.gmpz.fac2_ui(n)¶

Python wrapper for GNU MP mpz_2fac_ui() function.

Parameters n:: a int that must fit into a C unsigned long.
Returns:: \(n!!\), the double factorial of n.
Raises:: TypeError –

_gmp.gmpz.mfac_uiui(n, m)¶

Python wrapper for GNU MP mpz_mfac_uiui() function.

Parameters n, m:: two instances of int that must fit into a C unsigned long.
Returns:: \(n!^{(m)}\), the m-multi-factorial of n.
Raises:: TypeError –

_gmp.gmpz.primorial_ui(n)¶

Python wrapper for GNU MP mpz_primorial_ui() function.

Parameters n:: a int that must fit into a C unsigned long.
Returns:: \(n\sharp\), the product of all positive prime numbers \(\leq\) n.
Raises:: TypeError –

>>> print(primorial_ui(10))
210 # 2*3*5*7

_gmp.gmpz.bin_ui(n, k)¶

Python wrapper for GNU MP mpz_bin_ui() and mpz_bin_uiui() functions.

Parameters n, k:: n is a mpz or a int that must fit into a C unsigned long. k is int that must fit into a C unsigned long.
Returns:: The binomial coefficient \(\binom{n}{k}\).
Raises:: TypeError, OverflowError –

_gmp.gmpz.remove(z1, z2)¶

Python wrapper for GNU MP mpz_remove() function.

Parameters z1, z2:: z1 and z2 are either instances of mpz or int.
Returns:: (z, occ) where z is the number z1 in which all occurrences of the factor z2 have been removed and occ is the number of these occurrences.
Raises:: TypeError –

>>> print(remove(1728, 2))
(27, 6)

_gmp.gmpz.hamdist(z1, z2)¶

Python wrapper for GNU MP mpz_hamdist() function.

Parameters z1, z2:: z1 and z2 are either instances of mpz or int.
Returns:: The hamming distance between z1 and z2.
Raises:: TypeError –

Random Number Functions¶

Note

GMP random number functions use a variable of type gmp_randstate_t which holds an algorithm selection and a current state. Such a global (and internal) state variable is initialized during _gmp.gmpz module initialization via the GMP function gmp_randinit_default().

_gmp.gmpz.randseed_ui()¶

Python wrapper for GNU MP mpz_randseed_ui() function. Set an initial seed value.

Returns:: Ǹone

If the special file /dev/random exists on the operating system, seed will be extracted from it. Otherwise, it will be the system’s time that will be used (less secure).

_gmp.gmpz.urandomb_ui(n)¶

Python wrapper for GNU MP mpz_urandomb_ui() function.

Parameters n:: A int that must be <= (sizeof(unsigned long) << 3), otherwise ValueError is raised.
Returns:: A random number (int) of n bits.
Raises:: TypeError, ValueError –

_gmp.gmpz.urandomm_ui(n)¶

Python wrapper for GNU MP mpz_urandomm_ui() function.

Parameters n:: A int that must fit into a unsigned long, otherwise TypeError is raised.
Returns:: A random number (int) in range \([0, n-1]\).
Raises:: TypeError –

Some examples:

>>> randseed_ui()
>>> print(urandomb_ui(64))
3049390686714079220 # random number of 64 bits
>>> print(urandomm_ui(64))
48                  # random number in interval [0, 63]

Exceptions¶

exception _gmp.gmpz.GMPZError¶

Module _gmp.gmpz¶

GMP Integers¶

Object mpz¶

Properties of the mpz object¶

Operators¶

Number Theoretic Functions¶

Bitwise Operations¶

Other Bitwise Operations¶

Miscellaneous methods¶

Comparisons and Booleans¶

Attributes¶

Module Methods¶

Random Number Functions¶

Exceptions¶

Table of Contents

Previous topic

Next topic

This Page