|
Polly 20.0.0git
|
#include <limits.h>#include <stdbool.h>#include <stdint.h>Go to the source code of this file.
Classes | |
| struct | mpz_t |
Macros | |
| #define | MP_DIGIT_MAX (UINT32_MAX * UINT64_C(1)) |
| #define | MP_WORD_MAX (UINT64_MAX) |
| #define | MP_DIGIT_BIT (sizeof(mp_digit) * CHAR_BIT) |
| #define | MP_WORD_BIT (sizeof(mp_word) * CHAR_BIT) |
| #define | MP_SMALL_MIN LONG_MIN |
| #define | MP_SMALL_MAX LONG_MAX |
| #define | MP_USMALL_MAX ULONG_MAX |
| #define | MP_MIN_RADIX 2 |
| #define | MP_MAX_RADIX 36 |
Typedefs | |
| typedef unsigned char | mp_sign |
| typedef unsigned int | mp_size |
| typedef int | mp_result |
| typedef long | mp_small |
| typedef unsigned long | mp_usmall |
| typedef uint32_t | mp_digit |
| typedef uint64_t | mp_word |
| typedef struct mpz_t * | mp_int |
Functions | |
| static mp_digit * | MP_DIGITS (mp_int Z) |
| static mp_size | MP_ALLOC (mp_int Z) |
| static mp_size | MP_USED (mp_int Z) |
| static mp_sign | MP_SIGN (mp_int Z) |
| void | mp_int_default_precision (mp_size ndigits) |
Sets the default number of digits allocated to an mp_int constructed by mp_int_init_size() with prec == 0. | |
| void | mp_int_multiply_threshold (mp_size ndigits) |
| Sets the number of digits below which multiplication will use the standard quadratic "schoolbook" multiplication algorithm rather than Karatsuba-Ofman. | |
| static bool | mp_int_is_odd (mp_int z) |
Reports whether z is odd, having remainder 1 when divided by 2. | |
| static bool | mp_int_is_even (mp_int z) |
Reports whether z is even, having remainder 0 when divided by 2. | |
| mp_result | mp_int_init (mp_int z) |
Initializes z with 1-digit precision and sets it to zero. | |
| mp_int | mp_int_alloc (void) |
Allocates a fresh zero-valued mpz_t on the heap, returning NULL in case of error. | |
| mp_result | mp_int_init_size (mp_int z, mp_size prec) |
Initializes z with at least prec digits of storage, and sets it to zero. | |
| mp_result | mp_int_init_copy (mp_int z, mp_int old) |
Initializes z to be a copy of an already-initialized value in old. | |
| mp_result | mp_int_init_value (mp_int z, mp_small value) |
Initializes z to the specified signed value at default precision. | |
| mp_result | mp_int_init_uvalue (mp_int z, mp_usmall uvalue) |
Initializes z to the specified unsigned value at default precision. | |
| mp_result | mp_int_set_value (mp_int z, mp_small value) |
Sets z to the value of the specified signed value. | |
| mp_result | mp_int_set_uvalue (mp_int z, mp_usmall uvalue) |
Sets z to the value of the specified unsigned value. | |
| void | mp_int_clear (mp_int z) |
Releases the storage used by z. | |
| void | mp_int_free (mp_int z) |
Releases the storage used by z and also z itself. | |
| mp_result | mp_int_copy (mp_int a, mp_int c) |
Replaces the value of c with a copy of the value of a. | |
| void | mp_int_swap (mp_int a, mp_int c) |
Swaps the values and storage between a and c. | |
| void | mp_int_zero (mp_int z) |
Sets z to zero. | |
| mp_result | mp_int_abs (mp_int a, mp_int c) |
Sets c to the absolute value of a. | |
| mp_result | mp_int_neg (mp_int a, mp_int c) |
Sets c to the additive inverse (negation) of a. | |
| mp_result | mp_int_add (mp_int a, mp_int b, mp_int c) |
Sets c to the sum of a and b. | |
| mp_result | mp_int_add_value (mp_int a, mp_small value, mp_int c) |
Sets c to the sum of a and value. | |
| mp_result | mp_int_sub (mp_int a, mp_int b, mp_int c) |
Sets c to the difference of a less b. | |
| mp_result | mp_int_sub_value (mp_int a, mp_small value, mp_int c) |
Sets c to the difference of a less value. | |
| mp_result | mp_int_mul (mp_int a, mp_int b, mp_int c) |
Sets c to the product of a and b. | |
| mp_result | mp_int_mul_value (mp_int a, mp_small value, mp_int c) |
Sets c to the product of a and value. | |
| mp_result | mp_int_mul_pow2 (mp_int a, mp_small p2, mp_int c) |
Sets c to the product of a and 2^p2. | |
| mp_result | mp_int_sqr (mp_int a, mp_int c) |
Sets c to the square of a. | |
| mp_result | mp_int_div (mp_int a, mp_int b, mp_int q, mp_int r) |
Sets q and r to the quotent and remainder of a / b. | |
| mp_result | mp_int_div_value (mp_int a, mp_small value, mp_int q, mp_small *r) |
Sets q and *r to the quotent and remainder of a / value. | |
| mp_result | mp_int_div_pow2 (mp_int a, mp_small p2, mp_int q, mp_int r) |
Sets q and r to the quotient and remainder of a / 2^p2. | |
| mp_result | mp_int_mod (mp_int a, mp_int m, mp_int c) |
Sets c to the remainder of a / m. | |
| mp_result | mp_int_expt (mp_int a, mp_small b, mp_int c) |
Sets c to the value of a raised to the b power. | |
| mp_result | mp_int_expt_value (mp_small a, mp_small b, mp_int c) |
Sets c to the value of a raised to the b power. | |
| mp_result | mp_int_expt_full (mp_int a, mp_int b, mp_int c) |
Sets c to the value of a raised to the b power. | |
| static mp_result | mp_int_mod_value (mp_int a, mp_small value, mp_small *r) |
Sets *r to the remainder of a / value. | |
| int | mp_int_compare (mp_int a, mp_int b) |
Returns the comparator of a and b. | |
| int | mp_int_compare_unsigned (mp_int a, mp_int b) |
Returns the comparator of the magnitudes of a and b, disregarding their signs. | |
| int | mp_int_compare_zero (mp_int z) |
Returns the comparator of z and zero. | |
| int | mp_int_compare_value (mp_int z, mp_small v) |
Returns the comparator of z and the signed value v. | |
| int | mp_int_compare_uvalue (mp_int z, mp_usmall uv) |
Returns the comparator of z and the unsigned value uv. | |
| bool | mp_int_divisible_value (mp_int a, mp_small v) |
Reports whether a is divisible by v. | |
| int | mp_int_is_pow2 (mp_int z) |
Returns k >= 0 such that z is 2^k, if such a k exists. | |
| mp_result | mp_int_exptmod (mp_int a, mp_int b, mp_int m, mp_int c) |
Sets c to the value of a raised to the b power, reduced modulo m. | |
| mp_result | mp_int_exptmod_evalue (mp_int a, mp_small value, mp_int m, mp_int c) |
Sets c to the value of a raised to the value power, modulo m. | |
| mp_result | mp_int_exptmod_bvalue (mp_small value, mp_int b, mp_int m, mp_int c) |
Sets c to the value of value raised to the b power, modulo m. | |
| mp_result | mp_int_exptmod_known (mp_int a, mp_int b, mp_int m, mp_int mu, mp_int c) |
Sets c to the value of a raised to the b power, reduced modulo m, given a precomputed reduction constant mu defined for Barrett's modular reduction algorithm. | |
| mp_result | mp_int_redux_const (mp_int m, mp_int c) |
Sets c to the reduction constant for Barrett reduction by modulus m. | |
| mp_result | mp_int_invmod (mp_int a, mp_int m, mp_int c) |
Sets c to the multiplicative inverse of a modulo m, if it exists. | |
| mp_result | mp_int_gcd (mp_int a, mp_int b, mp_int c) |
Sets c to the greatest common divisor of a and b. | |
| mp_result | mp_int_egcd (mp_int a, mp_int b, mp_int c, mp_int x, mp_int y) |
Sets c to the greatest common divisor of a and b, and sets x and y to values satisfying Bezout's identity gcd(a, b) = ax + by. | |
| mp_result | mp_int_lcm (mp_int a, mp_int b, mp_int c) |
Sets c to the least common multiple of a and b. | |
| mp_result | mp_int_root (mp_int a, mp_small b, mp_int c) |
Sets c to the greatest integer not less than the bth root of a, using Newton's root-finding algorithm. | |
| static mp_result | mp_int_sqrt (mp_int a, mp_int c) |
Sets c to the greatest integer not less than the square root of a. | |
| mp_result | mp_int_to_int (mp_int z, mp_small *out) |
Returns MP_OK if z is representable as mp_small, else MP_RANGE. | |
| mp_result | mp_int_to_uint (mp_int z, mp_usmall *out) |
Returns MP_OK if z is representable as mp_usmall, or MP_RANGE. | |
| mp_result | mp_int_to_string (mp_int z, mp_size radix, char *str, int limit) |
Converts z to a zero-terminated string of characters in the specified radix, writing at most limit characters to str including the terminating NUL value. | |
| mp_result | mp_int_string_len (mp_int z, mp_size radix) |
Reports the minimum number of characters required to represent z as a zero-terminated string in the given radix. | |
| mp_result | mp_int_read_string (mp_int z, mp_size radix, const char *str) |
Reads a string of ASCII digits in the specified radix from the zero terminated str provided into z. | |
| mp_result | mp_int_read_cstring (mp_int z, mp_size radix, const char *str, char **end) |
Reads a string of ASCII digits in the specified radix from the zero terminated str provided into z. | |
| mp_result | mp_int_count_bits (mp_int z) |
Returns the number of significant bits in z. | |
| mp_result | mp_int_to_binary (mp_int z, unsigned char *buf, int limit) |
Converts z to 2's complement binary, writing at most limit bytes into the given buf. | |
| mp_result | mp_int_read_binary (mp_int z, unsigned char *buf, int len) |
Reads a 2's complement binary value from buf into z, where len is the length of the buffer. | |
| mp_result | mp_int_binary_len (mp_int z) |
Returns the number of bytes to represent z in 2's complement binary. | |
| mp_result | mp_int_to_unsigned (mp_int z, unsigned char *buf, int limit) |
Converts the magnitude of z to unsigned binary, writing at most limit bytes into the given buf. | |
| mp_result | mp_int_read_unsigned (mp_int z, unsigned char *buf, int len) |
Reads an unsigned binary value from buf into z, where len is the length of the buffer. | |
| mp_result | mp_int_unsigned_len (mp_int z) |
Returns the number of bytes required to represent z as an unsigned binary value in base 256. | |
| const char * | mp_error_string (mp_result res) |
Returns a pointer to a brief, human-readable, zero-terminated string describing res. | |
Variables | |
| const mp_result | MP_OK |
| const mp_result | MP_FALSE |
| const mp_result | MP_TRUE |
| const mp_result | MP_MEMORY |
| const mp_result | MP_RANGE |
| const mp_result | MP_UNDEF |
| const mp_result | MP_TRUNC |
| const mp_result | MP_BADARG |
| const mp_result | MP_MINERR |
| const mp_sign | MP_NEG |
| A sign indicating a (strictly) negative value. | |
| const mp_sign | MP_ZPOS |
| A sign indicating a zero or positive value. | |
| #define MP_DIGIT_BIT (sizeof(mp_digit) * CHAR_BIT) |
Definition at line 81 of file imath/imath.h.
| #define MP_DIGIT_MAX (UINT32_MAX * UINT64_C(1)) |
Definition at line 54 of file imath/imath.h.
| #define MP_MAX_RADIX 36 |
Definition at line 88 of file imath/imath.h.
| #define MP_MIN_RADIX 2 |
Definition at line 87 of file imath/imath.h.
| #define MP_SMALL_MAX LONG_MAX |
Definition at line 84 of file imath/imath.h.
| #define MP_SMALL_MIN LONG_MIN |
Definition at line 83 of file imath/imath.h.
| #define MP_USMALL_MAX ULONG_MAX |
Definition at line 85 of file imath/imath.h.
| #define MP_WORD_BIT (sizeof(mp_word) * CHAR_BIT) |
Definition at line 82 of file imath/imath.h.
| #define MP_WORD_MAX (UINT64_MAX) |
Definition at line 55 of file imath/imath.h.
| typedef uint32_t mp_digit |
Definition at line 52 of file imath/imath.h.
| typedef int mp_result |
Definition at line 40 of file imath/imath.h.
| typedef unsigned char mp_sign |
Definition at line 38 of file imath/imath.h.
| typedef unsigned int mp_size |
Definition at line 39 of file imath/imath.h.
| typedef long mp_small |
Definition at line 41 of file imath/imath.h.
| typedef unsigned long mp_usmall |
Definition at line 42 of file imath/imath.h.
| typedef uint64_t mp_word |
Definition at line 53 of file imath/imath.h.
Definition at line 67 of file imath/imath.h.
References mpz_t::alloc.
Referenced by mp_int_random(), s_pad(), and s_udiv_knuth().
Definition at line 66 of file imath/imath.h.
References mpz_t::digits.
Referenced by CLAMP(), export(), get_long_bits(), import(), mp_int_add(), mp_int_clear(), mp_int_copy(), mp_int_init_copy(), mp_int_init_size(), mp_int_mul(), mp_int_read_binary(), mp_int_read_unsigned(), mp_int_sqr(), mp_int_sub(), mp_int_swap(), mp_int_to_int(), mp_int_to_uint(), s_2expt(), s_dadd(), s_ddiv(), s_dmul(), s_dp2k(), s_embar(), s_isp2(), s_pad(), s_qdiv(), s_qmul(), s_qsub(), s_tobin(), s_ucmp(), s_udiv_knuth(), UMUL(), and USQR().
| const char * mp_error_string | ( | mp_result | res | ) |
Returns a pointer to a brief, human-readable, zero-terminated string describing res.
The returned string is statically allocated and must not be freed by the caller.
Definition at line 1668 of file imath/imath.c.
References res, s_error_msg, and s_unknown_err.
Sets c to the absolute value of a.
Definition at line 516 of file imath/imath.c.
References a(), assert, mp_int_copy, MP_OK, MP_ZPOS, res, and mpz_t::sign.
Sets c to the sum of a and b.
Definition at line 537 of file imath/imath.c.
References a(), assert, b(), carry(), CLAMP(), cmp(), mpz_t::digits, MAX(), MP_DIGITS(), mp_int_zero, MP_MEMORY, MP_OK, MP_SIGN(), MP_USED(), s_pad(), s_uadd(), s_ucmp(), s_usub(), mpz_t::sign, and mpz_t::used.
Sets c to the sum of a and value.
Definition at line 594 of file imath/imath.c.
References a(), mp_int_add, MP_VALUE_DIGITS, and s_fake().
| mp_int mp_int_alloc | ( | void | ) |
Allocates a fresh zero-valued mpz_t on the heap, returning NULL in case of error.
The only possible error is out-of-memory.
Definition at line 378 of file imath/imath.c.
References mp_int_init.
Returns the number of bytes to represent z in 2's complement binary.
Definition at line 1620 of file imath/imath.c.
References mp_int_count_bits, mp_int_unsigned_len, and res.
| void mp_int_clear | ( | mp_int | z | ) |
Releases the storage used by z.
Definition at line 459 of file imath/imath.c.
References mpz_t::digits, MP_DIGITS(), s_free(), and mpz_t::single.
| int mp_int_compare_zero | ( | mp_int | z | ) |
Returns the comparator of z and zero.
Definition at line 1002 of file imath/imath.c.
References assert, mpz_t::digits, MP_SIGN(), MP_USED(), and MP_ZPOS.
Replaces the value of c with a copy of the value of a.
No new memory is allocated unless a has more significant digits than c has allocated.
Definition at line 476 of file imath/imath.c.
References a(), assert, COPY(), MP_DIGITS(), MP_MEMORY, MP_OK, MP_USED(), s_pad(), mpz_t::sign, and mpz_t::used.
Returns the number of significant bits in z.
Definition at line 1560 of file imath/imath.c.
References assert, mpz_t::digits, MP_DIGIT_BIT, and MP_USED().
| void mp_int_default_precision | ( | mp_size | ndigits | ) |
Sets the default number of digits allocated to an mp_int constructed by mp_int_init_size() with prec == 0.
Allocations are rounded up to multiples of this value. MP_DEFAULT_PREC is the default value. Requires ndigits > 0.
Definition at line 198 of file imath/imath.c.
References assert, default_precision, and size.
Sets q and r to the quotent and remainder of a / b.
Division by powers of 2 is detected and handled efficiently. The remainder is pinned to 0 <= r < b.
Either of q or r may be NULL, but not both, and q and r may not point to the same value.
Definition at line 774 of file imath/imath.c.
References a(), assert, b(), CLEANUP_TEMP, cmp(), CMPZ(), DECLARE_TEMP, mpz_t::digits, mp_int_copy, mp_int_zero, MP_NEG, MP_OK, MP_SIGN(), MP_UNDEF, MP_ZPOS, REQUIRE, res, s_isp2(), s_qdiv(), s_qmod(), s_ucmp(), s_udiv_knuth(), mpz_t::sign, and TEMP.
Sets q and r to the quotient and remainder of a / 2^p2.
This is a special case for division by powers of two that is more efficient than using ordinary division. Note that mp_int_div() will automatically handle this case, this function is for cases where you have only the exponent.
Definition at line 886 of file imath/imath.c.
References a(), assert, mp_int_copy, MP_OK, res, s_qdiv(), and s_qmod().
Sets q and *r to the quotent and remainder of a / value.
Division by powers of 2 is detected and handled efficiently. The remainder is pinned to 0 <= *r < b. Either of q or r may be NULL.
Definition at line 872 of file imath/imath.c.
References a(), CLEANUP_TEMP, DECLARE_TEMP, mp_int_div, mp_int_to_int, MP_OK, MP_VALUE_DIGITS, REQUIRE, s_fake(), and TEMP.
Reports whether a is divisible by v.
Definition at line 1327 of file imath/imath.c.
References a(), mp_int_div_value, and MP_OK.
Sets c to the greatest common divisor of a and b, and sets x and y to values satisfying Bezout's identity gcd(a, b) = ax + by.
It returns MP_UNDEF if the GCD is undefined, such as for example if a and b are both zero.
Definition at line 1211 of file imath/imath.c.
References a(), assert, b(), CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, MIN(), mp_int_abs, mp_int_add, mp_int_compare, mp_int_copy, mp_int_is_even(), mp_int_is_odd(), mp_int_set_value, mp_int_sub, mp_int_zero, MP_MEMORY, MP_OK, MP_UNDEF, MP_ZPOS, REQUIRE, res, s_dp2k(), s_qdiv(), s_qmul(), and TEMP.
Sets c to the value of a raised to the b power.
It returns MP_RANGE if b < 0.
Definition at line 901 of file imath/imath.c.
References a(), assert, b(), CLEANUP_TEMP, DECLARE_TEMP, mp_int_copy, mp_int_mul, mp_int_set_value, mp_int_sqr, MP_OK, MP_RANGE, REQUIRE, and TEMP.
Sets c to the value of a raised to the b power.
It returns MP_RANGE) if b < 0.
Definition at line 949 of file imath/imath.c.
References a(), assert, b(), CLEANUP_TEMP, DECLARE_TEMP, MP_DIGIT_BIT, mp_int_copy, mp_int_mul, mp_int_set_value, mp_int_sqr, MP_NEG, MP_OK, MP_RANGE, MP_SIGN(), MP_USED(), REQUIRE, and TEMP.
Sets c to the value of a raised to the b power.
It returns MP_RANGE if b < 0.
Definition at line 925 of file imath/imath.c.
References a(), assert, b(), CLEANUP_TEMP, DECLARE_TEMP, mp_int_mul, mp_int_set_value, mp_int_sqr, MP_OK, MP_RANGE, REQUIRE, and TEMP.
Sets c to the value of a raised to the b power, reduced modulo m.
It returns MP_RANGE if b < 0 or MP_UNDEF if m == 0.
Definition at line 1037 of file imath/imath.c.
References a(), assert, b(), CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, GROW(), m, mp_int_copy, mp_int_mod, MP_OK, MP_RANGE, MP_UNDEF, MP_USED(), REQUIRE, s_brmu(), s_embar(), and TEMP.
Sets c to the value of value raised to the b power, modulo m.
It returns MP_RANGE if b < 0 or MP_UNDEF if m == 0.
Definition at line 1075 of file imath/imath.c.
References b(), m, mp_int_exptmod, MP_VALUE_DIGITS, and s_fake().
Sets c to the value of a raised to the value power, modulo m.
It returns MP_RANGE if value < 0 or MP_UNDEF if m == 0.
Definition at line 1066 of file imath/imath.c.
References a(), m, mp_int_exptmod, MP_VALUE_DIGITS, and s_fake().
Sets c to the value of a raised to the b power, reduced modulo m, given a precomputed reduction constant mu defined for Barrett's modular reduction algorithm.
It returns MP_RANGE if b < 0 or MP_UNDEF if m == 0.
Definition at line 1084 of file imath/imath.c.
References a(), assert, b(), CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, GROW(), m, mp_int_copy, mp_int_mod, MP_OK, MP_RANGE, MP_UNDEF, MP_USED(), REQUIRE, s_embar(), and TEMP.
| void mp_int_free | ( | mp_int | z | ) |
Releases the storage used by z and also z itself.
This should only be used for z allocated by mp_int_alloc().
Definition at line 469 of file imath/imath.c.
References assert, and mp_int_clear.
Sets c to the greatest common divisor of a and b.
It returns MP_UNDEF if the GCD is undefined, such as for example if a and b are both zero.
Definition at line 1150 of file imath/imath.c.
References a(), assert, b(), CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, MIN(), mp_int_abs, mp_int_copy, mp_int_is_odd(), mp_int_neg, mp_int_sub, MP_MEMORY, MP_OK, MP_UNDEF, MP_ZPOS, REQUIRE, s_dp2k(), s_qdiv(), s_qmul(), and TEMP.
Initializes z with 1-digit precision and sets it to zero.
This function cannot fail unless z == NULL.
Definition at line 366 of file imath/imath.c.
References mpz_t::alloc, mpz_t::digits, MP_BADARG, MP_OK, MP_ZPOS, mpz_t::sign, mpz_t::single, and mpz_t::used.
Initializes z to be a copy of an already-initialized value in old.
The new copy does not share storage with the original.
Definition at line 408 of file imath/imath.c.
References assert, COPY(), default_precision, MAX(), MP_DIGITS(), mp_int_init, mp_int_init_size, MP_OK, MP_USED(), res, mpz_t::sign, and mpz_t::used.
Initializes z with at least prec digits of storage, and sets it to zero.
If prec is zero, the default precision is used. In either case the size is rounded up to the nearest multiple of the word size.
Definition at line 386 of file imath/imath.c.
References mpz_t::alloc, assert, default_precision, mpz_t::digits, MP_DIGITS(), mp_int_init, MP_MEMORY, MP_OK, MP_ZPOS, s_alloc(), s_round_prec(), mpz_t::sign, and mpz_t::used.
Initializes z to the specified unsigned value at default precision.
Definition at line 435 of file imath/imath.c.
References mp_int_init_copy, MP_VALUE_DIGITS, and s_ufake().
Initializes z to the specified signed value at default precision.
Definition at line 427 of file imath/imath.c.
References mp_int_init_copy, MP_VALUE_DIGITS, and s_fake().
Sets c to the multiplicative inverse of a modulo m, if it exists.
The least non-negative representative of the congruence class is computed.
It returns MP_UNDEF if the inverse does not exist, or MP_RANGE if a == 0 or m <= 0.
Definition at line 1118 of file imath/imath.c.
References a(), assert, CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, m, mp_int_compare_value, mp_int_copy, mp_int_egcd, mp_int_mod, mp_int_sub, MP_NEG, MP_OK, MP_RANGE, MP_SIGN(), MP_UNDEF, REQUIRE, and TEMP.
|
inlinestatic |
Reports whether z is even, having remainder 0 when divided by 2.
Definition at line 111 of file imath/imath.h.
References mpz_t::digits.
Referenced by find_prime(), mp_int_egcd(), and mp_int_find_prime().
|
inlinestatic |
Reports whether z is odd, having remainder 1 when divided by 2.
Definition at line 108 of file imath/imath.h.
References mpz_t::digits.
Referenced by mp_int_egcd(), and mp_int_gcd().
| int mp_int_is_pow2 | ( | mp_int | z | ) |
Returns k >= 0 such that z is 2^k, if such a k exists.
If no such k exists, the function returns -1.
Definition at line 1336 of file imath/imath.c.
Sets c to the least common multiple of a and b.
It returns MP_UNDEF if the LCM is undefined, such as for example if a and b are both zero.
Definition at line 1308 of file imath/imath.c.
References a(), assert, b(), CLEANUP_TEMP, DECLARE_TEMP, mp_int_copy, mp_int_div, mp_int_gcd, mp_int_mul, MP_OK, REQUIRE, and TEMP.
Sets c to the remainder of a / m.
The remainder is pinned to 0 <= c < m.
Definition at line 859 of file imath/imath.c.
References a(), CLEANUP_TEMP, CMPZ(), DECLARE_TEMP, m, mp_int_add, mp_int_copy, mp_int_div, MP_OK, REQUIRE, and TEMP.
Sets *r to the remainder of a / value.
The remainder is pinned to 0 <= r < value.
Definition at line 227 of file imath/imath.h.
References a(), and mp_int_div_value.
Sets c to the product of a and b.
Definition at line 665 of file imath/imath.c.
References a(), assert, b(), CLAMP(), default_precision, MAX(), MP_DIGITS(), mp_int_compare_zero, mp_int_zero, MP_MEMORY, MP_NEG, MP_OK, MP_SIGN(), MP_USED(), MP_ZPOS, p, s_alloc(), s_free(), s_kmul(), s_pad(), s_round_prec(), mpz_t::sign, mpz_t::used, and ZERO.
Sets c to the product of a and 2^p2.
Requires p2 >= 0.
Definition at line 724 of file imath/imath.c.
References a(), assert, mp_int_copy, MP_MEMORY, MP_OK, res, and s_qmul().
Sets c to the product of a and value.
Definition at line 715 of file imath/imath.c.
References a(), mp_int_mul, MP_VALUE_DIGITS, and s_fake().
| void mp_int_multiply_threshold | ( | mp_size | ndigits | ) |
Sets the number of digits below which multiplication will use the standard quadratic "schoolbook" multiplication algorithm rather than Karatsuba-Ofman.
Requires ndigits >= sizeof(mp_word).
Definition at line 206 of file imath/imath.c.
References assert, and multiply_threshold.
Referenced by main().
Sets c to the additive inverse (negation) of a.
Definition at line 526 of file imath/imath.c.
References a(), assert, CMPZ(), mp_int_copy, MP_OK, MP_SIGN(), res, and mpz_t::sign.
Reads a 2's complement binary value from buf into z, where len is the length of the buffer.
The contents of buf may be overwritten during processing, although they will be restored when the function returns.
Definition at line 1591 of file imath/imath.c.
References assert, MP_DIGIT_BIT, MP_DIGITS(), mp_int_zero, MP_MEMORY, MP_NEG, MP_OK, MP_SIGN(), s_2comp(), s_pad(), s_qmul(), and mpz_t::sign.
Reads a string of ASCII digits in the specified radix from the zero terminated str provided into z.
For values of radix > 10, the letters A..Z or a..z are accepted. Letters are interpreted without respect to case.
Leading whitespace is ignored, and a leading + or - is interpreted as a sign flag. Processing stops when a NUL or any other character out of range for a digit in the given radix is encountered.
If the whole string was consumed, MP_OK is returned; otherwise MP_TRUNC. is returned. If end is not NULL, *end is set to point to the first unconsumed byte of the input string (the NUL byte if the whole string was consumed). This emulates the behavior of the standard C strtol() function.
Requires MP_MIN_RADIX <= radix <= MP_MAX_RADIX.
Definition at line 1507 of file imath/imath.c.
References assert, CLAMP(), CMPZ(), mpz_t::digits, MP_MAX_RADIX, MP_MEMORY, MP_MIN_RADIX, MP_NEG, MP_OK, MP_TRUNC, MP_ZPOS, s_ch2val(), s_dadd(), s_dmul(), s_inlen(), s_pad(), mpz_t::sign, str, and mpz_t::used.
Reads a string of ASCII digits in the specified radix from the zero terminated str provided into z.
For values of radix > 10, the letters A..Z or a..z are accepted. Letters are interpreted without respect to case.
Leading whitespace is ignored, and a leading + or - is interpreted as a sign flag. Processing stops when a NUL or any other character out of range for a digit in the given radix is encountered.
If the whole string was consumed, MP_OK is returned; otherwise MP_TRUNC. is returned.
Requires MP_MIN_RADIX <= radix <= MP_MAX_RADIX.
Definition at line 1503 of file imath/imath.c.
References mp_int_read_cstring, and str.
Reads an unsigned binary value from buf into z, where len is the length of the buffer.
The contents of buf are not modified during processing.
Definition at line 1642 of file imath/imath.c.
References assert, MP_DIGIT_BIT, MP_DIGITS(), mp_int_zero, MP_MEMORY, MP_OK, s_pad(), and s_qmul().
Sets c to the reduction constant for Barrett reduction by modulus m.
Requires that c and m point to distinct locations.
Definition at line 1112 of file imath/imath.c.
Sets c to the greatest integer not less than the bth root of a, using Newton's root-finding algorithm.
It returns MP_UNDEF if a < 0 and b is even.
Definition at line 1346 of file imath/imath.c.
References a(), assert, b(), CLEANUP_TEMP, DECLARE_TEMP, mp_int_compare_unsigned, mp_int_copy, mp_int_div, mp_int_expt, mp_int_mul_value, mp_int_neg, mp_int_sub, mp_int_sub_value, MP_NEG, MP_OK, MP_SIGN(), MP_UNDEF, MP_ZPOS, REQUIRE, and TEMP.
Sets z to the value of the specified unsigned value.
Definition at line 451 of file imath/imath.c.
References mp_int_copy, MP_VALUE_DIGITS, and s_ufake().
Sets z to the value of the specified signed value.
Definition at line 443 of file imath/imath.c.
References mp_int_copy, MP_VALUE_DIGITS, and s_fake().
Sets c to the square of a.
Definition at line 737 of file imath/imath.c.
References a(), assert, CLAMP(), default_precision, MAX(), MP_DIGITS(), MP_MEMORY, MP_OK, MP_USED(), MP_ZPOS, p, s_alloc(), s_free(), s_ksqr(), s_pad(), s_round_prec(), mpz_t::sign, mpz_t::used, and ZERO.
Sets c to the greatest integer not less than the square root of a.
This is a special case of mp_int_root().
Definition at line 311 of file imath/imath.h.
References a(), and mp_int_root.
Referenced by cf_sqrt(), and test_sqrt().
Reports the minimum number of characters required to represent z as a zero-terminated string in the given radix.
Requires MP_MIN_RADIX <= radix <= MP_MAX_RADIX.
Definition at line 1490 of file imath/imath.c.
References assert, MP_MAX_RADIX, MP_MIN_RADIX, MP_NEG, MP_SIGN(), and s_outlen().
Sets c to the difference of a less b.
Definition at line 603 of file imath/imath.c.
References a(), assert, b(), carry(), CLAMP(), cmp(), mpz_t::digits, MAX(), MP_DIGITS(), MP_MEMORY, MP_NEG, MP_OK, MP_SIGN(), MP_USED(), MP_ZPOS, s_pad(), s_uadd(), s_ucmp(), s_usub(), mpz_t::sign, and mpz_t::used.
Sets c to the difference of a less value.
Definition at line 656 of file imath/imath.c.
References a(), mp_int_sub, MP_VALUE_DIGITS, and s_fake().
Swaps the values and storage between a and c.
Definition at line 496 of file imath/imath.c.
References a(), mpz_t::digits, MP_DIGITS(), and mpz_t::single.
Converts z to 2's complement binary, writing at most limit bytes into the given buf.
Returns MP_TRUNC if the buffer limit was too small to contain the whole value. If this occurs, the contents of buf will be effectively garbage, as the function uses the buffer as scratch space.
The binary representation of z is in base-256 with digits ordered from most significant to least significant (network byte ordering). The high-order bit of the first byte is set for negative values, clear for non-negative values.
As a result, non-negative values will be padded with a leading zero byte if the high-order byte of the base-256 magnitude is set. This extra byte is accounted for by the mp_int_binary_len() function.
Definition at line 1578 of file imath/imath.c.
References assert, MP_NEG, MP_SIGN(), res, s_2comp(), and s_tobin().
Returns MP_OK if z is representable as mp_small, else MP_RANGE.
If out is not NULL, *out is set to the value of z when MP_OK.
Definition at line 1393 of file imath/imath.c.
References assert, MP_DIGIT_BIT, MP_DIGITS(), mp_int_compare_value, MP_NEG, MP_OK, MP_RANGE, MP_SIGN(), MP_SMALL_MAX, MP_SMALL_MIN, MP_USED(), and MP_ZPOS.
Converts z to a zero-terminated string of characters in the specified radix, writing at most limit characters to str including the terminating NUL value.
A leading - is used to indicate a negative value.
Returns MP_TRUNC if limit was to small to write all of z. Requires MP_MIN_RADIX <= radix <= MP_MAX_RADIX.
Definition at line 1441 of file imath/imath.c.
References assert, cmp(), CMPZ(), mp_int_clear, mp_int_init_copy, MP_MAX_RADIX, MP_MIN_RADIX, MP_NEG, MP_OK, MP_SIGN(), MP_TRUNC, res, s_ddiv(), s_val2ch(), str, and t.
Returns MP_OK if z is representable as mp_usmall, or MP_RANGE.
If out is not NULL, *out is set to the value of z when MP_OK.
Definition at line 1417 of file imath/imath.c.
References assert, MP_DIGIT_BIT, MP_DIGITS(), mp_int_compare_uvalue, MP_NEG, MP_OK, MP_RANGE, MP_SIGN(), MP_USED(), and MP_USMALL_MAX.
Converts the magnitude of z to unsigned binary, writing at most limit bytes into the given buf.
The sign of z is ignored, but z is not modified. Returns MP_TRUNC if the buffer limit was too small to contain the whole value. If this occurs, the contents of buf will be effectively garbage, as the function uses the buffer as scratch space during conversion.
The binary representation of z is in base-256 with digits ordered from most significant to least significant (network byte ordering).
Definition at line 1634 of file imath/imath.c.
Returns the number of bytes required to represent z as an unsigned binary value in base 256.
Definition at line 1660 of file imath/imath.c.
References mp_int_count_bits, and res.
| void mp_int_zero | ( | mp_int | z | ) |
Sets z to zero.
The allocated storage of z is not changed.
Definition at line 508 of file imath/imath.c.
References assert, mpz_t::digits, MP_ZPOS, mpz_t::sign, and mpz_t::used.
Definition at line 69 of file imath/imath.h.
References mpz_t::sign.
Referenced by get_si(), mp_int_add(), mp_int_compare(), mp_int_compare_uvalue(), mp_int_compare_value(), mp_int_compare_zero(), mp_int_div(), mp_int_expt_full(), mp_int_invmod(), mp_int_mul(), mp_int_neg(), mp_int_read_binary(), mp_int_root(), mp_int_string_len(), mp_int_sub(), mp_int_to_binary(), mp_int_to_int(), mp_int_to_string(), mp_int_to_uint(), and s_embar().
Definition at line 68 of file imath/imath.h.
References mpz_t::used.
Referenced by CLAMP(), get_long_bits(), mp_int_add(), mp_int_compare_zero(), mp_int_copy(), mp_int_count_bits(), mp_int_expt_full(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_init_copy(), mp_int_mul(), mp_int_sqr(), mp_int_sub(), mp_int_to_int(), mp_int_to_uint(), s_brmu(), s_dadd(), s_ddiv(), s_dmul(), s_dp2k(), s_embar(), s_isp2(), s_norm(), s_qdiv(), s_qmod(), s_qmul(), s_reduce(), s_tobin(), s_ucmp(), s_udiv_knuth(), UMUL(), and USQR().
|
extern |
Definition at line 41 of file imath/imath.c.
Referenced by mp_int_init().
|
extern |
Definition at line 35 of file imath/imath.c.
|
extern |
Definition at line 37 of file imath/imath.c.
Referenced by GROW(), mp_int_add(), mp_int_copy(), mp_int_egcd(), mp_int_gcd(), mp_int_init_size(), mp_int_mul(), mp_int_mul_pow2(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_unsigned(), mp_int_sqr(), mp_int_sub(), s_brmu(), s_embar(), and s_udiv_knuth().
|
extern |
Definition at line 42 of file imath/imath.c.
|
extern |
A sign indicating a (strictly) negative value.
Definition at line 44 of file imath/imath.c.
Referenced by CMPZ(), mp_int_compare_uvalue(), mp_int_compare_value(), mp_int_div(), mp_int_expt_full(), mp_int_invmod(), mp_int_mul(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_root(), mp_int_string_len(), mp_int_sub(), mp_int_to_binary(), mp_int_to_int(), mp_int_to_string(), mp_int_to_uint(), and s_fake().
|
extern |
Definition at line 34 of file imath/imath.c.
Referenced by GROW(), mp_int_abs(), mp_int_add(), mp_int_copy(), mp_int_div(), mp_int_div_pow2(), mp_int_div_value(), mp_int_divisible_value(), mp_int_egcd(), mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_init(), mp_int_init_copy(), mp_int_init_size(), mp_int_invmod(), mp_int_lcm(), mp_int_mod(), mp_int_mul(), mp_int_mul_pow2(), mp_int_neg(), mp_int_read_binary(), mp_int_read_cstring(), mp_int_read_unsigned(), mp_int_root(), mp_int_sqr(), mp_int_sub(), mp_int_to_int(), mp_int_to_string(), mp_int_to_uint(), s_embar(), s_reduce(), s_tobin(), and s_udiv_knuth().
|
extern |
Definition at line 38 of file imath/imath.c.
Referenced by mp_int_expt(), mp_int_expt_full(), mp_int_expt_value(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_invmod(), mp_int_to_int(), and mp_int_to_uint().
|
extern |
Definition at line 36 of file imath/imath.c.
|
extern |
Definition at line 40 of file imath/imath.c.
Referenced by mp_int_read_cstring(), mp_int_to_string(), and s_tobin().
|
extern |
Definition at line 39 of file imath/imath.c.
Referenced by mp_int_div(), mp_int_egcd(), mp_int_exptmod(), mp_int_exptmod_known(), mp_int_gcd(), mp_int_invmod(), and mp_int_root().
|
extern |
A sign indicating a zero or positive value.
Definition at line 45 of file imath/imath.c.
Referenced by mp_int_abs(), mp_int_compare(), mp_int_compare_value(), mp_int_compare_zero(), mp_int_div(), mp_int_egcd(), mp_int_gcd(), mp_int_init(), mp_int_init_size(), mp_int_mul(), mp_int_read_cstring(), mp_int_root(), mp_int_sqr(), mp_int_sub(), mp_int_to_int(), mp_int_zero(), s_embar(), s_qdiv(), s_qsub(), s_udiv_knuth(), and s_ufake().
1.9.6