Bifroest	Mr. Tines	CTC Home	CTClib	MacCTC	CTCjava	Manual

Bignums Module

This module consists of the following files:-

• bignums.h: Header file
• bignums.c: Source file

CTC Bignums

1. It handles only non-negative integers.
2. It is primarily concerned with (and optimised for) modular arithmetic.
3. It does not handle short integers efficiently.
4. Whereas the library does have maximum number size limits, these are not generally tested for. (The limit is unlikely to be less that half a million bits. There is a rather more stringent limit of 65535 bits as the maximum length of integer that the PGP file format is capable of representing.)

Many routines return booleans indicating success. In the case of any of these routines failing it is due to failure to allocated memory. mod_power_mpn alone can also fail due to a user interrupt.

Internally the package is written to execute modular arithmetic efficently. Specifically it executes all modular operations without generating any intermediate results greatly longer than the modulus.

Formats

Internal

This is the Bignums' nature format in which it performs all arithmetic. This consists of the data-types described later.

External

This is the PGP file format for Multiple Precision Numbers. This is byte oriented and big-endian. A number consists of a two bytes length specifying the length of the number in bits, followed immediately by the minimum number of bytes that will hold that number of bits.

uint16_t arrays

These consists of arrays of unsigned 2-byte integers.  The number in this form may omit any number of zero bits at the bottom (least significant) end of the number.  These are arrays used by the PEGWIT eliptic curve code.

Hexadecimal

This is a C-style (null terminated) character string containing the number in hexadecimal. CTC does not use this format, except for test purposes.  Note that when generating such values CTC is inclined to include a number of leading zeros.

Data Types

mp_number

mp_number is private structure containing an arbituary sized integer. Calling programs should not declare objects of this type (only pointers to it).

bignum

This type is a pointer to an mp_number. This type is the normal type used in calling programs. Conceptually this type is a big-number. Some operations (which are guaranteed not to extend the number) may use this type for output arguments, but in generally this is used for input arguments.

 

 

Note that a bignum must be initialised by init_mpn before calling any other routine with it. Failure to do so may result in a program crash.

bignump

This type is a pointer to an bignum  (a pointer to a pointer). This type is normally used to return value from any routine where the length of the value may be extended. The majority of bignump arguments must be valid pointers to pre-initialised bignum values. However there are a few exceptions where this may be replace by NULL to indicate the value that would be returned is not required. NULLs are only valid where it is explicitly stated.

Macros

EXTRACT_SHORT(x)

This macro extracts an unsigned short (2-byte integer) from a network-order (a big-endian) character buffer.

EXTRACT_LONG(x)

This macro extracts an unsigned long (4-byte integer) from a network-order (a big-endian) character buffer.

Functions

Storage Management

void init_mpn(bignump num);

This routine initialises the bignum pointed to by num. This routine must be called for all bignums before they are used in any other routine. However init_mpn should not be called on an already initialised bignum as this would lose the already allocated storage.

 

 

It is not recommended to rely on initialisation being setting to NULL, although there may be a few places in the CTC library where this is currently relied on.

void clear_mpn(bignump num);

All initialise bignums must have there storage released with clear_mpn before they go out of scope

void wipe_mpn(bignump internal);

As for clear_mpn except that the storage is zeroed before it released.

 

 
 
 

Input and Output

ushort byte_length(byte * number);

where number is the address of a character buffer containing a number in PGP file format. It returns the length of the number in bytes.

boolean get_mpn(bignump internal, byte * external);

Reads an external format number from external and returns the number as internal. It returns FALSE if storage allocation is necessary and fails.

short put_mpn(byte * external, bignump internal);

This function writes the value in internal to external in PGP file format and returns the number of bytes in the number. The number of bytes written to externalis two greater than this as it includes the two-byte length field. It is the caller responsibility to ensure that the buffer pointed to by external is large enough, if necessary using byte_length() to determine the necessary buffer size.

boolean read_mpn(char * input, bignump number);

This function reads the null terminated hexadecimal number from input and places the value in number. It will return false if the storage allocation fails, or if any character other than a hexadecimal digit is found in the input string. This function is case insensitive.

void format_mpn(char * output, bignum number);

This function writes number into the buffer pointed to by output. This will include a terminating null-character and may include a number of leading zeros. (With a 4-byte integer implementation there may be up to 7 leading zeros.)

boolean set_mpn(uint32_t value, bignump number);

This function sets the value of number to value. If returns TRUE is successful.

Arithmetic

common_error mod_power_mpn(bignump result, bignum multi, bignum expon, bignum modulus);

This function calculates multi raised to the power of expon, modulo modulus. The returned value indicates whether the result was success and if not whether memory-allocation failure or a user interrupt prevented the calculation completing. This routine does all the necessary storage allocation before embarking on the calculation so in the case of memory-allocation failure the function should return immediately. Where successful result of this calculation is returned as result.

void remainder_mpn(bignum result, bignum modulus, boolean minus1);

This function calculates result modulo modulus and returns the result in result, where minus1 is false. Where minus1 is true, the calculation is performed modulo (modulus - 1). However this is only guaranteed to work where modulus is odd. (The minus1 argument is included to simplify a number of operations with RSA private keys where operations must be done modulo a prime number minus 1.) As result cannot increase in size in during this operation, no storage is ever allocated and the operation cannot fail.

ushort mod_short(bignum number, ushort modulus)

This function calculates and returns number modulo modulus.

boolean divide_mpn(bignump quotient, bignump remainder, bignum numerator, bignum denominator);

This function attempts to divide numerator by denominator and returns true if successful. If successful quotient is set to the quotient and remainder is set to the remainder. The remainder argument may be NULL if this value is not required.

boolean add_mpn(bignump result, bignum add);

This function adds the values of the two arguments to together and returns the result as result. It returns TRUE if successful.

boolean multiply_mpn(bignump result, bignum left, bignum right);

This function calculates the product of left & right and returns the result in result. It returns TRUE if successful.

void subtract_mpn(bignum result, bignum minus);

This function subtracts the value in minus from result returning the result in result.

boolean HCF(bignump result, bignum left, bignum right);

This function calculates the Highest Common Factor of left & right and returns the result in result. It returns TRUE if successful.

 

 
 
 

Miscellaneous

boolean sieve(bignum number);

Returns true if could be a prime. This is a simple prime number sieve using the first few hundred prime numbers.

ushort length_mpn(bignum number);

Returns the length of the number in bits.

short size_mpn(bignum internal);

Returns the length of the number in bytes.

boolean copy_mpn(bignump result, bignum input);

Assigns result to the value currently held by input and returns true if successful. (Only memory allocation problems can cause a failure).

boolean gt_mpn(bignum left, bignum right);

Returns true if (and only if) left is greater than right.

boolean eq_mpn(bignum left, bignum right);

Returns true if (and only if) left is equal to right.

boolean nthBitSet_mpn( mp_numptr value, ushort bitnum )

Returns true if the bit numbered bitnum, counting from 0 in value is set, otherwise false.

void set0thBit_mpn(bignum value, boolean bit)

If bit is true, set the lowest bit of value, otherwise clear it.

boolean pack16_mpn(bignump value, ushort *data, ushort datalen, byte bitsUsed, byte freeLowBits)

pack the lowest bitsUsed bits from datalen uint16_t's into value with freeLowBits clear bits below this. Implicitly init_mpn()s value. Returns false if insufficient space is available

boolean unpack16_mpn(bignum value, ushort *data, ushort *datalen, byte bitsUsed, byte freeLowBits)

The converse operation to pack16_mpn, returns false if datalen is too small

boolean triple_mpn(bignump result, bignum input)

Sets result eqaul to a value three times input and return true; a false return means that there was not space to allocate for the result.

boolean set_prime_order(bignump value);

Initialises the value  to the GF 2²⁵⁵ prime. This routine does its own bignum initialisation so init_mpn need not be called first.