知道p和q形式的RSA因式分解

Question

我想知道RSA模N的两个因子(p和q)的形式是否对保理有很大帮助。

例如:表单4k+3的p，表4k+7的so (p-3)%4 =0和q，so (q-7)%4 =0

Answer 1

如果k在这两种形式中是相同的，即n=(4k+3)(4k+7)，那么分解是很简单的：p=\lceil\sqrt n\,\rceil-2，q=p+4。

假设这两个k从现在起是独立的:注意，对于给定大小的奇数素数p，数量p\bmod4在\{1,3\}中大约是平分的。因此，已知的表单提供了一些关于p的信息。我们得到了关于q的相同信息，但是观察n\equiv1\pmod4已经允许从p\equiv3\pmod4推断它。因此，已知的表单只提供1位关于帮助因子n的信息:对于给定的n，它最多只能提供一半的工作。同样，在普通RSA模数中，约有四分之一的n具有这种形式，因此，如果这些n很容易解决问题，则RSA是不安全的。