$\newcommand{\alicebob}{#1 & \ra{#2} & #3\\[-5pt]}$ $\newcommand{\bobalice}{#1 & \la{#2} & #3\\[-5pt]}$ $\newcommand{\alicework}{#1 & &\\[-5pt]}$ $\newcommand{\bobwork}{ & & #1\\[-5pt]}$ $\newcommand{\work}{#1 & & #2\\}$ $\newcommand{\allwork}{ & #1 & \\}$ $\newcommand{\aliceseparator}{-------&&\\}$ $\newcommand{\bobseparator}{&&-------\\}$ $\newcommand{\foo}{\phantom{\text{bigarrowfitsallthis}}}$ $\newcommand{\ra}{% \vphantom{\xrightarrow{asd}}% \smash{\xrightarrow[\foo]{#1}}% }$ $\newcommand{\la}{% \vphantom{\xleftarrow{asd}}% \smash{\xleftarrow[\foo]{#1}}% }$ $\newcommand{\z}{\mathbb{Z}_{#1}}$ $\newcommand{\zq}{\mathbb{Z}_\varq}$ $\newcommand{\zqs}{\mathbb{Z}_q^\ast}$ $\newcommand{\zps}{\mathbb{Z}_p^\ast}$ $\newcommand{\zns}{\mathbb{Z}_{#1}^\ast}$ $\require{action} \newcommand{\sampleSymb}{ {\overset{\$}{\leftarrow}} }\newcommand{\field}{\mathbb{F}_{#1}}\newcommand{\sample}{#1\sampleSymb\zq}\newcommand{\sampleGeneric}{#1\sampleSymb#2}\newcommand{\sampleInterval}{#1\sampleSymb\interval{#2}}\newcommand{\sampleRange}{#1\sampleSymb\range{#2}}\newcommand{\samplezqs}{\class{hover}{#1\sampleSymb\zqs}}\newcommand{\sampleN}{\class{hover}{#1\sampleSymb\z{#2}}}\newcommand{\sampleNs}{\class{hover}{#1\sampleSymb\z{#2}^\ast}}\newcommand{\equalQ}{\overset{?}{=}}\newcommand{\gQ}{\overset{?}{>}}\newcommand{\inQ}{\overset{?}{\in}}\newcommand{\cgroup}{\mathbb{G}}\newcommand{\hash}{\mathsf{Hash}({#1})}\newcommand{\hashbit}{\mathsf{Hash}({#1})\verb+[0:#2]+}\newcommand{\naturals}{\mathbb{N}}\newcommand{\sqfree}{L_\mathsf{square-free}}\newcommand{\ceil}{\lceil #1 \rceil}\newcommand{\sampleSet}{\class{hover}{#1\sampleSymb#2}}\newcommand{\bunch}{\{ #1_i\}_{i=1}^m}\newcommand{\bunchi}{\{ #1\}_{i=1}^m}\newcommand{\forb}{\text{ for }i=1,\ldots,m}\newcommand{\interval}{[0, #1[}\newcommand{\range}{[#1]}\newcommand{\rangeone}{\{1, \dots,#1 -1 \}}\newcommand{\vara}{\class{var var_a}{a}}\newcommand{\varb}{\class{var var_b}{b}}\newcommand{\varc}{\class{var var_c}{c}}\newcommand{\vard}{\class{var var_d}{d}}\newcommand{\varh}{\class{var var_h}{h}}\newcommand{\varg}{\class{var var_g}{g}}\newcommand{\varu}{\class{var var_u}{u}}\newcommand{\varx}{\class{var var_x}{x}}\newcommand{\varX}{\class{var var_X}{X}}\newcommand{\varz}{\class{var var_z}{z}}\newcommand{\varr}{\class{var var_r}{r}}\newcommand{\varq}{\class{var var_q}{q}}\newcommand{\varp}{\class{var var_p}{p}}\newcommand{\vare}{\class{var var_e}{e}}\newcommand{\vary}{\class{var var_y}{y}}\newcommand{\varw}{\class{var var_w}{w}}\newcommand{\varprover}{\class{var var_Prover}{\text{Prover}}}\newcommand{\varprover}{\class{var var_Prover}{\text{Prover}}}\newcommand{\varverifier}{\class{var var_Verifier}{\text{Verifier}}}\newcommand{\varN}{\class{var var_N}{N}}\newcommand{\rhovar}{\class{var var_ρ}{\rho}}\newcommand{\sigmavar}{\class{var var_σ}{\sigma}}\newcommand{\thetavar}{\class{var var_θ}{\theta}}\newcommand{\muvar}{\class{var var_μ}{\mu}}\newcommand{\true}{\mathsf{true}}\newcommand{\false}{\mathsf{false}}$Number is product of two primes ## Product of primes # One way to prove that some number$\varN$is the product of two primes$\varN = \varp \varq$is by showing that: •$\varN$is square-free •$\varN$only has two divisors If we only showed that$\varN$is square-free, then it could be of the form$\varN = \varp \varq \varr$. On the other hand, if we only proved that$\varN$has two divisors, it could be of the form$\varN = \varp^2\varq$. When the primes are congruent with$3 \; \mathsf{mod}\; 4$, we can show that$\varN\$ is the product of two primes much more efficiently with the Paillier-Blum modulus proof.

Number is square-free
Proves that a number is square-free.
Two prime divisors
Proves that a number has two prime divisors.
Product of two primes
Proves that a number is the product of two distinct primes: in parallel, run the square-freeness proof together with the two-prime-divisors proof.
Paillier-Blum Modulus
An efficient proof that shows a number is the product of two primes congruent with 3 mod 4.