📄 bignum.h
字号:
MP_ERRNO_PADINFO_INITIALIZATION_BAD_CUTOFF,
MP_ERRNO_RANDOM_DIGIT_INTERVAL_INVALID_PARAMETERS,
MP_ERRNO_RANDOM_MOD_INVALID_PARAMETERS,
MP_ERRNO_RANDOM_MOD_INVERSE_NOT_PRIME,
MP_ERRNO_RANDOM_MOD_NONZERO_INVALID_PARAMETERS,
MP_ERRNO_SELECT_A0B0_BAD_COFACTOR,
MP_ERRNO_SELECT_A0B0_BAD_MU,
MP_ERRNO_SELECT_A0B0_NON_CONSTANT_QUOTIENT,
MP_ERRNO_SELECT_A0B0_NONZERO_REMAINDER,
MP_ERRNO_SELECT_CURVE_BAD_FIELD_TYPE,
MP_ERRNO_SELECT_D_UNSUCCESSFUL,
MP_ERRNO_TO_KARA_INVALID_LENGTH,
MP_ERRNO_TO_KARA2_INVALID_LENGTH,
MP_ERRNO_COUNT // Number of entries above
} mp_errno_t;
exportable_var mp_errno_t mp_errno;
#define inadequate_memory (mp_errno == MP_ERRNO_NO_MEMORY)
extern const char* mp_errno_name(const mp_errno_t);
// Update table in mperrnam.c when adding new error message
/*
Some routine allow an argument of digit_NULL or
reciprocal_1_NULL when the corresponding argument
is not otherwise used. For example, the division
routine allows but does not require a
reciprocal structure as argument,
and allows the quotient to be suppressed.
*/
#define digit_NULL ((digit_t*)0)
#define reciprocal_1_NULL ((reciprocal_1_t*)0)
#define modmultemp_NULL ((modmultemp_t*)0)
/*
The next several #defines are used in function prototypes.
*/
#define MP_INPUT digit_tc[]
#define MP_OUTPUT digit_t[]
#define MP_MODIFIED digit_t[]
#define DIFS_INPUT MP_INPUT
#define DIFS_OUTPUT MP_OUTPUT
#define DIFS_MODIFIED MP_MODIFIED
#define SIGNS_INPUT kara_sign_tc[]
#define SIGNS_MODIFIED kara_sign_t[]
#define SIGNS_OUTPUT kara_sign_t[]
extern digit_t accumulate(MP_INPUT, digit_tc, MP_MODIFIED, DWORDC);
extern digit_t Stdcall86 add_diff(MP_INPUT, DWORDC, MP_INPUT, DWORDC, MP_OUTPUT);
extern DWORD add_full(MP_INPUT, DWORDC, MP_INPUT, DWORDC, MP_OUTPUT);
extern digit_t Stdcall86 add_same(MP_INPUT, MP_INPUT, MP_OUTPUT, DWORDC);
extern DWORD add_signed(MP_INPUT, DWORDC, MP_INPUT, DWORDC, MP_OUTPUT);
extern int compare_diff(MP_INPUT, DWORDC, MP_INPUT, DWORDC);
extern int compare_sum_diff(MP_INPUT, DWORDC, MP_INPUT, DWORDC, MP_INPUT, DWORDC);
BOOL create_modulus(MP_INPUT, DWORDC, reddir_tc, mp_modulus_t*);
extern dblint_t dblint_gcd(dblint_tc, dblint_tc);
extern dblint_t dblint_ogcd(dblint_tc, dblint_tc);
extern digit_t dblint_sqrt(dblint_tc);
extern digit_t decumulate(MP_INPUT, digit_tc, MP_MODIFIED, DWORDC);
extern DWORD digit_factor(digit_tc, digit_t[], DWORD[]);
extern digit_t digit_gcd(digit_tc, digit_tc);
extern int digit_jacobi(digit_tc, digit_tc);
extern digit_t digit_least_prime_divisor(digit_tc);
extern digit_t digit_mod_divide_odd(digit_tc, digit_tc, digit_tc);
extern digit_t digit_ogcd(digit_tc, digit_tc);
extern char* digit_out(digit_tc);
extern digit_t digit_sqrt(digit_tc);
extern void div21(dblint_tc, digit_tc, digit_t*, digit_t*);
extern void div21_fast(dblint_tc, digit_tc,
reciprocal_1_tc*, digit_t*, digit_t*);
extern DWORD divide(MP_INPUT, DWORDC, MP_INPUT, DWORDC,
reciprocal_1_tc*, MP_OUTPUT, MP_OUTPUT);
extern DWORD divide_rounded(MP_INPUT, DWORDC, MP_INPUT, DWORDC,
reciprocal_1_tc*, MP_OUTPUT, MP_OUTPUT);
extern void divide_precondition_1(MP_INPUT, DWORDC, reciprocal_1_t*);
extern digit_t divide_immediate(MP_INPUT, digit_tc,
reciprocal_1_tc*, MP_OUTPUT, DWORDC);
extern digit_t estimated_quotient_1(digit_tc, digit_tc,
digit_tc, reciprocal_1_tc*);
extern BOOL find_big_prime(DWORDC, MP_INPUT, DWORDC,
MP_INPUT, DWORDC, MP_OUTPUT);
extern padinfo_tc *find_padinfo(DWORDC);
DWORD from_modular(MP_INPUT, MP_OUTPUT, mp_modulus_tc*);
extern int gcdex_jacobi(MP_INPUT, mp_modulus_tc*, MP_OUTPUT, MP_OUTPUT);
extern void mod_add(MP_INPUT, MP_INPUT, MP_OUTPUT, mp_modulus_tc*);
DWORD mod_exp(MP_INPUT, MP_INPUT, DWORDC, MP_OUTPUT,
mp_modulus_tc*);
extern DWORD mod_exp_immediate(MP_INPUT, digit_tc, MP_OUTPUT,
mp_modulus_tc*);
extern int mod_jacobi_immediate(const signed long, mp_modulus_tc*);
extern void mod_Lucas(MP_INPUT, MP_INPUT, DWORDC, MP_OUTPUT,
mp_modulus_tc*);
extern void mod_LucasUV(MP_INPUT, MP_INPUT, MP_INPUT, DWORDC,
MP_OUTPUT, MP_OUTPUT, mp_modulus_tc*);
extern void mod_mul(MP_INPUT, MP_INPUT, MP_OUTPUT,
mp_modulus_tc*, modmultemp_t*);
extern void mod_mul_immediate(MP_INPUT, digit_tc,
MP_OUTPUT, mp_modulus_tc*);
extern void mod_mul_kara1(MP_INPUT, DIFS_INPUT, SIGNS_INPUT,
MP_OUTPUT, mp_modulus_tc*, modmultemp_t*);
extern void mod_mul_kara(DIFS_INPUT, SIGNS_INPUT,
DIFS_INPUT, SIGNS_INPUT,
MP_OUTPUT, mp_modulus_tc*, modmultemp_t*);
extern void mod_negate(MP_INPUT, MP_OUTPUT, mp_modulus_tc*);
extern void mod_shift(MP_INPUT, intc, MP_OUTPUT, mp_modulus_tc*);
extern BOOL mod_sqrt(MP_INPUT, MP_OUTPUT, mp_modulus_tc*);
extern void mod_sub(MP_INPUT, MP_INPUT, MP_OUTPUT, mp_modulus_tc*);
extern BOOL modular_reduce(MP_INPUT, DWORDC, reddir_tc,
MP_OUTPUT, mp_modulus_tc*, modmultemp_t*);
extern void* mp_alloc_temp(DWORDC);
#define Allocate_Temporaries(typename, ptr) \
ptr = (typename*)mp_alloc_temp(sizeof(typename))
#define Allocate_Temporaries_Multiple(nelmt, typename, ptr) \
ptr = (typename*)mp_alloc_temp((nelmt)*sizeof(typename))
#if USEASM_ALPHA
extern void mp_copy(MP_INPUT, MP_OUTPUT, DWORDC);
#else
#define mp_copy(src, dest, lng) \
memcpy((void *)(dest), (const void *)(src), (lng)*sizeof(digit_t))
#endif
extern char* mp_decimal(MP_INPUT, DWORDC);
extern long mp_decimal_input(charc*, MP_OUTPUT, DWORDC, charc**);
extern char* mp_dword_decimal(DWORDC*, DWORDC);
extern int mp_format(MP_MODIFIED, DWORDC,
digit_tc, charc*, char*, DWORDC);
extern void mp_free_temp(void*);
#define Free_Temporaries(ptr) mp_free_temp((void*)ptr)
extern DWORD mp_gcd(MP_INPUT, DWORDC, MP_INPUT, DWORDC, MP_OUTPUT);
extern DWORD mp_gcdex(MP_INPUT, DWORDC, MP_INPUT, DWORDC,
MP_OUTPUT, MP_OUTPUT, MP_OUTPUT, MP_OUTPUT);
extern void mp_initialization(void);
extern void mp_longshift(MP_INPUT, intc, MP_OUTPUT, DWORDC);
extern digit_t mp_shift(MP_INPUT, intc, MP_OUTPUT, DWORDC);
extern DWORD mp_significant_bit_count(MP_INPUT, DWORDC);
extern BOOL mp_sqrt(MP_INPUT, MP_OUTPUT, DWORDC);
extern DWORD mp_trailing_zero_count(MP_INPUT, DWORDC);
extern void mul_kara(DIFS_INPUT, SIGNS_INPUT,
DIFS_INPUT, SIGNS_INPUT,
MP_OUTPUT, padinfo_tc*);
extern void mul_kara_know_low(DIFS_INPUT, SIGNS_INPUT,
DIFS_INPUT, SIGNS_INPUT,
MP_INPUT, MP_OUTPUT,
padinfo_tc*);
extern void mul_kara_squaring(MP_INPUT, DWORDC,
DIFS_MODIFIED, SIGNS_MODIFIED,
MP_OUTPUT, padinfo_tc*,
modmultemp_t*);
extern void multiply(MP_INPUT, DWORDC, MP_INPUT, DWORDC, MP_OUTPUT);
extern digit_t multiply_immediate(MP_INPUT, digit_tc, MP_OUTPUT, DWORDC);
extern void Stdcall86 multiply_low(MP_INPUT, MP_INPUT, MP_OUTPUT, DWORDC);
extern DWORD multiply_signed(MP_INPUT, DWORDC, MP_INPUT, DWORDC, MP_OUTPUT);
extern DWORD multiply_signed_immediate(MP_INPUT, DWORDC,
signed long, MP_OUTPUT);
#define PRIME_SIEVE_LENGTH 3000
#if (PRIME_SIEVE_LENGTH % 3 != 0)
#error "PRIME_SIEVE_LENGTH must be a multiple of 3"
#endif
extern digit_t next_prime(
digit_tc pstart,
digit_t *lpsievbeg,
digit_t sieve[PRIME_SIEVE_LENGTH],
digit_t *lpmax_sieved_squared
);
extern void padinfo_initialization(DWORDC);
extern BOOL probable_prime(MP_INPUT, DWORDC, MP_INPUT, DWORDC, DWORDC);
extern BOOL remove_small_primes(MP_INPUT, DWORDC, digit_tc,
digit_t[], DWORD[], DWORD*,
MP_OUTPUT, DWORD*);
#if USEASM_IX86
#pragma warning(disable : 4035) /* No return value */
static inline int significant_bit_count(digit_tc pattern)
{
_asm {
mov eax,pattern ; Nonzero pattern
bsr eax,eax ; eax = index of leftmost nonzero bit
; BSR is slow on Pentium
; but fast on Pentium Pro
add eax,1 ; Add one to get significant bit count
}
}
#pragma warning(default : 4035)
#elif USEASM_ALPHA
extern const BYTE half_byte_significant_bit_count[128]; /* See mpmisc.c */
/*
The Alpha code uses the CMPBGE instruction to
identify which bytes are nonzero. The most significant
bit must occur within the leftmost nonzero byte.
We use the CMPBGE output to identify which byte that is.
After we extract that byte, we identify its most significant bit.
*/
static inline int significant_bit_count(digit_tc pattern)
{
intc zero_byte_pattern = __asm("cmpbge zero, %0, v0", pattern);
intc byte_offset_plus_1
= 8*half_byte_significant_bit_count[127 - (zero_byte_pattern >> 1)] + 1;
return byte_offset_plus_1
+ half_byte_significant_bit_count[pattern >> byte_offset_plus_1];
}
#else
extern int significant_bit_count(digit_tc);
#endif
extern digit_t Stdcall86 sub_diff(MP_INPUT, DWORDC, MP_INPUT, DWORDC, MP_OUTPUT);
extern digit_t Stdcall86 sub_same(MP_INPUT, MP_INPUT, MP_OUTPUT, DWORDC);
#define sub_signed(a, lnga, b, lngb, c) add_signed(a, lnga, b, -(lngb), c)
BOOL test_primality(MP_INPUT, DWORDC);
BOOL test_primality_check_low(MP_INPUT, DWORDC);
BOOL get_prime(MP_OUTPUT, DWORDC);
BOOL get_generator(DWORD*, DWORD*, DWORDC);
extern void to_kara(MP_INPUT, DWORDC, DIFS_OUTPUT, SIGNS_OUTPUT,
padinfo_tc*);
BOOL to_modular(MP_INPUT, DWORDC, MP_OUTPUT, mp_modulus_tc*);
static inline int trailing_zero_count(digit_tc); /* this file */
typedef void Stdcall86 vmul_t(DIFS_INPUT, DIFS_INPUT, DIFS_OUTPUT, DWORDC);
exportable_var vmul_t *vmulnn[VMUL_MAX_LNG_SINGLE];
/* Addresses for 1 x 1 to 12 x 12 products */
/* Defined at end of vmul.c */
#if PRINT_ERROR_MESSAGES
extern void mp_display(FILE*, charc*, MP_INPUT, DWORDC);
exportable_var FILE* mp_errfil; /* Set to stdout in mp_globals */
#endif /* PRINT_ERROR_MESSAGES */
/****************************************************************************/
static inline digit_t add_immediate(digit_tc a[],
digit_tc iadd,
digit_t b[],
DWORDC lng)
/*
Compute b = a + iadd, where iadd has length 1.
Both a and b have length lng.
Function value is carry out of leftmost digit in b.
*/
{
if (lng == 0) {
return iadd;
} else if (a == b && b[0] <= RADIXM1 - iadd) {
b[0] += iadd;
return 0;
} else {
return add_diff(a, lng, &iadd, 1, b);
}
}
/***************************************************************************/
static inline int compare_immediate(digit_tc a[],
digit_tc ivalue,
DWORDC lng)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -