Timeline for Fast computation of multiplicative inverse modulo q
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 28, 2015 at 16:21 | history | protected | user9072 | ||
| Oct 10, 2010 at 6:43 | answer | added | Luke Gustafson | timeline score: 6 | |
| Oct 9, 2010 at 21:53 | answer | added | Barry | timeline score: 6 | |
| Oct 4, 2010 at 14:47 | vote | accept | Idoneal | ||
| Oct 4, 2010 at 11:16 | comment | added | j.p. | What do you mean with "fastest" algorithm? Are you interested in the asymptotic fastest algorithm (i.e., for the bit length of $q$ going to infinity)? Or are you interested in concretely implementing an inversion for numbers not too large (like a few thousand bits)? | |
| Oct 4, 2010 at 10:35 | comment | added | Idoneal | Ahan! very good. | |
| Oct 4, 2010 at 10:13 | comment | added | AVS | @Idoneal: The fast Euclidean algorithm takes time that is quasi-linear in the input size $n=\log q$ (whereas the standard Euclidean algorithm has complexity that is quadratic in $n$). Since linear time is required just to read the input, up to polylogarithmic factors, the fast Euclidean algorithm is optimal. | |
| Oct 4, 2010 at 10:07 | answer | added | AVS | timeline score: 30 | |
| Oct 4, 2010 at 9:54 | comment | added | Idoneal | To Buzzard: I wanted to check if there is any smarter way to do it than Euclid. Is there any reason to think that nothing better is possible? | |
| Oct 4, 2010 at 9:41 | answer | added | Sebastian Petersen | timeline score: 1 | |
| Oct 4, 2010 at 9:08 | comment | added | Kevin Buzzard | You want faster than Euclid's algorithm?? | |
| Oct 4, 2010 at 9:05 | history | asked | Idoneal | CC BY-SA 2.5 |