CSA Preface 

Standards development within the Information Technology sector is harmonized with international standards development. Through the CSA Technical Committee on Information Technology (TCIT), Canadians serve as the SCC Mirror Committee (SMC) on ISO/IEC Joint Technical Committee 1 on Information Technology (ISO/IEC JTC1) for the Standards Council of Canada (SCC), the ISO member body for Canada and sponsor of the Canadian National Committee of the IEC. Also, as a member of the International Telecommunication Union (ITU), Canada participates in the International Telegraph and Telephone Consultative Committee (ITU-T). 

This Standard supersedes CAN/CSA-ISO/IEC 18032:06 (adopted ISO/IEC 18032:2005). At the time of publication, ISO/IEC 18032:2020 is available from ISO and IEC in English only. CSA Group will publish the French version when it becomes available from ISO and IEC. 

This Standard has been formally approved, without modification, by the Technical Committee and has been developed in compliance with Standards Council of Canada requirements for National Standards of Canada. It has been published as a National Standard of Canada by CSA Group. 

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.