鉴于我们知道离散日志的最小解决方案，打破 RSA mod N
Breaking RSA given we know minimal solution to discrete log mod N
所以我想弄清楚离散日志问题和 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.
所以我完全不知道如何解决这个问题。如果有人能提供 hints/solution 来解决这个问题，我将不胜感激。谢谢。
在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。
所以我想弄清楚离散日志问题和 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.
所以我完全不知道如何解决这个问题。如果有人能提供 hints/solution 来解决这个问题，我将不胜感激。谢谢。
在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。