ISO/IEC 18032:2020
(Main)Information security — Prime number generation
Information security — Prime number generation
This document specifies methods for generating and testing prime numbers as required in cryptographic protocols and algorithms. Firstly, this document specifies methods for testing whether a given number is prime. The testing methods included in this document are divided into two groups: — probabilistic primality tests, which have a small error probability. All probabilistic tests described here can declare a composite to be a prime; — deterministic methods, which are guaranteed to give the right verdict. These methods use so-called primality certificates. Secondly, this document specifies methods to generate prime numbers. Again, both probabilistic and deterministic methods are presented. NOTE It is possible that readers with a background in algorithm theory have already had previous encounters with probabilistic and deterministic algorithms. The deterministic methods in this document internally still make use of random bits (to be generated via methods described in ISO/IEC 18031), and "deterministic" only refers to the fact that the output is correct with probability one. Annex A provides error probabilities that are utilized by the Miller-Rabin primality test. Annex B describes variants of the methods for generating primes so that particular cryptographic requirements can be met. Annex C defines primitives utilized by the prime generation and verification methods.
Sécurité de l'information — Génération de nombres premiers
General Information
Relations
Standards Content (Sample)
INTERNATIONAL ISO/IEC
STANDARD 18032
Second edition
2020-12
Information security — Prime number
generation
Sécurité de l'information — Génération de nombres premiers
Reference number
©
ISO/IEC 2020
© ISO/IEC 2020
All rights reserved. Unless otherwise specified, or required in the context of its implementation, no part of this publication may
be reproduced or utilized otherwise in any form or by any means, electronic or mechanical, including photocopying, or posting
on the internet or an intranet, without prior written permission. Permission can be requested from either ISO at the address
below or ISO’s member body in the country of the requester.
ISO copyright office
CP 401 • Ch. de Blandonnet 8
CH-1214 Vernier, Geneva
Phone: +41 22 749 01 11
Email: copyright@iso.org
Website: www.iso.org
Published in Switzerland
ii © ISO/IEC 2020 – All rights reserved
Contents Page
Foreword .iv
1 Scope . 1
2 Normative references . 1
3 Terms and definitions . 1
4 Symbols and abbreviated terms . 2
5 Trial division . 3
6 Probabilistic primality test . 4
6.1 General . 4
6.2 Requirements . 4
6.3 Miller-Rabin primality test . 4
7 Deterministic primality verification methods . 5
7.1 General . 5
7.2 Elliptic curve primality proving algorithm . 6
7.2.1 General. 6
7.2.2 Elliptic curve primality certificate generation . 6
7.2.3 Elliptic curve primality certificate verification . 7
7.3 Primality certificate based on The Shawe-Taylor algorithm . 7
8 Prime number generation . 8
8.1 General . 8
8.2 Requirements . 8
8.3 Using the Miller-Rabin primality test . 9
8.3.1 General. 9
8.3.2 Random search . 9
8.3.3 Incremental search . 9
8.3.4 Primes with an elliptic curve primality certificate . 9
8.4 Using deterministic methods. 9
8.4.1 General. 9
8.4.2 The Shawe-Taylor algorithm .10
Annex A (normative) Error probabilities .11
Annex B (normative) Generating primes with side conditions .13
Annex C (normative) Additional random number generation methods .16
Annex D (normative) Auxiliary methods .17
Annex E (informative) Prime generation examples .31
Bibliography .33
© ISO/IEC 2020 – All rights reserved iii
Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical
Commission) form the specialized system for worldwide standardization. National bodies that
are members of ISO or IEC participate in the development of International Standards through
technical committees established by the respective organization to deal with particular fields of
technical activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other
international organizations, governmental and non-governmental, in liaison with ISO and IEC, also
take part in the work.
The procedures used to develop this document and those intended for its further maintenance are
described in the ISO/IEC Directives, Part 1. In particular, the different approval criteria needed for
the different types of document should be noted. This document was drafted in accordance with the
editorial rules of the ISO/IEC Directives, Part 2 (see www .iso .org/ directives).
Attention is drawn to the possibility that some of the elements of this document may be the subject
of patent rights. ISO and IEC shall not be held responsible for identifying any or all such patent
rights. Details of any patent rights identified during the development of the document will be in the
Introduction and/or on the ISO list of patent declarations received (see www .iso .org/ patents) or the IEC
list of patent declarations received (see http:// patents .iec .ch).
Any trade name used in this document is information given for the convenience of users and does not
constitute an endorsement.
For an explanation of the voluntary nature of standards, the meaning of ISO specific terms and
expressions related to conformity assessment, as well as information about ISO's adherence to the
World Trade Organization (WTO) principles in the Technical Barriers to Trade (TBT), see www .iso .org/
iso/ foreword .html.
This document was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, Information security, cybersecurity and privacy protection.
This second edition cancels and replaces the first edition (ISO/IEC 18032:2005), which has been
technically revised.
The main changes compared to the previous edition are as follows:
— the Frobenius-Grantham primality test in 6.2, the Lehmann primality test in 6.3 and Maurer’s
algorithm in 8.3.1, have been removed;
– the Elliptic curve primality proving algorithm, The Shawe-Taylor algorithm and the algorithm to
generate primes with side conditions, have been added or substantially revised.
Any feedback or questions on this document should be directed to the user’s national standards body. A
complete listing of these bodies can be found at www .iso .org/ members .html.
iv © ISO/IEC 2020 – All rights reserved
INTERNATIONAL STANDARD ISO/IEC 18032:2020(E)
Information security — Prime number generation
1 Scope
This document specifies methods for generating and testing prime numbers as required in
cryptographic protocols and algorithms.
Firstly, this document specifies methods for testing whether a given number is prime. The testing
methods included in this document are divided into two groups:
— probabilistic primality tests, which have a small error probability. All probabilistic tests described
here can declare a composite to be a prime;
— deterministic methods, which are guaranteed to give the right verdict. These methods use so-called
primality certificates.
Secondly, this document specifies methods to generate prime numbers. Again, both probabilistic and
deterministic methods are presented.
NOTE It is possible that readers with a background in algorithm theory have already had previous encounters
with probabilistic and deterministic algorithms. The deterministic methods in this document internally still
make use of random bits (to be generated via methods described in ISO/IEC 18031), and “deterministic” only
refers to the fact that the output is correct with probability one.
Annex A provides error probabilities that are utilized by the Miller-Rabin primality test.
Annex B describes variants of the methods for generating primes so that particular cryptographic
requirements can be met.
Annex C defines primitives utilized by the prime generation and verification methods.
2 Normative references
The following documents are referred to in the text in such a way that some or all of their content
constitutes requirements of this document. For dated references, only the edition cited applies. For
undated references, the latest edition of the referenced document (including any amendments) applies.
ISO/IEC 18031, Information technology — Security techniques — Random bit generation
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
ISO and IEC maintain terminological databases for use in standardization at the following addresses:
— ISO Online browsing platform: available at https:// www .iso .org/ obp
— IEC Electropedia: available at http:// www .electropedia .org/
3.1
composite number
composite
integer for which divisors exist that are not trivial divisors (3.8)
© ISO/IEC 2020 – All rights reserved 1
3.2
deterministic random bit generator
DRBG
random bit generator that produces a random-appearing sequence of bits by applying a deterministic
algorithm to a suitably random initial value called a seed and, possibly, some secondary inputs on which
the security of the random bit generator does not depend
3.3
entropy
measure of the disorder, randomness or variability in a closed system
[SOURCE: ISO/IEC 18031:2011, 3.11]
3.4
Jacobi symbol
Jacobi symbol of a positive integer a with respect to an odd integer n
product of the Legendre symbols of a with respect to the prime factors of n, including multiplicity (3.5)
Note 1 to entry: If the prime factor p occurs with multiplicity m ≥ 1 in the factorization of n, then the Legendre
symbol of a with respect to p occurs with multiplicity m in the product that yields the Jacobi symbol of a with
respect to n.
Note 2 to entry: The Legendre symbol of a positive integer a with respect to a prime number p is the value
(p - 1)/2
a mod p
3.5
multiplicity
multiplicity of a prime divisor p of n
e
largest positive integer e with p dividing n
3.6
primality certificate
mathematical proof that a given integer is indeed a prime
Note 1 to entry: For a small integer, primality is most efficiently proven by trial division. In this case, the primality
certificate can therefore be empty.
3.7
prime number
prime
positive integer for which there exist only trivial divisors (3.8)
3.8
trivial divisors
trivial divisors of a nonzero integer N
1, -1, N and –N
Note 1 to entry: Any nonzero integer N is divisible by (at least) 1, -1, N and –N.
4 Symbols and abbreviated terms
a div n for integers a and n, with n ≠ 0, a div n is the unique integer s satisfying a = s · n
+ r where 0 ≤ r < n.
a mod n for integers a and n, with n ≠ 0, a mod n is the unique non-negative integer r
satisfying a = (a div n) · n + r.
C primality certificate
2 © ISO/IEC 2020 – All rights reserved
C(N) primality certificate for the number N
C (N) empty primality certificate, indicating that trial division should be used to verify
that N is a prime
c
exp(c) natural exponential function evaluated at c, i.e. e where e ≈ 2,718 28
gcd greatest common divisor
Jacobi(a,N) Jacobi symbol for an integer a with respect to a nonzero odd integer N
k number of bits in N
L limit below which primality is verified by trial division
th
Lucas(D, K, N) K element of the Lucas sequence modulo N with discriminant D
ln(a) natural logarithm of a with respect to the base e ≈ 2,718 28
log (a) logarithm of a with respect to base b
b
min{a,b} minimum of the numbers a and b
N candidate number to be tested for primality, where N is always a positive,
odd number
sgn(D) sign of a number, i.e. sgn(D) = 1 if D ≥ 0 and -1 otherwise.
T (probabilistic) test for primality
Z the set of the integers 0, 1, 2, ., N-1, representing the ring of integers modulo N
N
Z * subset of Z containing the numbers that have a multiplicative inverse modulo
N N
N (e.g., if N is prime, Z * consists of the integers 1, 2, ., N-1)
N
β parameter that determines the lower bound of the entropy of the output of a
prime generation algorithm
μ maximal number of steps in an incremental search for a prime
⎿x⏌ largest integer smaller than or equal to x
⎾x⏋ smallest integer greater than or equal to x
√n principal (i.e. non-negative) square root of a non-negative number n
5 Trial division
The primality of an integer N can be proven by means of trial division. This shall be done in the
following way:
a) For all primes p ≤ √N:
1) if N mod p = 0 then return “N composite” and stop;
b) return “N prime” and stop.
For small integers N, trial division is less computationally expensive than other primality tests.
Implementations of any primality test described in this document may define a trial division bound
© ISO/IEC 2020 – All rights reserved 3
L, below which trial division is used in order to prove the primality of integers. This document sets no
value for L except for a lower bound, i.e. L > 6.
NOTE 1 It is assumed that the set of prime numbers below a certain size are already known. One practical way
to implement the test is to have a pre-computed table of the first few primes, do trial division by these, and then
simply trial divide by all odd integers up to the square root.
NOTE 2 The size of integers for which trial division is less computationally expensive than another primality
test depends on the test and its implementation. A possible value for L can be L = 10 .
[1]
NOTE 3 A binned gcd method, as described in ANSI X9.80-2010, can be more efficient than trial division for
certain implementations.
6 Probabilistic primality test
6.1 General
A probabilistic primality test takes a positive, odd integer N as input and returns “N accepted” or “N
composite”. The Miller-Rabin primality test described in 6.3 will always output “N accepted” when N
is a prime number. However, if N is a composite number, then an instance of the test can erroneously
return “N accepted”. In order to reduce the probability of such errors, one usually performs several
iterations of testing on N, using different choices for the random values employed.
The probabilistic tests in this clause shall only be applied to odd integers that are greater or equal to
the trial division bound L. If N < L, trial division shall be applied to determine the primality of N.
6.2 Requirements
In order for a number to be accepted as a (probable) prime, this document requires the error probability,
-100
i.e. the probability the number is composite, to be at most 2 . This provides significant confidence
-100
that any candidate prime being tested for primality that meets this threshold is indeed prime. The 2
probability bound is achieved by requiring a sufficient number of Miller-Rabin tests, depending on how
the number was generated (see Annex A).
6.3 Miller-Rabin primality test
The Miller-Rabin primality test is based on the following observation. Suppose that N actually is an odd
r
prime number and that r and s are the unique positive integers such that N – 1 = 2 s, with s odd. For
each positive integer b < N, exactly one of the following three conditions will be satisfied:
s
— b mod N = 1;
s
— b mod N = N – 1; or
i
s
— b mod N = N – 1, for some i with 0 < i < r.
()
Equivalently, if N ≥ 3 is an odd integer and there exists a positive integer b < N that does not satisfy
any of the conditions above, then N is a composite number. A probabilistic primality test based on this
observation shall be applied to any odd integer N ≥ L, as follows.
Initialization
r
a) Determine positive integers r and s such that N – 1 = 2 s, where s is odd.
b) Set rounds = 0.
Perform t iterations (rounds) of Miller-Rabin testing (for integer t ≥ 1).
c) Choose a random integer b such that 2 ≤ b ≤ N – 2.
4 © ISO/IEC 2020 – All rights reserved
s
d) Set y = b mod N.
e) If y = 1 or y = N – 1,
1) set rounds = rounds + 1;
2) if rounds
go to step c)
else
return “N probably prime” and stop testing.
f) For i = 1 to r – 1, do:
1) set y = y mod N;
2) if y = N – 1;
i) set rounds = rounds + 1;
ii) if rounds < t, go to step c);
otherwise return “N probably prime” and stop testing.
g) Return “N composite” and stop testing.
The candidate N is accepted as being (probably) prime at the conclusion of the iterated testing process
if and only if N passes all t rounds of Miller-Rabin primality testing (with each choice of b satisfying
one of the conditions associated with primality). The testing process returns “N composite” and is
immediately halted if, for some choice of b, none of the tested conditions are satisfied (see A.2 and A.3 to
determine the number of iterations required by this document).
The integer b generated in step c) shall be generated using a random bit generator that meets the
specifications of ISO/IEC 18031 and converted to a number using the conversion methods in Annex C
or ISO/IEC 18031. For each iteration, the process of selecting a value for b in step c) is performed anew.
NOTE 1 The rationale for the base b being randomly generated is two-fold. Firstly, the average case error
estimates adopted from Reference [9] and used in A.3 assume b is random. Secondly, for a known base b, it is not
difficult to construct composite integers that will pass a round of Miller-Rabin with respect to that base.
NOTE 2 Step f) is only applicable when r > 1, i.e. if N mod 4 = 1.
7 Deterministic primality verification methods
7.1 General
Deterministic primality verification methods use primality certificates in order to verify the primality
of a given number. This clause specifies the content of two types of primality certificates:
— primality certificates based on elliptic curves;
— primality certificates for primes generated by The Shawe-Taylor algorithm (see 8.4.2).
A primality certificate contains information that enables efficient verification that a given number is a
prime. For both types of certificates described in this document, small numbers (i.e. numbers smaller
than the trial division bound L) shall be verified to be primes by trial division. Let C denote the empty
primality certificate for such numbers.
An elliptic curve primality certificate can be computed given any prime. Hence, the methods for
computing this certificate may be used to verify primality. The primality certificate obtained in The
© ISO/IEC 2020 – All rights reserved 5
Shawe-Taylor algorithm is generated as part of the process of generating a prime, and cannot be
efficiently computed for an arbitrary prime (after the prime has been generated).
7.2 Elliptic curve primality proving algorithm
7.2.1 General
Information regarding elliptic curves can be obtained from ISO/IEC 15946-1.
7.2.2 Elliptic curve primality certificate generation
To generate a certificate of primality for an odd integer N ≥ L, the method described below is used
recursively. If the method succeeds, the total collection of data generated by the method is organized in
a primality certificate, C(N). Verifying C(N), and thereby proving that N is prime, is considerably faster
than generating the certificate.
On input of an integer N ≥ L, with gcd(N,6) = 1, the elliptic curve primality proving algorithm shall start
with the following initializations.
a) Set S = { N } (the set of integers that require a primality certificate), and set Certs = { } (a contentless
certificate).
In the following steps, various primality tests are applied to an integer r selected from set S. If a
test (provisionally) accepts the primality of r, it returns a certificate C(r), and, possibly, a set of
probable primes { q }, in which case the certificate shall not be used to prove that r is prime, unless
i
each q has been proven prime. If necessary, the algorithm shall proceed recursively, attempting
i
to generate a certificate of primality for each of those probable primes. In the course of generating
those certificates, additional probable primes may be added to the set of integers that require
certificates. The algorithm shall continue until either there are no more probable primes to process
or the processing is aborted because some integer requiring a certificate is determined to be a
composite number.
b) Select a value for r from S and set S = S − { r } (i.e. remove the element r from S).
1) Apply either:
— Pocklington’s primality test to r (see D.2) and, if that test is inconclusive, also apply the
Deterministic Lucas primality test to r (see D.4.2); or
— the Brillhart-Lehmer-Selfridge test to r (see D.5).
In either case, when the testing is performed, allow probable primes ≥ L to occur (with
multiplicity) in the partial factorizations of r − 1 and/or r + 1.
2) If the testing indicates r is composite, return “r composite” (along with the value of r) and stop.
3) If the testing is inconclusive, proceed to step c).
4) If the testing indicates that r is prime, then adjoin C(r) to Certs, where C(r) is the certificate for r
returned by the successful test, and set S = S ∪ { q }, where { q } is the set of probable primes (if
i i
any) appearing in the factorizations of r − 1 and/or r + 1 (whichever were used in the testing);
if S is not empty, repeat step b). Otherwise, return “N prime” along with C(N) = Certs, and stop.
2 3
c) Generate an elliptic curve E given by y = x +ax+b for some integers a, b.
1) Apply the elliptic curve primality test to r (see D.6). When the test is performed, allow probable
primes ≥L to occur (with multiplicity) in the partial factorization of the order of E (the curve E
r
reduced modulo r).
2) If the test indicates that r is composite, return “r composite” along with the value of r and stop.
6 © ISO/IEC 2020 – All rights reserved
3) If the test is inconclusive, repeat step c) with a new choice of elliptic curve.
4) If the test indicates that r is prime, then adjoin C(r) to Certs, where C(r) is the certificate for r
returned by the successful test, and set S = S ∪ { q }, where { q } is the set of probable primes (if
i i
any) appearing in the factorization of the order of E ; if S is not empty, go to step b). Otherwise,
r
return “N is prime” along with C(N) = Certs, and stop.
The probable prime factors (if any) appearing in steps b) and c) are required to be greater than or equal
to the trial division bound. The primality of smaller factors shall be ascertained using trial division.
During the recursion, the tests in step b) can be skipped. It is included in the algorithm’s description for
efficiency purposes.
If the primality of N is inconclusive, the test may be executed again. The test may not be rerun in full
if partial results of the previous execution are retained (e.g., the value of Certs when testing process
was stopped and the composite r value that caused the early termination). It can be sufficient to back
the recursion step one level prior to the point of failure. Varying choices of curves in step c) and/or
optionally skipping step b) is likely to result in different sets of probable primes to test.
In case r is composite, the elliptic curve test in step c) is likely to be inconclusive and so the algorithm
can fail to terminate. As a precaution, a limit on the number of iterations of step c) may be enforced.
NOTE The elliptic curve E in step c) can be generated using the CM method described in D.8.
7.2.3 Elliptic curve primality certificate verification
An elliptic curve primality certificate for an integer N ≥ L, with gcd(N, 6) = 1, is a set of (interdependent)
certificates, C(N) = { C }, where each C asserts the primality of some integer r ≥ L, and exactly one of the
i i i
r is equal to N. Each C is a certificate resulting from the execution of either Pocklington's test (D.2.2), the
i i
Deterministic Lucas test (D.4.2), the Brillhart-Selfridge-Lehmer test (D.5) or the elliptic curve test (D.6).
If C asserts the primality of r based (in part) on the assumed primality of one or more other integers
i i
q ≥ L, then the certificate C (and hence the primality of r ) shall only be successfully verified after
j i i
the primality of each of the q is accepted via the verification of their certificates, which shall also be
j
included in C(N). If C asserts the primality of r based (in part) on the assumed primality of any integers
i i
less than L, then trial division shall be used to verify the primality of those integers as part of the
verification of C .
i
The elliptic curve primality certificate C(N) = { C } is accepted only if every C is accepted (and exactly
i i
one of the r is equal to N). If the verification of any C fails, then the elliptic curve primality certificate
i i
for N shall be rejected.
Verifying each of the individual certificates C shall be done as specified in Annex D.
i
7.3 Primality certificate based on The Shawe-Taylor algorithm
This type of primality certificate C is a collection of certificates { C } which shall be computed (only)
i
during the generation process of the prime number using the process described in 8.4.2 (The Shawe-
Taylor algorithm). The certificates C are the result of the Pocklington test (see D.2.2) whose proofs of
i
primality have the following structure:
Proof(r ) =(r , q , a )
i i i i
where r , q , and a are integers. The certificate C , which asserts that r is prime, is verified once it passes
i i i i i
the checks in C.2 and q is proven to be (an odd) prime (e.g., by trial division or by verifying its own
i
certificate, which has also been included in C). The last certificate to be verified, say C = (N, q , a ),
1 1 1
contains the value N. If all of the C are verified (and are confirmed to chain up to N), then C itself is
i
verified and N is accepted as being prime.
© ISO/IEC 2020 – All rights reserved 7
8 Prime number generation
8.1 General
This clause specifies two approaches to prime number generation. The first approach is to employ the
probabilistic Miller-Rabin primality test on randomly chosen candidates (8.3). [Optionally, a probable
prime, N, generated by such methods may subsequently be proven prime by generating an elliptic curve
primality certificate (7.2) for N.] The second approach to prime number generation is to employ the
deterministic Shawe-Taylor method (8.4) which yield integers known to be prime. This method can also
produce primality certificates as part of the generation process.
k-1 k
The methods in this clause generate primes in the interval (2 , 2 ) for some k. To generate primes
with additional constraints, such as generating primes in a more restrictive interval and/or primes that
satisfy certain congruence conditions, the methods in B.2 shall be used. Examples of primes generated
with additional constraints are given in Annex E.
These techniques shall only be applied to generate primes greater or equal to the trial division bound
L. Generating primes less than L can be simply done by selecting integers less than L and testing for
primality using trial division.
8.2 Requirements
In order for a prime number generation algorithm to conform to this document, the algorithm shall:
— generate random bits using a deterministic random bit generator that meets the specifications of
ISO/IEC 18031;
— generate random numbers from sequences of random bits using the conversion methods specified
in Annex C or ISO/IEC 18031;
— ensure, in the case of non-provable primes (8.3), that the error probability that a composite passes
-100
as prime is at most 2 .
-100
Annex A contains more information on how the algorithms in 8.3 shall satisfy the 2 error properties.
For applications where the primes generated need to be secret, the following also applies:
— the (secret) entropy used in the random bit generator to produce the output number shall satisfy
the requirements of ISO/IEC 18031 and shall be at least B bits where B is the security level of that
application;
— if additional constraints are placed on the prime being generated (B.2), the constraints shall be
limited so as not to affect the security of the system and the requirements in Annex B shall apply.
In the case of generating primes for use in RSA, B should be at least 112 for 1 024-bit primes, 128 for 1 536-
bit primes, 192 for 3 840-bit primes, and 256 for 7 680-bit primes. ISO/IEC 18031 requires a minimum
entropy of 120 bits to avoid collisions. In the case of RSA, collisions can lead to primes repeating for
different RSA moduli. Such primes can be recovered by computing a gcd among the RSA moduli.
[7][14]
NOTE Limiting the total number of constraints is necessary to avoid Coppersmith-style attacks, e.g.
these attacks can factor RSA moduli if roughly half the bits of a prime factor are known. If the constraints (such
k
as the number of known bits) are limited, then these attacks do not apply. For example, requiring an integer n < 2
k-2 k-1 k
to lie in the interval (2 + 2 , 2 ) with n mod 4 = 3, and gcd(n-1, e ) = 1 for some odd encryption exponent gives
k-1 k
less than 5 bits of constraint. If the interval is replaced with (2 √2, 2 ), the total constraint is less than 4,5 bits.
Generating a k–bit number n with n mod q = 1 for some randomly generated (and secret) integer q of size m bits
places roughly two bits of constraint on n (since n can be expressed as n = 1 + u q where u, q are both k-m, m-bit
numbers respectively). Further requiring q to be prime adds a few additional bits of constraint, approximately
log (m) – 0,528 bits by the prime number theorem.
When regenerating (secret) primes from a fixed seed, care should be taken so as to avoid side-channel
attacks.
8 © ISO/IEC 2020 – All rights reserved
8.3 Using the Miller-Rabin primality test
8.3.1 General
The error probability that a composite passes as being prime depends on the number of iterations
used in the Miller-Rabin primality test. Annex A shall be followed to determine the requisite number of
iterations.
Subclauses 8.3.2 and 8.3.3 describe two algorithms that meet the requirements of 8.2.
8.3.2 Random search
The following algorithm may be used to generate a k-bit prime.
k-1 k
a) Generate a random number N such that 2 < N <2 . If N is even, increment N by 1.
b) Apply the Miller-Rabin primality test. If it is accepted, return N and stop. Otherwise, go to step a).
8.3.3 Incremental search
The following algorithm may be used to generate a k-bit prime. It differs from the algorithm given in
8.3.2 by the way it selects candidates for primality testing. If a randomly chosen (odd) candidate N is
not accepted by the Miller-Rabin primality test, several of the following consecutive odd integers (N+2,
N+4, etc.) are tested before randomly choosing another value for N. As a result, this algorithm can have
some practical advantages (in terms of the efficiency of an implementation) over 8.3.2. A parameter
denoted μ limits the number of consecutive odd integers that are tested between random choices of N.
k-1 k
a) Generate a random number N such that 2 < N <2 . If N is even, increment N by 1.
k k
b) Set Max = min{ 2 -1, N + 2µ } for some appropriately chosen value of µ, e.g. µ = 10 ln(2 ).
c) If N is accepted by the Miller-Rabin primality test, return N and stop.
d) Set N = N+2.
e) If N > Max, go to step a). Otherwise, go to step c).
Rather than increment the candidate prime N in step d) by 2, one may apply the Miller-Rabin test to
elements in the sequence N, N+2, N+4, …, Max which survive the sieving procedure described in C.1. The
sieve process eliminates candidate primes that are divisible by the small primes used in the sieve.
k
NOTE The suggested value of 10 ln(2 ) for µ is based on the Prime Number theorem which gives an
k k k
approximation of 2 / ln(2 ) for the number of primes less than 2 . The extra factor of 10 is given to increase the
likelihood that a prime is contained in the interval [N, N+2µ]. In particular, Lemma 4 of Reference [5] conjectures
such a prime exists with probability about 1 - exp( -2 · c ), c = 10.
8.3.4 Primes with an elliptic curve primality certificate
A certified prime may be generated by first generating a prime using the methods described in 8.3.2 and
8.3.3, and then computing an elliptic curve primality certificate for that number, as described in 7.2.
8.4 Using deterministic methods
8.4.1 General
The deterministic method in this subclause constructs a provable prime of the desired size by recursively
constructing smaller provable primes. The prime generation algorithm calls itself repeatedly to
generate a third-size (or half-size) prime and this recursion only stops when the prime size is such that
a random candidate prime can be proven prime by trial division, after which the recursion unwinds by
constructing triple-size (or doubled-size) primes that are provably prime by construction.
© ISO/IEC 2020 – All rights reserved 9
8.4.2 The Shawe-Taylor algorithm
The Shawe-Taylor algorithm generates a random prime number N from scratch. It shall be implemented
using the algorithm described. This algorithm takes as input an integer k, the number of bits in the
required prime. It returns a number N and a certificate of primality if requested.
This algorithm is called recursively, such that for a given bit-length j ≥ log (L), there is a:
a) j’-bit prime q where j’ = ⎾j/3⏋ + 1 (or ⎾j/2⏋ + 1) and a primality certificate C(q) (which includes the
certificates of any smaller primes used to construct q) if requested.
from which a j-bit prime p is constructed as follows:
j-1 j
b) Select an integer x at random from the interval (2 , 2 – 2q].
c) Set p = x + ((1-x) mod 2q), t = (p – 1) div q (note q divides p – 1).
d) Apply the Pocklington’s primality test to p, with p-1 = F R where F = q, R = t.
If test returns “p prime”;
return p along with certificate C(p) (if a certificate is requested) and stop.
j
else if p < 2 – 2q;
set p = p + 2q, t = t + 2, and go to step d).
else go to step b).
When j < log (L), a j-bit prime q shall be constructed using trial division.
2 0
The certificate C for the k-bit prime N is the collection of certificates generated in step d) and the trial
division certificate C (q ).
0 0
The algorithm may be implemented by first setting j = k (for some n), and recursively computing bit-
n
lengths j = ⎾j /3⏋ + 1 (or ⎾j /2⏋ + 1) until j < log (L), upon which the j -bit prime q is constructed
i-1 i i 0 2 0 0
using trial division. The prime q is then used to construct the j -bit prime q via steps b) to d). The
0 1 1
prime q is then used to construct a j -bit prime q , and so forth until a k-bit prime N = q is generated.
1 2 2 n
j-1 j
Rather than increment the candidate prime p in step c) by 2q [in step d)], for some J in ( (2 – p) / 2q, (2
– p) / 2q ) the Pocklington test may be applied to elements in the sequence p, p+2q, p+4q, …, p+2Jq which
survive the sieving procedure described in C.1. The sieve process eliminates candidate primes that are
divisible by small primes used in the sieve.
NOTE Use of the alternative value j’ = ⎾j/2⏋ + 1 in step a) is equivalent to the Shawe-Taylor algorithm in
ISO/IEC 18032:2005 (and adapted from Reference [18]). The choice j’ = ⎾j/3⏋ + 1 makes use of the more general
version of Pocklington’s theorem given in D.2, and results in a more efficient algorithm due to fewer recursive steps.
10 © ISO/IEC 2020 – All rights reserved
Annex A
(normative)
Error probabilities
A.1 General
For any probabilistic test, the number of iterations that need to be performed depends on the error
probability of one iteration of the test. The error probability of one iteration varies depending on
whether the number to be tested has been selected at random, or whether it was chosen to have special
properties.
For the Miller-Rabin test, worst-case error estimates (A.2) are given for the probability that an iterated
application of the test accepts a given composite input number. The worst-case error estimates shall be
applied unless stated otherwise within this document.
For large and randomly chosen integers, good average-case error estimates can be given, which
significantly reduce the number of iterations of Miller-Rabin to be performed. The error estimates in A.3
apply only to the random search method of 8.3.2. In the case of the incremental search method of 8.3.3,
[5]
different error probabilities apply. To ensure the incremental search method achieves the requisite
-100
2 error probability, the number of iterations of Miller-Rabin to be performed shall be increased by
1. Thus, for example, a 1 024-bit candidate prime requires at least 5 iterations. Further, if the number
of iterations of Miller-Rabin is reduced for either search method, the candidate prime should also pass
a single iteration of the probabilistic Lucas test (D.3) before being accepted as a (probable) prime. As,
to date, there are no known examples of composites which pass a single iteration of Miller-Rabin (with
[15]
base/witness a = 2) and a single iteration of the Lucas test, i.e. Baillie-PSW pseudo-primes.
In general, the estimates depend on two parameters:
— k, the bit length of the numbers generated; and
— t, the number of times the test is iterated on each candidate.
A.2 Worst-case error estimate for t Miller-Rabin primality tests
The probability that a composite number is accepted by t (independent) Miller-Rabin tests is at most
t -100
(¼) (see Reference [9]). Thus, to ensure an error probability of at most 2 , t shall satisfy t ≥ 50.
A.3 Average-case error estimates for t Miller-Rabin primality tests
Table A.1 and Table A.2 contain estimates of the base-2 logarithm of the average-case error probability
for t Miller-Rabin tests. The underlined entries correspond to the minimum number of independent
-100
Miller-Rabin tests required to reach the 2 threshold. For instance, the entry for k = 256 and t = 16
-101
is −101, showing that the error probability for 16 Miller-Rabin tests of a 256-bit number is 2 . The
second sub-table shows that 4 Miller-Rabin tests of a 1 024-bit number limit the error probability to
-109
2 . The entries are derived from the formula provided in Appendix F of Reference [10] based on
results in References [5] and [9].
Table A.1 — Average-case error estimates for t Miller-Rabin primality tests (k = 256)
k\t 10 11 12 13 14 15 16 17
256 -80 -84 -88 -91 -95 -98 -101 -104
© ISO/IEC 2020 – All rights reserved 11
Table A.2 — Average-case error estimates for t Miller-Rabin primality tests (k ≥ 512)
k\t 1 2 3 4 5 6 7
512 -26 -47 -61 -73 -83 -92 -100
1 024 -42 -72 -93 -109 -124 -137 -148
1 536 -56 -92 -117 -137 -155 -171 -186
2 048 -67 -109 -137 -161 -182 -200 -217
3 072 -86 -137 -172 -201 -227 -249 -270
4 096 -103 -160 -201 -235 -264 -291 -315
6 144 -130 --200 -250 -292 -328 -361 -391
The average case error estimates for t iterations of the test assume that every iteration uses a random
base. Therefore, if one first uses a fixed base, e.g. a = 2, and then t-1 random bases, then the error
probabilities listed here should be used as if only t-1 iterations have been made.
-100
For bit-lengths 4 096 or greater, t = 1 satisfies the error probability bound of 2 . However,
implementations can want to consider using an additional round as a precaution that the necessary
conditions required for use of these tables are not strictly met.
In general, applying additional rounds of Miller-Rabin primality tests are permitted. For example,
certain applications may want the average-case error estimates to match the intended security level
for which the prime(s) are to be used. Further, for a fixed security level the size of the primes can differ
depending on the public key algorithm. For example, a 3 072-bit prime p used in Diffie-Hellman (over a
prime field) offers roughly 128 bits of security, whereas the prime factors for a 3 072-bit RSA modulus
are 1 536-bit numbers. Thus, in the case of Diffie-Hellman, 3 rounds of Miller-Rabin primality testing
would be required to match the 128 bit security level, and 4 rounds would be required for each of the
prime factors of a RSA modulus.
NOTE The average-case probabilities decrease as the bit-length of the prime increases.
12 © ISO/IEC 2
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.