Developer Reference

Contents

Prime Number Generation Functions

This section introduces Intel® Integrated Performance Primitives (Intel® IPP) Cryptography functions for prime number generation.
This section describes Intel IPP Cryptography functions for generating probable prime numbers of variable lengths and validating probable prime numbers through a probabilistic primality test scheme for cryptographic use. A probable prime number is thus defined as an integer that passes the Miller-Rabin probabilistic primality-based test.
The scheme adopted for the probable prime number generation is based on a well-known prime number theorem. Study shows that the number of primitives that are no greater than the given large integer
x
is closely approximated by the expression. Let π(
x
) denote the number of primes that are not greater than x. In this case the statement is true
Further study indicates that if
X
represents the event where the tested
k
-bit integer
n
is composite and if
Y
t
denotes the event where the Miller-Rabin test with the security parameter
t
declares
n
to be a prime, the test error probability is upper bounded by
Subsequently, a practical strategy for generating a random
k
-bit probable prime is to repeatedly pick
k
-bit random odd integers until finding one integer that can pass a recognized probabilistic primality test scheme as a probable prime. The available set of probable prime number generation functions enables you to specify an appropriate value of the security parameter
t
used in the Miller-Rabin primality test to meet the cryptographic requirements for your application.
All Intel IPP for prime number generation use the context
IppsPrimeState
as an operational vehicle that carries the bitlength of the target probable prime number, the structure capturing the state of the pseudorandom number generation, the structured working buffer used for Montgomery modular computation in the Miller-Rabin primality test, and the buffer to store the generated probable prime number.
The following sequence of operations is required to generate a probable prime number of the specified bitlength:
  1. Call the function
    PrimeGetSize
    to get the size required to configure the
    IppsPrimeState
    context.
  2. Allocate memory through the operating system memory allocation function and configure the
    IppsPrimeState
    context
    by calling the function
    PrimeInit
    .
  3. Generate a probable prime number of the specified bitlength by calling the function
    PrimeGen_BN
    . If the returned
    IppStatus
    is
    ippStsInsufficientEntropy
    , then change the parameters of the pseudorandom generator and call the function
    PrimeGen_BN
    again.
  4. Clean up secret data stored in the context.
  5. Free the memory allocated to the
    IppsPrimeState
    context by calling the operating system memory-free service function.

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.