Use the simple continued fraction of $\sqrt{27323}$ to factor $27323$.
So far I have:
$\sqrt{27323} = 1 + (\sqrt{27323} - 1)$
which gives...
$= 1 + \frac{1}{(\frac{1}{164.2967029})}$
- I'm getting a bit lost after this point, my professor told me that if done properly I only need to consider the first four convergents of $\sqrt{27323}$. Any help is greatly appreciated.
I'll have a stab at this.
First, here's a link on how to find the simple continued fraction of a number $x$: http://mathworld.wolfram.com/ContinuedFraction.html
And here's a link (see pages 13 - 15) on how to factorize a number $n$, using the simple continued fraction of $x = \sqrt n$: http://wstein.org/edu/2010/414/projects/johnson.pdf
From the first link we find that the simple continued fraction of $x= \sqrt n = \sqrt {27323}$ for the first 4 terms is:
$$x = [a_0, a_1, a_2, a_3]$$
$$x = [165, 3, 2, 1]$$
See equations 5 to 10 in the link. From equations 24 to 28 we can determine the first 4 convergents, which are: $$\frac{p_0}{q_0} = \frac{165}{1}$$ $$\frac{p_1}{q_1} = \frac{496}{3}$$ $$\frac{p_2}{q_2} = \frac{1157}{7}$$ $$\frac{p_3}{q_3} = \frac{1653}{10}$$
That was the easy part. Now for the tough part (factorization). From the second link, we let $\frac{A_k}{B_k}$ be the $k$'th convergent. We then define the number $Q_k$ as $Q_k = A_{k-1}^2 - kB_{k-1}^2$. This leads to the equation $(-1)^kQ_k \equiv A_{k-1}^2 \pmod n$. We can now construct the set $Q = \{Q_1, Q_2, Q_3, Q_4 \}$ of solutions for each $k$ and then find the factors of each $Q_k$ as shown below:
As described in the second link, we now need to look through the set $Q$ and find a subset whose prime factors will all be squares when multiplied together. The only such subset in this case is $\{Q_2, Q_4 \}$ where $Q_2*Q_4 = 109*109 = 109^2$. Set $X = 109$. Now multiply the corresponding $A_{k-1}$ for each $Q_k$ to get $A_1*A_3 = 496*1653 = 819888$, which$\pmod n =198$. Set $Y = 198$. Now find the $gcd(X - Y, n)$ which is 89.
And we are done!
We have found a factor of 27323 and it's name is $$\mathbf 89$$
And they say this is one of the fastest factorization algorithms around. :-)