IAIK-JCE Provider API Documentation
Version 6.0
iaik.utils

Class NumberTheory

• java.lang.Object
• iaik.utils.NumberTheory

• ```public final class NumberTheory
extends java.lang.Object```
Some useful number theoretic utility methods.
Version:
File Revision 23
• Field Summary

Fields
Modifier and Type Field and Description
`static java.math.BigInteger` `ONE`
BigInteger constant 1
`static int` `SMALLEST_PRIME_SIZE`
`static java.math.BigInteger` `TWO`
BigInteger constant 2
`static java.math.BigInteger` `ZERO`
BigInteger constant 0
• Method Summary

Methods
Modifier and Type Method and Description
`static int[]` ```extGcd(int a, int b)```
Extended Euclidean algorithm for computing the greatest common divisor of two integers.
`static int` ```gcd(int a, int b)```
Euclidean algorithm for computing the greatest common divisor of two integers.
`static java.math.BigInteger` ```getStrongPrime(int x, java.util.Random random)```
Returns a random strong prime.
`static boolean` `hasSmallFactors(java.math.BigInteger b)`
Test the given BigInteger b for small prime factors.
`static boolean` `isProbablePrime(java.math.BigInteger b)`
Perform a probabilistic primality test to determine if b is prime.
`static boolean` `millerRabin(java.math.BigInteger n)`
Performs the Miller-Rabin probabilistic primality test to determine if n is prime.
`static java.math.BigInteger` `nextPrime(java.math.BigInteger b)`
Return the smallest prime greater than or equal to b.
• Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• Field Detail

• SMALLEST_PRIME_SIZE

`public static final int SMALLEST_PRIME_SIZE`
Constant Field Values
• ZERO

`public static final java.math.BigInteger ZERO`
BigInteger constant 0
• ONE

`public static final java.math.BigInteger ONE`
BigInteger constant 1
• TWO

`public static final java.math.BigInteger TWO`
BigInteger constant 2
• Method Detail

• gcd

```public static int gcd(int a,
int b)```
Euclidean algorithm for computing the greatest common divisor of two integers.
• extGcd

```public static int[] extGcd(int a,
int b)```
Extended Euclidean algorithm for computing the greatest common divisor of two integers.
Returns:
{d,x,y} satisfying ax + by = d
• nextPrime

`public static java.math.BigInteger nextPrime(java.math.BigInteger b)`
Return the smallest prime greater than or equal to b.
• getStrongPrime

```public static java.math.BigInteger getStrongPrime(int x,
java.util.Random random)```
Returns a random strong prime.

This method implements an algorithm published in RSA LABORATORIES' CryptoBytes, Volume 3, Number 1 - Spring 1997, page 9.

Parameters:
`x` - the strength of the prime number
`random` - the random number generator to use
Returns:
the new generated random strong prime
• isProbablePrime

`public static boolean isProbablePrime(java.math.BigInteger b)`
Perform a probabilistic primality test to determine if b is prime. This method returns true if b is probable prime and false if it is definitely composite. The probability of returning true if b is composite is fiexd to 2-80 for this implementation.

This method only works for positive numbers.

`hasSmallFactors(java.math.BigInteger)`, `millerRabin(java.math.BigInteger)`
• millerRabin

`public static boolean millerRabin(java.math.BigInteger n)`
Performs the Miller-Rabin probabilistic primality test to determine if n is prime. Implementation according to IEEE Specification 1363 with error probability less than 2-100.

This method returns true if n is probable prime and false if it is definitely composite. The probability of returning true if n is composite is less than 2-100 for this implementation.

Parameters:
`n` - the integer to be tested (bit length must be >= 160)
Returns:
`true` if n is probable prime and `false` if it is definitely composite.
Throws:
`java.lang.IllegalArgumentException` - if the bit length of the number to be tested is shorter than 160 bits
• hasSmallFactors

`public static boolean hasSmallFactors(java.math.BigInteger b)`
Test the given BigInteger b for small prime factors. In other words, if this method returns true, the number is composite, if it returns false, it may be a prime. This method should not be used directly, use isProbablePrime() instead. Also note that it may not work for very small numbers.
This Javadoc may contain text parts from IETF Internet Standard specifications (see copyright note) and RSA Data Security Public-Key Cryptography Standards (PKCS, see copyright note).

 6.0 (c) 2002 IAIK, (c) 2003 - 2022 SIC