# Why are the primes all the same size in pqRSA?

pqRSA is MP-RSA with 4096-bit primes to build up a modulus of up to 1TB.

If the objective is to make processing the modulus as expensive as possible for the quantum computer why not use just two 4096-bit primes with the rest being 1024-bit primes? Would that offer comparable security?

• I'd wager that unless the combination of the multiplication of the primes are quantum safe (and it isn't) the combined quantum complexity is basically not the multiplication of the complexities of having 2 + 1 primes (etc.). That's my intuition, you'd have to dive into the paper to find out. Dec 15, 2023 at 20:27
• @kodlu I've included a link; it is a joke submission (by DJB) to NIST PQC competition, more information on our own site Dec 15, 2023 at 20:33

No, it would not. As noted in the PQ-RSA paper, there is a Grover accelerated form of the elliptic curve method GEECM which can detect a prime factor $$p$$ of $$N$$ with $$L_p[1/2,1]$$ quantum work (essentially by performing a Grover search for an elliptic curve mod $$p$$ with smooth order). One could use this to extract all of the 1024-bit primes with work only half of the security margin. We’d then be left with a product of 2 4096-bit primes which would be trivial for Shor’s algorithm.
• @JamesArlington for an $L_p[1/2,1]$ algorithm the cost in bits roughly scales according to the square root of the bit size of $p$. I our case then, if it takes $2^\lambda$ quantum operations to detect a 4096-bit prime, then it takes roughly $2^{\lambda/2}$ quantum operations to detect a 1024-bit primes. Dec 16, 2023 at 6:56