danger.crypto
Class BigInteger

java.lang.Object
  danger.crypto.BigInteger

All Implemented Interfaces:

Comparable

public final class BigInteger
extends Object
implements Comparable

BigInteger is an MPZ: an integer without an upper bound to its size. However, currently danger.crypto.BigInteger has a very real upper bound of 2048 bits. This restriction may be removed in the future.

When converting a BigInteger to/from a byte array, the number is assumed to be in "normalized" format. Normalized format is two's complement, big endian. In other words, the first byte is the most significant, and the high bit of the first byte determines its sign. For example, the number 2300 is represented as the byte array { 8, 0xfc }, and the number -129 is represented as the byte array { 0xff, 0x7f }.

A BigInteger is immutable, so operations always return a new BigInteger as the result. This may cause memory churn when doing many operations.

FIXME: There are also several fundamental math operations missing, because they weren't needed by the Terminal app that this class was created for. Those holes should be filled in.

NOTE: The current implementation of the java.math.BigInteger class on the device is more complete than this one. However, it is also much slower than this one. Eventually the performance issue will be improved. Until then, you may choose to use one or the other depending on your needs. Note that the java.math.BigInteger class has only been implemented since 2.3.

Field Summary

static BigInteger	ONE The BigInteger corresponding to 1, for convenience.
static BigInteger	ZERO The BigInteger corresponding to 0, for convenience.

Constructor Summary

BigInteger(byte[] in)
Create a new BigInteger from a byte array in normalized format.

BigInteger(byte[] in, int offset, int length)
Create a new BigInteger from a byte array in normalized format.

BigInteger(int x)
Create a new BigInteger from a native "int".

BigInteger(long x)
Create a new BigInteger from a native "long".

BigInteger(String s, int base)
Create a new BigInteger from a string.

Method Summary

BigInteger	add(BigInteger x) Add two BigIntegers.
int	bitLength() Determines how many bits are used by the absolute value of this number.
int	compareTo(BigInteger x) Compare this number to another BigInteger.
int	compareTo(Object o) Compare this number to an arbitrary object.
BigInteger	divide(BigInteger x) Divide two BigIntegers.
boolean	equals(Object o) Determine if this number is equal to an arbitrary object.
static BigInteger	generatePrimeCandidate(int bits) Generate a BigInteger which is a candidate for being prime, but hasn't had any rigorous tests applied yet.
static BigInteger	generateProbablePrime(int bits) Generate a BigInteger which is probably prime.
int	hashCode() Generates a hash code for this number.
boolean	isProbablePrime(int certainty) Determine if a BigInteger is probably prime.
BigInteger	mod(BigInteger x) Divide two BigIntegers and return the remainder.
BigInteger	modInverse(BigInteger x) Find the modular inverse of a number.
BigInteger	modPow(BigInteger exponent, BigInteger m) Raise this number to the exponent power, modulo m.
BigInteger	multiply(BigInteger x) Multiply two BigIntegers.
BigInteger	subtract(BigInteger x) Subtract two BigIntegers.
byte[]	toByteArray() Convert this number into a byte array, in normalized format.
int	toInteger() Convert this number to a java int.
String	toString() Generate a string representation of this number in decimal format.
String	toString(int base) Generate a string representation of this number in the given base.
static BigInteger	valueOf(int x) Create a BigInteger from a java int.
static BigInteger	valueOf(long x) Create a BigInteger from a java long.
static BigInteger	valueOf(String s) Create a BigInteger from a java String.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

ZERO

public static final BigInteger ZERO

The BigInteger corresponding to 0, for convenience.

ONE

public static final BigInteger ONE

The BigInteger corresponding to 1, for convenience.

Constructor Detail

BigInteger

public BigInteger(int x)

Create a new BigInteger from a native "int".

Parameters:

x - the initial value of this BigInteger, as an int

BigInteger

public BigInteger(long x)

Create a new BigInteger from a native "long".

Parameters:

x - the initial value of this BigInteger, as a long

BigInteger

public BigInteger(byte[] in,
                  int offset,
                  int length)

Create a new BigInteger from a byte array in normalized format. (See the class description for an explanation of normalized format.)

Parameters:

in - the byte array to parse

offset - offset in in to begin parsing

length - number of bytes of in to parse

BigInteger

public BigInteger(byte[] in)

Create a new BigInteger from a byte array in normalized format. (See the class description for an explanation of normalized format.) Equivalent to BigInteger(in, 0, in.length).

Parameters:

in - the byte array to parse

BigInteger

public BigInteger(String s,
                  int base)

Create a new BigInteger from a string.

Parameters:

s - the initial value as a string

base - the base of the string encoding

Throws:

NumberFormatException - if the base is outside the range [2, 16]

Method Detail

valueOf

public static BigInteger valueOf(int x)

Create a BigInteger from a java int.

Parameters:

x - the initial value as an int

Returns:

BigInteger with the value x

valueOf

public static BigInteger valueOf(long x)

Create a BigInteger from a java long.

Parameters:

x - the initial value as an long

Returns:

BigInteger with the value x

valueOf

public static BigInteger valueOf(String s)

Create a BigInteger from a java String. The number is assumed to be encoded in base 10 -- for other bases, use the BigInteger(String,int) constructor.

Parameters:

s - the initial value as a string in base 10

Returns:

BigInteger with the requested value

add

public BigInteger add(BigInteger x)

Add two BigIntegers.

Parameters:

x - the BigInteger to add

Returns:

a BigInteger representing (this + x)

subtract

public BigInteger subtract(BigInteger x)

Subtract two BigIntegers.

Parameters:

x - the BigInteger to subtract

Returns:

a BigInteger representing (this - x)

multiply

public BigInteger multiply(BigInteger x)

Multiply two BigIntegers.

Parameters:

x - the BigInteger to multiply

Returns:

a BigInteger representing (this * x)

divide

public BigInteger divide(BigInteger x)

Divide two BigIntegers.

Parameters:

x - the BigInteger to divide

Returns:

a BigInteger representing the integer part of (this / x)

mod

public BigInteger mod(BigInteger x)

Divide two BigIntegers and return the remainder.

Parameters:

x - the BigInteger to divide

Returns:

a BigInteger representing the remainder of (this / x) as a non-negative integer

Throws:

ArithmeticException - if x <= 0

modInverse

public BigInteger modInverse(BigInteger x)

Find the modular inverse of a number.

Parameters:

x - the modulus, which needs to be relatively prime to this BigInteger

Returns:

the modular inverse v, such that (this * v) mod x = 1

Throws:

ArithmeticException - if x <= 0, or this BigInteger has no inverse relative to x

compareTo

public int compareTo(BigInteger x)

Compare this number to another BigInteger.

Parameters:

x - the number to compare to

Returns:

0 if the two BigIntegers are equal; a negative integer if this number is less than x; a positive integer if this number is greater than x

compareTo

public int compareTo(Object o)
              throws ClassCastException

Compare this number to an arbitrary object.

Specified by:

compareTo in interface Comparable

Parameters:

o - the object to compare to

Returns:

an integer (see compareTo(BigInteger)) if o is a BigInteger

Throws:

ClassCastException - if o is not a BigInteger

equals

public boolean equals(Object o)

Determine if this number is equal to an arbitrary object.

Overrides:

equals in class Object

Parameters:

o - the object to compare to

Returns:

true if the object is a BigInteger and compareTo(o) returns 0.

hashCode

public int hashCode()

Generates a hash code for this number.

Overrides:

hashCode in class Object

Returns:

an int hash code

bitLength

public int bitLength()

Determines how many bits are used by the absolute value of this number. (In other words, two's-complement sign bits are not counted.)

Returns:

the number of bits

toByteArray

public byte[] toByteArray()

Convert this number into a byte array, in normalized format. (See the class description for an explanation of normalized format.)

Returns:

byte array representation of the number

toInteger

public int toInteger()

Convert this number to a java int. If the number's absolute value won't fit in 31 bits, then the lower 31 bits are returned, with the sign preserved.

Returns:

int that contains the lowest 31 bits of the number, with sign preserved

toString

public String toString()

Generate a string representation of this number in decimal format. Equivalent to toString(10).

Overrides:

toString in class Object

Returns:

string representation of the number in base 10

toString

public String toString(int base)

Generate a string representation of this number in the given base.

Parameters:

base - the requested base of the output string (from 2 to 16, inclusive; anything outside that range will be assumed 10)

Returns:

string representation of the number in the requested base

modPow

public BigInteger modPow(BigInteger exponent,
                         BigInteger m)

Raise this number to the exponent power, modulo m. This is frequently desired for private-key/public-key crypto. On the Hiptop, this function is optimized heavily.

Parameters:

exponent - the power to raise this number to

m - the modulus to coerce the result into

Returns:

a new BigInteger representing (this ** exponent mod m)

isProbablePrime

public boolean isProbablePrime(int certainty)

Determine if a BigInteger is probably prime.

Parameters:

certainty - the amount of certainty desired, as an exponent of 50% (the Rabin-Miller test will be executed certainty/2 times)

Returns:

true if there's a probability of better than (1 / 2**certainty) that this number is prime; false if the number is definitely composite.

generateProbablePrime

public static BigInteger generateProbablePrime(int bits)

Generate a BigInteger which is probably prime.

Parameters:

bits - number of bits to generate (between 2 and 2048)

Returns:

a new BigInteger which has a probability of better than (1 / 2**100) of being prime

Throws:

ArithmeticException - if bits is out of range

generatePrimeCandidate

public static BigInteger generatePrimeCandidate(int bits)

Generate a BigInteger which is a candidate for being prime, but hasn't had any rigorous tests applied yet. You should call isProbablePrime(int) on the result to determine if the candidate is actually prime (with some degree of certainty).

One potential use for this method is to have finer-grained control over the (often time-consuming) process of generating a large prime number. Repeatedly calling generatePrimeCandidate(int) and isProbablePrime(int) gives you a chance to provide visible feedback between each iteration.

Note: Currently the CJC algorithm is used when bits is 512. This algorithm rapidly generates numbers that are not divisible by the first six primes. For other values of bits, this method only guarantees that the result is odd.