In RSA: Fast factorization of N if d and e are known a comment under the OPs question stated that if the encrytion exponent e is small compared to N=p⋅q for the RSA-primes p,q (like e<√N) one could find k in de=1+kφ(N) by rounding deN as k is an integer and φ(N)≈N.
I don't know how to show this rigorously as I don't find a way to use e<√N and I'm unsure whether the floor function or some other approximation was meant. (For the following i went with the floor as it seemed to be the most reasonable)
As φ(N)≤N I know that:
k=⌊1N+k⌋≥⌊deN⌋
As φ(N)=N−p−q+1 is also know that:
⌊deN⌋=⌊1N+kφ(N)N⌋=⌊1N+kpq−p−q+1pq⌋=⌊1N+k(1N−1q−1p)⌋+k
So it would be nice to have ⌊1N+k(1N−1q−1p)⌋=0 as this would show the preposition.
Does this result even hold true?
No comments:
Post a Comment