math - 鉴于我们知道离散对数模 N 的最小解决方案，打破 RSA

Question

所以我试图找出离散对数问题和 RSA 之间的联系。我认为这就是以下问题试图做的事情。

Suppose you have an oracle which gives you the smallest positive x satisfying
the following congruence:
                                  g^x ≡ k (mod N) 
where N = p*q for some distinct primes p and q, and g and k are any integers.
We also have one more condition that (p -1)/2 and (q -1)/2 are both primes.

What is the quickest way to find p and q? i.e. factor N. 

所以我完全不知道如何解决这个问题。如果有人可以为我提供解决此问题的提示/解决方案，我将不胜感激。谢谢。

Answer 1

在g^x = 1中，解决方案x将始终是 的除法器(p-1)*(q-1)。选择一些不同的 g 值，您可能会找到 的大多数因子(p-1)*(q-1)。而作为(p-1)(q-1) = N - p - q + 1，知道(p-1)(q-1)并N导致知道p + q。知道N = p*q和p+q就像知道一个矩形的周长和面积一样，可以快速求解p和q。