Factorizarea RSA cunoscând forma lui p și q

Mă întreb dacă cunoașterea formei ambilor factori (p și q) ai unui modul RSA N este un ajutor semnificativ pentru factorizare sau nu.

De exemplu: p de forma 4k+3, deci (p-3)%4 = 0 și q de forma 4k+7, deci (q-7)%4 = 0

Dacă $k$ este la fel în cele două forme, adică $n=(4k+3)(4k+7)$, factorizarea este trivială: $p=\lceil\sqrt n\,\rceil-2$, $q=p+4$.

Presupunând că cei doi $k$ sunt independente de acum înainte: rețineți că pentru numere prime impare $p$ de o dimensiune dată, cantitatea $p\bmod4$ este împărțit aproximativ în mod egal $\{1,3\}$. Astfel, forma cunoscută oferă un bit de informații despre $p$. Primim aceleași informații despre $q$, dar observând $n\equiv1\pmod4$ deja permis să o deducă din $p\equiv3\pmod4$. Prin urmare, forma cunoscută oferă doar 1 bit de informații despre factorul de ajutor $n$: pentru un dat $n$ poate în cel mai bun caz jumătate din muncă. De asemenea, despre unul $n$ din patru dintr-un modul RSA normal are această formă, deci dacă problema a fost ușoară pentru aceștia $n$, RSA ar fi nesigură.