ds.ov2.util
Class BigIntUtil

java.lang.Object
  ds.ov2.util.BigIntUtil

public class BigIntUtil
extends Object

BigInteger Utilities. Extending the BigInteger class for these few methods is not an option because one would need to program downcasts for all methods that return a fresh BigInteger, which are basically all methods of BigInteger.

Static class.

CPP Preprocessing

no cpp preprocessing needed

Execution Environment:

host

Author:

Hendrik Tews

Version:

$Revision: 1.10 $

Last Commit:

$Date: 2009-05-12 14:48:38 $ by $Author: tews $

Constructor Summary

protected

BigIntUtil() Static class, object creation disabled.

Method Summary

static int	byte_size(BigInteger bi) BigInteger size in bytes.
static boolean	coprime(BigInteger a, BigInteger b) Coprime check.
static void	copy_into_byte_array(BigInteger bi, byte[] a) Copy a BigInteger into a byte array.
static BigInteger	from_byte_array(byte[] a) Convert a byte array into a BigInteger.
static BigInteger	mod_rand_with_inverse(Random rand, BigInteger mod) Modular random number generator for the multiplicative subgroup.
static BigInteger	mod_rand(Random rand, BigInteger mod) Modular random number generator.
static BigInteger	multi_exponent(BigInteger[] base, BigInteger[] exponent, BigInteger modulus) Compute the multi-exponent base^exponent (modulo modulus).
static void	print_array(PrintWriter out, String intro_format, String line_start, BigInteger[] bi) Prints a BigInteger array as follows.
static String	to_byte_hex_string(BigInteger bi) Converts a BigInteger into a hex string.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BigIntUtil

protected BigIntUtil()

Static class, object creation disabled.

Method Detail

coprime

public static boolean coprime(BigInteger a,
                              BigInteger b)

Coprime check. Tests whether the two arguments are coprime. Two natural numbers are said to be coprime if the biggest factor they share is 1, ie. if there greatest common divisor is 1.

Parameters:

a - first BigInteger

b - second BigInteger

Returns:

true if a and b are coprime.

mod_rand

public static BigInteger mod_rand(Random rand,
                                  BigInteger mod)

Modular random number generator. Generate an equally distributed random number less than mod with a bit length at most 4 less than the bit length of mod.

Parameters:

rand - Random number generator

mod - modulus

Returns:

a random number less than mod

mod_rand_with_inverse

public static BigInteger mod_rand_with_inverse(Random rand,
                                               BigInteger mod)

Modular random number generator for the multiplicative subgroup. Generates an equally disctributed random number less than mod that has a modular inverse modulo mod. The bit length of the random number is at most 4 less than mod.

Parameters:

rand - Random number generator

mod - modulus

Returns:

random number less than mod with a modular inverse

multi_exponent

public static BigInteger multi_exponent(BigInteger[] base,
                                        BigInteger[] exponent,
                                        BigInteger modulus)

Compute the multi-exponent base^exponent (modulo modulus).

Asserts that the base and exponent array have the same length.

Parameters:

base - the bases

exponent - the exponents

modulus -

Returns:

the exponent base[0]^exponent[0] * base[1]^exponent[1] * ... (modulo modulus)

byte_size

public static int byte_size(BigInteger bi)

BigInteger size in bytes. For BigInteger.ZERO it returns 1. Note that the value computed here might be different from BigInteger.toByteArray.length because the latter might add a leading zero byte.

Parameters:

bi -

Returns:

the size in bytes of bi

to_byte_hex_string

public static String to_byte_hex_string(BigInteger bi)

Converts a BigInteger into a hex string. In contrast to BigInteger.toString(16) 4-digit-groups are separated by points, like 23EA.4F11...

Parameters:

bi - BigInteger to convert

Returns:

hex string

copy_into_byte_array

public static void copy_into_byte_array(BigInteger bi,
                                        byte[] a)

Copy a BigInteger into a byte array. This is a bit more tricky than just copying the result of BigInteger.toByteArray(). First, the argument array a might need some zero padding and second, BigInteger.toByteArray() might have a leading zero that does not fit into a.

Asserts that the BigInteger bi, with leading zeros removed, fits into a.

Parameters:

bi - the source BigInteger

a - the destination array

from_byte_array

public static BigInteger from_byte_array(byte[] a)

Convert a byte array into a BigInteger. This is just as BigInteger.BigInteger(byte[]) but does not produce negative BigIntegers if the first bit in a is set.

Parameters:

a - source byte array

Returns:

positive BigInteger with the value of a

print_array

public static void print_array(PrintWriter out,
                               String intro_format,
                               String line_start,
                               BigInteger[] bi)

Prints a BigInteger array as follows.

  4 bases
  base[0]: 5F11.9615
         = 1594988053
  base[1]: 1999.3BC3
         = 429472707
  base[2]: 00.8327.3245
         = 2200384069
  base[3]: 5D9E.AA9A
         = 1570679450
 

The first line is hex, the second decimal.

Argument intro_format must be a format string that accepts the length of the array as integer argument. It is used for the heading. In the above example it is "%d bases\n". Note the newline at the end!

The line_start is a string with the name of the array, in the above example it is "base".

Parameters:

out - output channel

intro_format - format string with at most integer directive for the heading

line_start - name of the array

bi - the array to print