| 12345678910111213141516171819202122232425262728 |
- \chapter{Wiener's Attack}
- \section{Bombelli's Algoritm}
- %% cuz python is pseudocode.
- \begin{minted}[fontsize=\small]{python}
- def intsqrt(a):
- i = 0
- while a > 0:
- g[i] = a % 100
- a /= 100
- i += 1
- x = 0
- r = 0
- for j in range(L-1, -1, -1):
- r = r*100 + g[j]
- y = 0
- for d in range(1, 10):
- yn = d*(20*x + d)
- if yn < r: y = yn
- else: break
- r -= y
- x = 10*x + d-1
- return (x, r)
- \end{minted}
- Has complexity $O(\log ^2 n)$.
|
