Editing Paillier cryptosystem (section)

=== Key generation ===
#Choose two large prime numbers <math>p</math> and <math>q</math> randomly and independently of each other such that <math>\gcd(pq, (p-1)(q-1))=1</math>. This property is assured if both primes are of equal length.<ref name="katzLindell">Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007</ref>
#Compute <math>n=pq</math> and <math>\lambda=\operatorname{lcm}(p-1,q-1)</math>. lcm means [[Least common multiple|Least Common Multiple]]. 
#Select random integer <math>g</math> where <math>g\in \mathbb Z^{*}_{n^{2}}</math>
#Ensure <math>n</math> divides the order of <math>g</math> by checking the existence of the following [[modular multiplicative inverse]]: <math>\mu = (L(g^\lambda \bmod n^2))^{-1} \bmod n</math>,
:where function <math>L</math> is defined as <math>L(x) = \frac{x-1}{n}</math> .
::Note that the notation <math>\frac{a}{b}</math> does not denote the modular multiplication of <math>a</math> times the [[modular multiplicative inverse]] of <math>b</math> but rather the [[quotient]] of <math>a</math> divided by <math>b</math>, i.e., the largest integer value <math>v \ge 0</math> to satisfy the relation <math>a \ge vb</math>.

*'''The public (encryption) key is <math>(n, g)</math>.'''
*'''The private (decryption) key is <math>(\lambda, \mu).</math>'''
If using p,q of equivalent length, a simpler variant of the above key generation steps would be to set <math>g = n+1, \lambda = \varphi(n),</math> and <math>\mu = \varphi(n)^{-1} \bmod n</math>, where <math>\varphi(n) = (p-1)(q-1)</math> .<ref name="katzLindell" />
The simpler variant is '''recommended''' for implementational purposes, because in the general form the calculation time of <math>\mu</math> can be very high with sufficiently large primes p,q.