# $n=pq$ and $n=p^2q$. How to take the value of two $n$ is the same in security

For example, Paillier's RSA modulus is $$n=pq$$, but OU's RSA modulus is $$p^2q$$. I think when two $$n$$ are the same, the security of the two cryptographic schemes must be different. So for example, if I take 3072 for Paillier's $$n$$, how long should I take for OU's $$n$$?

In "I take 3072 for Paillier's $$n$$", 3072 is surely the bit size of $$n$$. Thus I'll read the question as:

How wide should be OU's $$n=p^2q$$ to be as safe as Paillier's $$n=pq$$ of 3072 bits?

The best known attack against both cryptosystems is the factorization of $$n$$.

The best known factorization method for $$n=pq$$ with $$p$$ and $$q$$ random primes of roughly the same size is GNFS, of cost $$L_n[1/3,4\cdot3^{-2/3}]$$, per L notation.

For factorization of $$n=p^2q$$, GNFS also works with similar cost, thus we must have $$n$$ at least 3072-bit. However, Lenstra's ECM is also to consider, and (I think) it's cost is about $$L_{\min(p,q)}[1/2,2^{1/2}]$$. Thus to maximize resistance to that later algorithm we should have $$p$$ and $$q$$ of next to the same size. That size must be at least 1024-bit to get a 3072-bit $$n$$. And if we do the math and ignore the $$o(1)$$ in $$L_k[\alpha,c]=e^{(c+o(1))\ln(k)^\alpha\ln(\ln(k))^{1-\alpha}}$$, we get that 1024-bit $$p$$ and $$q$$ is (barely) enough for ECM to be more costly than GNFS.

Hence we should have $$p$$ and $$q$$ of 1024-bit at least, e.g. in range $$[2^{1024-1/3},2^{1024}]$$ for 3072-bit $$n$$. If we want to err on the safe side because we ignored the $$o(1)$$, we can bump that a little to e.g. 1152-bit, e.g. in range $$[2^{1152-1/3},2^{1152}]$$ for 3456-bit $$n$$.

The same computation supports the mysterious Captain Nemo's "RSA Moduli Should Have 3 Prime Factors" quote.

Addition: supporting evidence in Mathematica, yielding 0.5… (resp. 10.3…) for the base-2 logarithm of the ratio of work between ECM @1024-bit (resp. @1152 bits) factors, to the work for GNFS @3072-bit product. Try It Online!.

L[n_, a_, c_] := Exp[c (Log[n]^a) (Log[Log[n]]^(1-a))];
LGNFS[n_] := L[n, 1/3, 4 3^(-2/3)];
LLenstra[p_] := L[p, 1/2, 2^(1/2)];
Log[2., LLenstra[2^{1024,1152}]/LGNFS[2^3072]]