Let N = pq be the product of two large primes. Consider Chinese remainder theorem-Rivest, Shamir, Adleman (CRT-RSA) with the public encryption exponent e and private decryption exponents d_p, d_q. It is well known that given any one of d_p or d_q (or both) one can factorise N in probabilistic poly(log N) time with success probability almost equal to 1. Though this serves all the practical purposes, from theoretical point of view, this is not a deterministic polynomial time algorithm. In this paper, we present a lattice-based deterministic poly(log N) time algorithm that uses both d_p, d_q   (in addition to the public information e, N) to factorise N for certain ranges of d_p, d_q. We like to stress that proving the equivalence for all the values of d_p, d_q may be a nontrivial task.

Keywords:    CRT-RSA,  cryptanalysis,  factorisation,  LLL algorithm,  RSA

RSA¹⁷ is one of the most popular cryptosystems in the history of cryptology. Let us briefly describe the idea of RSA as follows:

• primes p, q, with q<p< 2q,
• N = pq, φ(N) = (p − 1)(q − 1),
• e, d are such that ed =1+ k φ(N), k ≥ 1,
• N, e are publicly available and plaintext M is encrypted as C ≡ M^e mod N,
• The secret key d is required to decrypt the ciphertext as
  M ≡ C^d mod N.

The study of RSA is one of the most attractive areas in cryptology research as evident from many excellent works¹,¹⁰,¹⁵. Rivest¹⁷, et al. itself presents a probabilistic polynomial time algorithm that on input N, e, d provides the factorisation of N; this is based on the technique provided by Miller¹⁶,¹⁸. It has been proved⁷,¹⁴ that given N, e, d, one can factor N in deterministic poly(log N) time provided ed ≤ N² .

Speeding up RSA encryption and decryption is of serious interest and for large N as both e, d cannot be small at the same time. For fast encryption, it is possible to use smaller e, e.g., the value as small as 2¹⁶ + 1 is widely believed to be a good candidate. For fast decryption, the value of d needs to be small. However, Wiener¹⁹ showed that for $d<\frac{1}{3}{N}^{\frac{1}{4}}$ , N can be factorised easily. Later, Boneh-Durfee² increased this bound up to d<N0.292. Thus, use of smaller d is in general not recommended. In this direction, an alternative approach has been proposed by Wiener¹⁹ exploiting the Chinese Remainder Theorem (CRT) for faster decryption. The idea is as follows:

• the public exponent e and the private CRT exponents d_p and d_q are used satisfying ed_p ≡ 1 mod (p − 1) and ed_q ≡ 1 mod (q − 1),
• the encryption is same as standard RSA,
• to decrypt a ciphertext C one needs to compute $M_{\text{1}}\equiv C^{d_p}$ mod p and $M_{\text{2}}\equiv C^{d_q}$ mod q,
• using CRT, one can get the plain text $M\in {\mathbb{Z}}_N$ such that M ≡ M₁ mod p and M ≡ M₂ mod q.

This variant of RSA is popularly known as CRT-RSA. One may refer to Jochemsz & May¹² and the references therein for state-of-the-art analysis on CRT-RSA.

Let us now outline the organization of this paper. Some preliminaries required in this area are discussed in section 1.1 and 1.2. A lattice-based technique was used to show that one can factorise N in deterministic polynomial time from the knowledge of N, e, d_p , d_q for certain ranges of d_p , d_q. Section 3 concludes the paper.

1.1   Probabilistic Polynomial Time Algorithm

Given N, e and any one of d_p , d_q (or both), there exists a well known solution to factorise N in probabilistic poly(log N) time with probability almost 1. An important work in this direction shows that with the availability of decryption oracle under a fault model, one can factorise N in poly(log N) time [3,Section 2,2] and the idea has been improved by Lenstra¹³.

Without loss of generality, consider that d_p is available. One can pick any random integer W in [2, N − 1]. If gcd(W, N) ≠ 1, then we already have one of the factors. Else, we consider gcd ($W^{e{d}_p-1}-1$ , N). First note that p divides. This is because, edp ≡ 1 mod (p − 1), i.e., ed^p − 1= k(p − 1) for some positive integer k and hence $W^{e{d}_p-1}-1$ =Wk(p−1)−1 is divisible by $W^{e{d}_p-1}-1$ p. Thus if q does not divide $W^{e{d}_p-1}-1$  then

gcd($W^{e{d}_p-1}-1$ , N) = p (this happens with probability almost equal to 1). If q too divides $W^{e{d}_p-1}-1$ , then gcd($W^{e{d}_p-1}-1$ , N) = N and the factorisation is not possible (this happens with a very low probability).

Thus, when both d_p, d_q are available, one can calculate both gcd($W^{e{d}_p-1}-1$ , N) and gcd($W^{e{d}_q-1}-1$ , N). If both of them are N (which happens with a very low probability) then the factorisation is not possible by this method.

Given e, d_p, d_q and N, let us define,
T _{e,dp ,dq ,N} = {W $\in$ [2, N − 1]| gcd(W, N)=1,
     gcd($W^{e{d}_p-1}-1$ , N) = N and gcd($W^{e{d}_p-1}-1$ , N) = N}
T _e,dp,N = {W$\in$ [2, N − 1]| gcd(W, N)=1,
     gcd($W^{e{d}_p-1}-1$ , N) = N} and
T _e,dq,N = {W $\in$ [2, N − 1]|
gcd(W, N)=1, gcd($W^{e{d}_p-1}-1$ , N) = N}.

It is easy to note that T_e,dp,dq,N = T_e,d_p,_N ∩ T_e,d_q,_N . Let us now provide some examples in Table 1. It is clear that while |T_e,dp,dq,N | is quite large for one prime-pair, it is very small for the other.

Proposition 1

Consider CRT-RSA with N = pq, encryption exponent e and decryption exponents d_p and d_q. Let g1 = gcd(p−1, q −1),
gp=gcd(ed_p−1, q−1), gq = gcd(ed_q −1, p−1) and ge = gcd(ed_p − 1, ed_q − 1). Then |T_e,dp,N| = gp(p − 1) − 1, |T_e,dq,N| = gq(q − 1) − 1 and |T_{e,dp ,dq ,N}| = gp gq − 1. Further, $g_1^2$ − 1 ≤|Te,dp,dq,N|≤ $g_e^2$ − 1.

Proof

We have g_p = gcd(ed_p − 1, q − 1). Then there exists a subgroup S_q of order g_p in ${\mathbb{Z}}_q^{*}$  such that for any $w\in S_q$ , we have q|wgp − 1. Now consider any $w_1\in {\mathbb{Z}}_p^{*}$ and w2 from Sq. By CRT, there exists a unique $W\in {\mathbb{Z}}_N^{*}$ such that W ≡ w1 mod p and
W ≡ w2 mod q, and vice versa. Thus the number of such W’s is gp(p − 1). It is evident that for all these W’s, we have
gcd(W, N) = 1 and N|W edp−1 − 1. We can also observe that any $W\in T_{e,d_p,N}$ can be obtained in this way. Discarding the case
W = 1, we get | T_e,dp,N | = gp(p − 1) – 1.
Similarly, we have gq = gcd(edq − 1, p − 1). Then there exists a subgroup Sp of order gq in ${\mathbb{Z}}_p^{*}$  such that for any $w\in S_p$ , we have p|wgq − 1. In the same manner, we get
|Te,dq,N | = gq(q − 1) – 1.
Now consider any $w_1\in S_p$ and $w_2\in S_q$ . By CRT, there exists a unique $W\in {\mathbb{Z}}_N^{*}$ such that W ≡ w1 mod p and W ≡ w2 mod q, and vice versa. Thus the number of such W’s is g_pg_q. It is evident that for all these W’s, we have gcd(W, N) = 1,
N|W ^edp−1 − 1 and N|W ^edq−1 − 1. One may observe that any
W ÎT_e,d_p,d_q,N  can be obtained in this manner. Discarding the case W = 1, we get |T_e,d_p,d_q,N | = g_pg_q − 1.
Consider ed_p − 1= k(p − 1) and ed_q − 1= l(q − 1). Then we get |T_e,d_p,d_q,N |≥ $g_1^2$  − 1, as g1 divides both g_p and g_q. Since g_e = gcd(ed_p − 1, ed_q − 1) = gcd(k(p − 1), l(q − 1)), each of gp, gq divides ge. Thus the bounds on |Te,dp,dq,N | follow.
Given e, N, dp, dq, one can get ge easily, and thus the upper bound of |T_e,d_p,d_q,N | is immediately known. If ge is bounded by poly(log N), then it is enough to try $g_e^2$ many distinct W’s to factorise N in poly(log N) time. However, from proposition 1, it is clear that |T_e,d_p,d_q,N | may not be bounded by poly(log N) as g_p,g_q may not be bounded by poly(log N) in all the cases. Thus we have the following question, where an affirmative answer will transform the probabilistic algorithm to a deterministic one. Is it possible to identify a W $\in$ [2,N − 1] \ T_e,d_p,d_q,N  in poly(log N) time?
To our knowledge, an affirmative answer to the above question is not known. Thus, from theoretical point of view, getting a deterministic polynomial time algorithm for factorising N with the knowledge of N, e, d_p,d_q is important. We solve it using lattice-based technique.

1.2 Preliminaries on Lattices

Let us present some basics on lattice reduction techniques. Consider the linearly independent vectors u1,...,uω , $\in {\mathbb{Z}}^n$ where ω ≤ n. A lattice, spanned by {u1,...,uω}, is the set of all linear combinations of u1,...,uω, i.e., ω is the dimension of the lattice. A lattice is called full rank when ω = n. Let L be a lattice spanned by the linearly independent vectors u1,...,uω, where u1,...,uω $\in {\mathbb{Z}}^n$ . By $u_1^{*}$ ,......,$u_w^{*}$ , we denote the vectors obtained by applying the Gram-Schmidt process to the vectors u1,...,uω.
The determinant of L is defined as $\det (L)={\prod }_{i=1}^w\parallel u_i^{*}\parallel$ , where ||.|| denotes the Euclidean norm on vectors. Given a polynomial $g(x,y)=\sum a_{i,j}{x}^i{y}^j$ , we define the Euclidean norm as $\parallel g(x,y)\parallel =\sqrt{{\sum }_{i,j}{a}_{i,j}^2}$    and infinity norm as $\parallel g(x,y)\parallel \infty ={\max }_{i,j}\left|a_{i,j}\right|$ .
It is known that given a basis u1,...,uω of a lattice L, the LLL algorithm¹³ can find a new basis b1,...,bω of L with the following properties.

– $\Vert b_i^{*}\Vert {}^2\le 2{\Vert b_{i+1}^{*}\Vert }^2$, for 1 ≤ i < ω.
– For all i, if $b_i=b_i^{*}+{\displaystyle {\sum }_{j=1}^{i-1}{\mu }_{i,j}{b}_j^{*}}$ then $\left|{\mu }_{i,j}\right|\le \frac{1}{2}$ for all j.
–  $\Vert b_i\Vert \le 2^{\frac{w(w-1)+(i-1)(i-2)}{4(w-i+1)}}\det {(L)}^{\frac{1}{w-i+1}}$   for i =1,...,ω.

Deterministic polynomial time algorithms has been presented by Coppersmith⁴ to find small integer roots of (i) polynomials in a single variable mod N, and of (ii) polynomials in two variables over the integers. The idea of Coppersmith4 extends to more than two variables also, but in that event, the method becomes heuristic.
A simpler algorithm by Coron⁵, than Coppersmith⁴ has been presented in this direction, but it was asymptotically less efficient. Later, a simpler idea by Coron⁶ than Coppersmith⁴ has been presented with the same asymptotic bound as in Coppersmith⁴. Both the works of Coron⁵,⁶ depends on the result of Howgrave-Graham⁸.
The results of May¹⁴, in finding the deterministic polynomial time algorithm to factorise N from the knowledge of e, d, uses the techniques presented by Coppersmith4 & Coron⁵. Further, the work of Coron and May⁷ exploits the technique presented in Howgrave-Graham⁹.

2.     DETERMINISTIC POLYNOMIAL TIME ALGORITHM

In this section we consider that both d_p, d_q are known apart from the public information N, e. We start with the following lemma. In the following results, we consider $p\approx N^{{\gamma }_1}$  as the bit size of p can be correctly estimated in log N many attempts.

Lemma 1
Let $e\text{ =}{N}^{\alpha }$ ,$d_p\le N^{{\delta }_1}$ ,$d_q\le N^{{\delta }_2}$ . Suppose p > q and $p\approx N^{{\gamma }_1}$ .  If both d_p, d_q. are known then one can factor N in deterministic poly(log N) time if 2α + δ1 + δ2 ≤ 2 − γ1.

Proof
We have edp − 1= k(p − 1), edq − 1= l(q − 1) for some positive integers k, l.
So,$kl=\frac{(e{d}_p-1)(e{d}_q-1)}{(p-1)(q-1)}$
Let $A=\frac{(e{d}_p-1)(e{d}_q-1)}{N}$. Now $\left|kl-A\right|=(e{d}_p-1)(e{d}_q-1)\frac{N-(p-1)(q-1)}{N(p-1)(q-1)}\approx \frac{e{d}_{p}e{d}_p(p+q)}{N^2}\le N^{2\alpha +{\delta }_1+{\delta }_2+{\gamma }_1-2}$ (neglecting the small constant).

So, as long as, 2α + δ1 + δ2 ≤ 2 − γ1, we have $kl=\lceil A\rceil$ . After finding kl, one gets (p − 1)(q − 1) and hence p + q can be obtained immediately, which factorises N. In the next result, we use the idea of Coppersmith⁴.

Theorem 1
Let $e\text{ =}{N}^{\alpha }$ ,$d_p\le N^{{\delta }_1}$ ,$d_q\le N^{{\delta }_2}$   . Suppose p is estimated as $N^{{\gamma }_1}$ . Further consider that an approximation p0 of p is known such that $\left|p-p_0\right|<N^{\beta }$ .
Let $k_0=\lfloor \frac{e{d}_p}{p_0}\rfloor ,q_0=\lfloor \frac{N}{p_0}\rfloor ,l_0=\lfloor \frac{e{d}_p}{q_0}\rfloor$ and

g = gcd(N –1,edq–1 + l0–l0N, ed_p–1 + k₀– k₀ N) = Nη
If both d_p , d_q are known then one can factor N in deterministic poly(log N) time if
α² + αδ₁ +2αβ +δ₁β −2αγ₁ −${\gamma }_1^2$ +αδ₂ +δ₁δ₂
+βδ₂ −2γ₁δ₂ −2βη +2γη –η₂ −α−δ₁ +β +2η −1 < 0
provided 1+3γ1 − 2β − δ1 − α − η ≥ 0.

Proof
We have ed_p = 1+ k(p − 1) and ed_q = 1+ l(q − 1). So $k=\frac{e{d}_p-1}{p-1}$ . We also have$k_0=\frac{e{d}_p}{p_0}$
then,
$\left|k-k_0\right|=\left|\frac{e{d}_p-1}{p-1}-\frac{e{d}_p}{p_0}\right|\approx \left|\frac{e{d}_p}{p}-\frac{e{d}_p}{p_0}\right|=\frac{e{d}_p\left|p-p_0\right|}{p{p}_0}\le N^{\alpha +{\delta }_1+\beta -2{\gamma }_1}$ Considering $q_0=\frac{N}{p_0}$ , it can be shown that,|q −q0| <N1+β-2γ1, neglecting the small constant. Assume, $q=N^{{\gamma }_{\text{2}}}$ , where γ2 =1–γ1 . So if we take $l_0=\frac{e{d}_p}{p_0}$ .
then  $\left|k-k_0\right|=\left|\frac{e{d}_p-1}{p-1}-\frac{e{d}_p}{p_0}\right|\approx \left|\frac{e{d}_p}{p}-\frac{e{d}_p}{p_0}\right|=\frac{e{d}_p\left|p-p_0\right|}{p{p}_0}\le N^{\alpha +{\delta }_1+\beta -2{\gamma }_1}$

Considering $q_0=\frac{N}{p_0}$,it can be shown that $\left|q-q_0\right|<N^{1+\beta -2{\gamma }_1}$, neglecting the small constant. Assume, $q=N^{{\gamma }_{\text{2}}}$ , where  γ2 =1- γ1 . So if we take $l_0=\frac{e{d}_p}{p_0}$ then$\begin{array}{l}\left|l-l_0\right|=\left|\frac{e{d}_q-1}{q-1}-\frac{e{d}_q}{q_0}\right|\approx \left|\frac{e{d}_q}{q}-\frac{e{d}_q}{q_0}\right|\\ =\frac{e{d}_q\left|q-q_0\right|}{q{q}_0}\le N^{\alpha +{\delta }_2+1+\beta -2{\gamma }_1-2{\gamma }_2}=N^{\alpha +{\delta }_2+\beta -1}\end{array}$

Let k1 = k − k₀ and l₁ = l − l₀. We have ed_p + k − 1= kp. So ed_p + k₀ + k₁ − 1= (k₀ + k₁)p. Similarly, ed_q+l₀+l₁−1=(l₀ + l₁)q. Now multiplying these equations, we get
(ed_p − 1+ k₀)(ed_q − 1+ l₀)+ k1(ed_q − 1+ l₀)
+ l₁(ed_p − 1+ k₀)+ k₁l₁ =(k₀ + k₁)p(l₀ + l₁)q

Now if we substitute k₁, l₁ by x, y respectively, then
(ed_p − 1+ k0)( ed_p − 1+ l₀)+ x(ed_q − 1+ l₀)
+ y(ed_p − 1+ k₀)+ xy =( k₀ + x)_p(l₀ + y)_q

Hence we have to find the solution k₁, l₁ of
(ed_p − 1+ k₀)( ed_q − 1+ l₀)+ x(ed_q− 1+ l₀)
+ y(ed_p − 1+ k₀)+ xy =( k₀ + x)p(l₀ + y)q
i.e., we have to find the roots of $f^{\prime }$ (x, y) = 0, where
$f^{\prime }$ (x, y) = (1 − N)xy + x(ed_q − 1+ l0 − l₀N)
+ y(ed_p−1+k₀−k0N)+( ed_p− 1+ k₀)( ed_q− 1+ l₀) − k₀ l₀ N.
We have
g = gcd(1 − N, ed_q − 1+ l₀ − l₀ N, ed_p − 1+ k₀ − k₀N)= Nη .
Let $f(x,y)=\frac{f^{\prime }(x,y)}{g}$ , X = $N^{\alpha +{\delta }_1+\beta -2{\gamma }_1}$ and Y = $N^{\alpha +{\delta }_2+\beta -1}$ . Clearly X, Y are the upper bounds of (k₁,l₁), the root of f. 
Thus,

$\begin{array}{l}W={\Vert f\left(xX,yY\right)\Vert }_{\infty }\ge \frac{X(e{d}_p-1+l_0-l_{0}N)}{g}\\ \approx \frac{XlN}{g}{\text{ = N}}^{\text{2}\alpha +{\delta }_{\text{1}}+\delta {}_{\text{2}}+\beta -{\gamma }_{\text{1}}-\eta }\end{array}$ Then from Coppersmith4 we need $XY<W^{\frac{2}{3}}$ , which implies 2α + δ1 + δ2 +2η< 3 + 4(γ1 − β)                                        (1)

If one of the variables x, y is significantly smaller than the other, we give some extra shifts on x or y. Without loss of generality, let us assume that k₁ is significantly smaller than l₁. Following the ‘extended strategy’ of Jochemsz and May¹¹,we know that these polynomials can be found by lattice reduction if $X^{s_1}{Y}^{s_2}<W^s$ for $s_j={\displaystyle \sum {}_{x^{i_1}{y}^{i_2}\in M/S^{i_j}}}$  
where$s=\left|S\right|$ , j=1, 2. One can check that

$s_1=\frac{3}{2}{m}^2+\frac{7}{2}m+\frac{t^2}{2}+\frac{5}{2}t+2mt+2$

,$s_2=\frac{3}{2}{m}^2+\frac{7}{2}m+t+mt+2$
,
and s =(m + 1)2 + mt + ts = (m + 1)2 + mt + t

Let t = τm. Neglecting the lower order terms we get that $X^{s_1}{Y}^{s_2}<W^s.$  is satisfied when $\left(\frac{3}{2}+\frac{{\tau }^2}{2}+2\tau \right)\left(\alpha +{\delta }_1+\beta \text{ - }2{\gamma }_1\right)+(\frac{3}{2}+\tau )\left(\alpha +{\delta }_2+\beta -1\right)<\left(1+\tau \right)\left(2\alpha +{\delta }_1+{\delta }_2+\beta -{\gamma }_1-\eta \right),$
i.e., when $\left(\frac{\alpha }{2}+\frac{{\delta }_1}{2}+\frac{\beta }{2}-{\gamma }_1\right){\tau }^2+\left(\alpha +{\delta }_1+\text{ 2}\beta \text{ - 3}{\gamma }_1-1+\eta \right)\tau +\left(\alpha +\frac{{\delta }_1+{\delta }_2}{2}+2\beta -2{\gamma }_1-\frac{3}{2}+\eta \right)<0$

In this case the value of τ for which the left hand side of the above inequality is minimum is $\tau =\frac{1+3{\gamma }_1-2\beta -{\delta }_1-\alpha -\eta }{\alpha +{\delta }_1+\beta -2{\gamma }_1}$ . As $\tau \ge 0$ , we need $1+3{\gamma }_1-2\beta -{\delta }_1-\alpha -\eta \ge 0$ . Putting this optimal value of τ we get the required condition as ${\alpha }^2+\alpha {\delta }_1+2\alpha \beta +{\delta }_1\beta -2\alpha {\gamma }_1-\gamma \frac{2}{1}+\alpha {\delta }_2+{\delta }_1{\delta }_2+\beta {\delta }_2-2{\gamma }_1{\delta }_2-2\beta \eta -{\eta }^2-\alpha -{\delta }_1+\beta +2\eta -1<0.$

The strategy presented by Jochemsz and May¹¹ works in polynomial time in log N. As we follow the same strategy, N can be factored from the knowledge of N, e, d_p, d_q in deterministic polynomial time in log N.
As the condition given in Theorem 1 is quite involved, we present a few numerical values in Table 2.

Corollary 1
Let $e\text{ =}{N}^{\alpha }$ ,$d_p<N^{{\delta }_1}$ ,$d_q<N^{{\delta }_2}$   .
Let g = gcd(N − 1, ed_p − 1, ed_q − 1) = N^η .
If N, e, d_{p, dq} are known then N can be factored in deterministic polynomial time in log N when
2α + δ1 + δ2 +2η< 3.

Proof
Since in this case we do not consider any approximation of p, q, we take β = γ. Putting this value of β in Inequality 1, we get the desired result.
For practical purposes, p, q are same bit size and if we consider that no information about the bits of p is known, then we have ${\gamma }_{\text{1}}={\gamma }_{\text{2}}=\beta =\frac{1}{2}$ . In this case, we require ${\alpha }^{\text{2}}+\alpha {\delta }_{\text{1}}+\alpha {\delta }_{\text{2}}+{\delta }_{\text{1}}{\delta }_{\text{2}}-{\eta }^{\text{2}}-\alpha -\frac{1}{2}{\delta }_{\text{1}}-\frac{1}{2}{\delta }_{\text{2}}+\text{2}\eta -\frac{3}{4}<0$ as well as $\frac{3}{2}-{\delta }_{\text{1}}-\alpha -\eta \ge 0$ .
As discussed in Section 1.1, if |T_e,dp,dq,N | is small, then one can easily prove the deterministic polynomial time equivalence. However, this idea cannot be applied when |T_e,d_p,d_q,N | is large. In such an event, our lattice based technique provides a solution for certain ranges of d_p, d_q. In all our experiments we start with large g1, e.g., of the order of 100 bits. In such cases, |T_e,d_p,d_q,N | is large as $g\frac{2}{1}-1$   ≤|T_e,d_p,d_q,N | following Proposition 1. One may note that the g₁ in Proposition 1 divides the g in Theorem 1.
Let us now present some experimental results in Table 3. Our experiments are based on the strategy of Coron₅ as it is easier to implement. We have written the programs in SAGE 3.1.1 over Linux Ubuntu 8.04 on a computer with Dual CORE Intel(R) Pentium(R) D 1.83 GHz CPU, 2 GB RAM and 2 MB Cache. We take large primes p, q such that N is of 1000 bits. We like to point out that the experimental results cannot reach the theoretical bounds due to the small lattice dimensions.

Towards theoretical interest, we have presented a deterministic poly(log N) time algorithm that can factorise N given e, d_p and d_q for certain ranges of d_p , d_q. This algorithm is based on lattice reduction techniques.

The authors like to thank Dr A Venkateswarlu for pointing out Proposition 1 and Mr Sourav Sen Gupta for presenting detailed comments on this version.

1. Boneh, D. Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 1999, 46(2), 203-13.

2. Boneh, D. & Durfee, G. Cryptanalysis of RSA with private key d less than N0.292. IEEE Trans. Infor­m. Theory, 2000, 46(4),1339-349,

3. Boneh, D.; DeMillo, R.A. & Lipton, R.J. On the importance of eliminating errors in cryptographic compu­tations. Journal of Cryptology, 2001, 14(2), 101-19.

4. Coppersmith, D. Small solutions to polynomial equations and low exponent vulnerabilities. Journal of Cryp­tology, 1997, 10(4), 223-60.

5. Coron, J.S. Finding small roots of bivariate integer equations revisited. Eurocrypt 2004, Lecture Notes in Computer Science, LNCS 3027, 2004, pp. 492-505.

6. Coron, J. S. Finding small roots of bivariate integer equations: A direct approach. Crypto 2007, Lecture Notes in Computer Science,Lecture Notes in Computer Science, LNCS 4622, 2007, pp. 379-94.

7. Coron, J. S. & May, A. Deterministic polynomial-time equivalence of computing the RSA secret key and factoring. Journal of Cryptology, 2007, 20(1), 39-50.

8. Howgrave-Graham, N. Finding small roots of univariate modular equations revisited. In Proceedings of Cryp­tography and Coding,Lecture Notes in Computer Science, LNCS1355, 1997, pp.131-42.

9. Howgrave-Graham, N. Approximate integer common divisors. In Proceedings of CaLC’01, Lecture Notes in Computer Science, LNCS 2146, 2001, pp. 51-66.

10. Jochemsz, E. Cryptanalysis of RSA variants using small roots of polynomials. Technische Universiteit Eindhoven, 2007. PhD Thesis.

11. Jochemsz, E. & May, A. A Strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants. Asiacrypt 2006, Lecture Notes in Computer Science, LNCS 4284, 2006, pp. 267-82.

12. Jochemsz, E. & May, A. A polynomial time attack on RSA with private CRT-exponents smaller than N0.073. Crypto 2007, Lecture Notes in Computer Science, LNCS 4622, 2007, pp. 395-411.

13. Lenstra, K.; Lenstra, H.W. & Lov´asz, L. Factoring polynomials with rational coefficients. Mathematische Annalen, 1982, 261, 513-34.

14. May, A. Computing the RSA secret key is deterministic polynomial time equivalent to factoring. Crypto 2004, Lecture Notes in Computer Science, LNCS 3152, 2004, pp. 213-19.

15. May, A. Using LLL-reduction for solving RSA and factorisation problems: A survey. LLL+25 Confer­ence in honour of the 25th birthday of the LLL algorithm, 2007. http://www.informatik.tu­darmstadt.de/KP/alex.html [Accessed on 23 December, 2008].

16. Miller, G.L. Riemann’s hypothesis and test of primality. In the 7th Annual ACM Symposium on the Theory of Computing, 1975, pp. 234–239.

17. Rivest, R.L.; Shamir, A. & Adleman, L. A method for obtaining digital signatures and public key cryp­tosystems. Communications of ACM, 1978, 21(2), 158-64.

18. Stinson, D.R. Cryptography -Theory and practice. Ed 2nd, Chapman & Hall/CRC, 2002.

19. Wiener, M. Cryptanalysis of short RSA secret exponents. IEEE Trans. Inform. Theo., 1990, 36(3), 553-58.