Last time we saw how to solve with a complexity of . We now want to see if we can solve the same question with complexity.

Consider solving where is a prime. We can still use Gaussian Elimination and, without loss of generality, assume that .

Let’s work through an example:

We then solve for to get

In general, we will need to be familiar with the multiplicative inverse which is

s.t.

For example,

So, coefficients of remain in and complexity .

Can we use this to solve faster?

It turns out, YES, we can!

1. First, solve for a “large enough” .

2. Convert to rational with “not too large” numerator and denominator.

We want to be large enough such that the resulting the unique solution to . How large, exactly, is that?

We know that has entries with bits. So,

This implies that every numerator/denominator of coordinates of is an integer .

Assume and does not divide .

Now, our high level approach to solving will be to take the following steps:

1. Solve in .

2. Set and recover from such that .

First, we will try to find where is a vector and is an integer with . Why?

, so will suffice.

We now present the algorithm to solve the first step:

1. Find

2. Set . For

3. Calculate and .

So,

Next time we will look at how to approximate a given real/rational by a rational with small integers using the Euclidean algorithm for greatest common divisor. We will use this to complete the solution to .