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
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:
2. Set . For
3. Calculate and .
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 .