Timeline for Fast computation of multiplicative inverse modulo q
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 5, 2010 at 6:18 | comment | added | Idoneal | I see. I haven't understood the half-GCD thing yet. It seems some 2-adic computation is going on. | |
| Oct 4, 2010 at 16:28 | history | edited | AVS | CC BY-SA 2.5 |
Added a link
|
| Oct 4, 2010 at 15:21 | comment | added | AVS | @idoneal: Actually, while Lehmer's idea does improve the constant and logarithmic factors in the standard Euclidean algorithm, it still runs in quadratic time. I believe the first subquadratic algorithms are due to Knuth (1970) and Schonhage (1971), who introduced the recursive divide-and-conquer approach that led to the half-gcd algorithm noted above. The Moller reference (to which I have added a link) gives a good summary of the historical development and the current state of the art. | |
| Oct 4, 2010 at 15:12 | history | edited | AVS | CC BY-SA 2.5 |
added hyperlink
|
| Oct 4, 2010 at 14:47 | vote | accept | Idoneal | ||
| Oct 4, 2010 at 14:44 | comment | added | Idoneal | Thanks. The way I understand it, the main idea (due to Lehmer) is carrying out the usual Euclidean algorithm for computing GCD with a little modification coming from the following observation: For computing the partial quotients, we can forget the tails and look at the leading digits. So for computing the GCD of 1234 and 102, first we need to find q and r such that 1234 =102.q+r with 0<r<102. Now, to find q, we might as well divide 10^3 by10^2 which takes less time. | |
| Oct 4, 2010 at 14:01 | history | edited | AVS | CC BY-SA 2.5 |
Added a brief overview of the algorithm and some references.
|
| Oct 4, 2010 at 11:23 | comment | added | j.p. | @Idoneal: Take a look at perso.ens-lyon.fr/damien.stehle/downloads/recbinary.pdf or perso.ens-lyon.fr/damien.stehle/downloads/antsgcd.pdf | |
| Oct 4, 2010 at 10:56 | comment | added | Idoneal | Well, I tried reading the reference in Google books but it seems to be somewhat complicated and moreover it is for polynomials. Is it possible explain the main idea behind the fast Euclidean algorithm in a few words or by some simple example? | |
| Oct 4, 2010 at 10:20 | history | edited | AVS | CC BY-SA 2.5 |
added 8 characters in body
|
| Oct 4, 2010 at 10:07 | history | answered | AVS | CC BY-SA 2.5 |