Lehmer's GCD algorithm: Difference between revisions

Revision as of 04:25, 17 January 2016

Revision as of 16:14, 22 February 2016

Line 10:

** Decrease ''m'' by one. Let ''x'' be the leading (most significant) digit in ''a'', ''x'' = ''a'' div ''β''^ ''m'' and ''y'' the leading digit in ''b'', ''y'' = ''b'' div ''β''^ ''m''.

** Initialize a 2 by 3 [[matrix (mathematics)|matrix]]

*::<math>\textstyle

\begin{bmatrix} A & B & x\\ C & D & y \end{bmatrix}

</math> to an extended [[identity matrix]] <math>\textstyle

\begin{bmatrix} 1 & 0 & x \\ 0 & 1 & y\end{bmatrix},

</math>

Line 21:

**::<math>\textstyle \begin{bmatrix} A & B & x \\ C & D & y \end{bmatrix}</math>

**: with the matrix product

**:: <math>\textstyle

\begin{bmatrix} 0 & 1 \\ 1 & -w \end{bmatrix}

\cdot

\begin{bmatrix} A & B & x \\ C & D & y \end{bmatrix}

= \begin{bmatrix} C & D &y \\ A - wC & B - wD & x-wy \end{bmatrix}

</math>

Line 35:

<references/>

* [[Kapil Hari Paranjape|Kapil Paranjape]], [http://www.imsc.res.in/~kapil/crypto/notes/node11.html Lehmer's Algorithm]

{{Number-theoretic algorithms}}