Cryptanalysis of RSA with Small Prime Combination - Information Security and Cryptology-ICISC 2010 - page 110

Hence the fraction x must be among the convergents of the continued fraction
expansion of e M . There are only O (log N ) many convergents, thus we can apply
the following process to each candidate for k and x until our algorithm succeeds.
We now show that the correct k and x yield the factorization of N .Letus
write (10) as

ex
k −

y
k .

M = z − (12)

Since the left is know to us, we can compute an approximation of z up to some
unknown error term

y
k , which can be bounded by

y
k |≤ 3 N θ− 4

4

| using (11).

√ ρN √ ρN

ex
k .Since p +[ ρq ]=2

Let S =2 + M − − z ,wehavethat S is

3 N θ− 4

4

an approximation of p +[ ρq ] with additive error at most using (12). Let

T = S 2 4 ρN . Now we show that T is well defined by proving S 2 − − 4 ρN ≥ 0.

y
k ,wewrite S = p + ρq + with

y
k | 3 N θ− 4 +1.

4

Since S = p +[ ρq ] − | |≤| +1 ≤

We have that S 2 4 ρN =( p + ρq + ) 2 p ) 2 +2 ( p + ρq )+ 2 .Since − − 4 ρN =( ρq −

(2 + √ 2) √ N ,wehavethat2 ( p + ρq ) (2 + √ 2) √ N< 2( 3 N θ− 4 +1) p + ρq ≤ ≤ ·

11 N θ + 4 ≤ 11 N 4 . This implies

N 2 θ , which holds by our lower bound N θ ≥

S 2 0.

We now show that T is an approximation of

− 4 ρN ≥

| ρq − p | with an additive error

2 √ N

that can be bounded by N 4 .Since

y
k |≤

4

3 N θ− 4

1 1

4 ( p + ρq ), we have

| < ≤

that S = p +[ ρq ]+ k ≤

5
4 ( p + ρq ). Then we have

= S 2 T −| ρq − p | − 4 ρN −| ρq − p |

( S − ( p + ρq ))( S +( p + ρq ))

S 2

=

− 4 ρN + | ρq − p |

9(2+ √ 2)
4

√ N

4

3 N θ− 4

·

12 N 4 .

≤ ≤

N θ

We suppose that ρq > p .Thustheterm 2 ( S

− T ) is an approximation of p with

error at most

p

1
2 ( S

1
2 (

− T ) − = | S − p − ρq − T − p + ρq | )

1
2 (

≤ | S − p − ρq | + | T − ρq + p | )

2

3 N θ− 4 + 12 2 N 4 ≤

7 N 4 .

≤

T ). Then one of the seven values p +2 kN 4 , k =

1

Let p = 1 , 0 , 1 , 2 , 3

is an approximation of p up to an error of at most N 4 in absolute value. We
apply Coppersmith's algorithm (Theorem 1) to all these values. The correct term
will then lead to the factorization of N .
If ρq < p , then the term

2 ( S

− − 3 , − 2 , −

1

2 ( S + T ) is an approximation of p ,andthefac-
torization of N can also be recovered. This completes the proof of Theorem
5.