🚀 go-pugleaf

In article <1992Jul30.213709.26515@sfc.sony.com> weaver@sfc.sony.com (Eric Weaver) writes:

[In RSA scheme, with N = PQ, and DE = 1 (mod (P-1)(Q-1))]

>
>Question for cognoscenti: How hard is it REALLY to guess or search D
>from PQ?
>-- 
>Eric Weaver  Sony AVTC  677 River Oaks Pkwy, MS 35  SJ CA 95134  408 944-4904
>& Eng. Asst., KFJC 89.7 -  Foothill College, Los Altos Hills, CA 94022

DE-1 is a multiple of (P-1)(Q-1) = phi(N).  Gary Miller showed
in his thesis how to factor general N in random polynomial time,
given an oracle that returns an arbitrary small multiple of
phi(N).  The reduction is quite efficient.  Therefore, any general
method for finding D (given E and N) would give a fast integer
factoring algorithm, which some would say is unlikely.

Jeff Shallit