Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

RSA Laboratories

2.5.1 What is primality testing?

Primality testing is the process of proving a number is prime (an integer greater than 1 is prime if it is divisible only by itself and 1). It is used in the key generation process for cryptosystems that depend on secret prime numbers, such as the RSA system. Probabilistic primality testing is a process that proves a number has a high probability of being prime.

To generate a random prime number, random numbers are generated (see Question 2.5.2) and tested for primality until one of them is found to be prime (or very likely to be prime, if probabilistic testing is used).

It is generally recommended to use probabilistic primality testing, which is much quicker than actually proving a number is prime. One can use a probabilistic test that determines whether a number is prime with arbitrarily small probability of error, say, less than 2-100. For further discussion of some primality testing algorithms, see [BBC88]. For some empirical results on the reliability of simple primality tests, see [Riv91a]; one can perform very fast primality tests and be extremely confident in the results. A simple algorithm for choosing probable primes was analyzed by Brandt and Damgård [BD93b].

Top of the page

Connect with EMCConnect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
Explore our world-class business partners and connect with a partner today.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.