[Resource Topic] 2006/093: RSA and a higher degree diophantine equation

Welcome to the resource topic for 2006/093

RSA and a higher degree diophantine equation

Authors: Abderrahmane Nitaj


Let N=pq be an RSA modulus where p, q are large primes of the same bitsize. We study the class of the public exponents e for which there exist an integer m with 1\leq m\leq {\log{N}\over \log{32}} and small integers u, X, Y and Z satisfying $$(e+u)Y^m-\psi(N)X^m=Z,$$ where \psi(N)=(p+1)(q-1). First we show that these exponents are of improper use in RSA cryptosystems. Next we show that their number is at least O\left(mN^{{1\over 2}+{\a\over m}-\a-\e}\right) where \a is defined by N^{1-\a}=\psi(N).

ePrint: https://eprint.iacr.org/2006/093

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .