Okay, so all I did is I just divided by d times phi(N)

and I moved the k times phi(N) term to the left-hand side.

Now, just for the heck of it I'm going to add absolute values here.

These will become useful in just a minute, but of course they don't change this equality at all.

Now, phi(N) of course is almost N; phi(N) is very, very close to N, as we said earlier.

And all I'm going to need then for this fraction is just to say that

it's less than 1 over square root of N. It's actually much, much smaller

than 1 over square root of N, it's actually on the order of 1 over N or even more than that,

but for our purposes all we need is that this fraction is less than 1 over square root of N.

Now let's stare at this fraction for just a minute.

You realize that this fraction on the left here is a fraction that we don't actually know.

We know e, but we don't know phi(N), and as a result we don't know e over phi(N).

But we have a good approximation to e over phi(N). Namely we know that phi(N)

is very close to N. Therefore e over phi(N) is very close to e over N.

So we have a good approximation to this left-hand side fraction, namely e over N.

What we really want is the right-hand side fraction,

because once we get the right-hand side fraction,

basically that's going to involve d, and then we'll be able to recover d. Okay, so let's see

if we replace e over phi(N) by e over N, let's see what kind of error we're going to get.

So to analyze that, what we'll do is first of all remind ourselves

that phi(N) is basically N - p - q + 1,

which means that N minus phi(N) is going to be less than p + q.

Actually I should, to be precise I should really write p + q + 1, but you know,

who cares about this 1, it's not, it doesn't really affect anything.

So I'm just going to ignore it for simplicity.

Okay, so N - phi(N) is less than p + q. Both p and q are roughly half the length of N,

so you know, they're both kind of on the order of square root of N,

so basically p + q we'll say is less than 3 times square root of N.

Okay, so we're going to use this inequality in just a minute.

But now we're going to start using the fact that we know something about d,

namely that d is small. So if we look at this inequality here,

d is less than the fourth root of N divided by 3.

It's actually fairly easy to see that if I square both sides

and I just manipulate things a little bit, it's [not] difficult to see that

this directly implies the following relation,

basically 1 over 2 d squared minus 1 over square root of N is greater than 3 over square root of N.

As I said, this basically follows by squaring both sides, then taking the

inverse of both sides, and then I guess multiplying one side by a half.

Okay, so you can easily derive this relation, and we'll need this relation in just a minute.

So now let's see, what we'd like to do is bound

the difference of e over N and k over d. Well what do we know?

By the triangular inequality, we know that this is equal to

the distance between e over N and e over phi(N) plus

the distance from e over phi(N) to k over d.

This is just what's called a triangular inequality; this is just a property of absolute values.

Now this absolute value here, we already know how to bound.

If you think about it it's basically the bound that we've already derived.

So we know that this absolute value here is basically less than 1 over square root of N.

Now what do we know about this absolute value here? What is e over N minus e over phi(N)?

Well let's do common denominators and see what we get.

So the common denominator is going to be N times phi(N),

and the numerator in this case is going to be e times phi(N) minus N.

Which we know from this expression here is less than 3 times square root of N.

So really what this numerator is going to be is e times 3 square root of N.

The numerator is going to be less than e times 3 square root of N.

So now I know that e is less than phi(N), so I know that e over phi(N) is less than 1.

In other words, if I erase e and I erase phi(N) I've only made the fraction larger.

Okay, so this initial absolute value is now going to be

smaller than 3 square root of N over N, which is simply,

3 square root of N over N is simply 3 over square root of N.

Okay, but what do we know about 3 over square root of N?

We know that it's less than 1 over 2 d squared minus 1 over square root of N.

Okay, so that's the end of our derivation.

So now we know that the first absolute value is less than 1 over 2 d squared minus square root of N.

The second absolute value is less than 1 over square root of N.

And therefore their sum is less than 1 over 2 d squared.

And this is the expression that I want you to stare at.

So here, let me circle it a little bit. So let me circle this part and this part.