Timeline for Computation of inverses modulo p followup
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Oct 19, 2010 at 12:35 | vote | accept | Barry | ||
| Oct 12, 2010 at 21:17 | comment | added | Dror Speiser | @Carnahan: That's probably false for number less than 10000 bits. | |
| Oct 12, 2010 at 18:45 | comment | added | Barry | Ah, thanks AVS! I wasn't expecting that performing the algorithm exactly as I wrote it would give a speed-up, but I was thinking that one of the other speed-ups might improve the algorithm I wrote to be comparable to others. One knows that the first remainder less than p will occur almost exactly half-way through the Euclidean algorithm with $p^2$ and $ap+1$, so jumping to the middle step will put you very close. | |
| Oct 12, 2010 at 18:45 | comment | added | AVS | The algorithm sketched in my comment above was only meant to show that your approach could be implemented in quasi-linear time. But this comes at the cost of making the algorithm much more complicated (which may be a pedagogical flaw or feature, depending on one's point of view), and it will still be slower than just computing the extended gcd. | |
| Oct 12, 2010 at 18:39 | comment | added | AVS | I didn't mention this in my answer to the linked question, but the half-gcd algorithm can be used to "jump" directly to any particular step of the extended Euclidean computation (not necessarily the last one) using a logarithmic number of recursive calls. One could perform a binary search to find the greatest remainder less than p using half-gcds, yielding a quasi-linear running time that is slower than the fast Euclidean algorithm by only a log factor, and even this might be avoided (at least on average) by jumping to the middle step and searching linearly from there. | |
| Oct 12, 2010 at 18:19 | answer | added | Sidney Raffer | timeline score: 3 | |
| Oct 12, 2010 at 17:47 | answer | added | Will Jagy | timeline score: 1 | |
| Oct 12, 2010 at 16:23 | comment | added | S. Carnahan♦ | If you examine AVS's answer to the question you linked, you will see that your algorithm is substantially slower than Fast Euclidean. | |
| Oct 12, 2010 at 16:10 | comment | added | Dror Speiser | Quadratic complexity. Compared to standard quadratic algorithm: half the iterations, on twice-the-size numbers. Since the operations are more than linear in size, I would guess that the constant is larger than the constant of the standard algorithm. | |
| Oct 12, 2010 at 14:46 | history | asked | Barry | CC BY-SA 2.5 |