Timeline for Modular inverse computation - avoiding Euclidean algorithm
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 7, 2023 at 18:38 | comment | added | Pace Nielsen | By the way, you could contact the author, to get clarification on the situation. | |
| Apr 7, 2023 at 18:36 | comment | added | Pace Nielsen | @Turbo Oh, so the incorrectness you mentioned, as far as you know, is limited to an unpublished paper. Then I stand by my comment, that using google scholar to look through the literature related to the published paper is a good idea. (It would still be a good idea if the published paper were incorrect, as the literature around it would hopefully reveal that fact.) | |
| Apr 7, 2023 at 18:29 | comment | added | Turbo | @PaceNielsen ".. the work $or$ some related work..". I think wiki had a writing once that quoted the author's work which claimed GCD is in NC. This is discussed in mathoverflow.net/questions/122616/is-integer-gcd-in-nc. | |
| Apr 7, 2023 at 18:24 | comment | added | Pace Nielsen | @Turbo If it is incorrect, perhaps those in the know should get the paper retracted. | |
| Apr 7, 2023 at 17:12 | comment | added | Turbo | @PaceNielsen I think there was earlier discussion somewhere on MO that the work or some related work by the same author is incorrect. Please see mathoverflow.net/questions/122616/is-integer-gcd-in-nc. There is some discussion here too but not totally relevant mathoverflow.net/questions/338053/…. | |
| Apr 7, 2023 at 16:35 | comment | added | Pace Nielsen | On google scholar, I found searching through the literature related to the paper "A parallel extended GCD algorithm" very intriguing. | |
| Apr 7, 2023 at 14:16 | comment | added | Timothy Chow | Complexity theory usually doesn't provide nontrivial "barriers" to fast algorithms; the well-known "barriers" are barriers to proving lower bounds. As you know, modular inverse is not known to be in $\mathsf{NC}$, but there's really no "barrier" standing in the way of a better algorithm for it, other than our lack of imagination. | |
| Apr 6, 2023 at 0:34 | comment | added | Gerry Myerson | Pierre's Last Theorem, The Bernhard Hypothesis, Max's Lemma, Joseph numbers, .... | |
| Apr 5, 2023 at 20:14 | comment | added | KConrad | @EmilJeřábek that's amazing. | |
| Apr 5, 2023 at 20:05 | history | edited | Turbo | CC BY-SA 4.0 |
added 323 characters in body
|
| Apr 5, 2023 at 20:01 | comment | added | Turbo | @KConrad well praising a family line for an individual's work!! | |
| Apr 5, 2023 at 20:01 | comment | added | Emil Jeřábek | @KConrad It does not stop there: Nick Pippenger returned the favour by naming en.wikipedia.org/wiki/SC_(complexity) . | |
| Apr 5, 2023 at 19:46 | comment | added | KConrad | @EmilJeřábek wow, "Nick's Class" is such an unexpected answer, esp. since Nick is a first name. Imagine we spoke of "Isaac's Method" instead of "Newton's Method". | |
| Apr 5, 2023 at 18:43 | comment | added | Emil Jeřábek | @KConrad en.wikipedia.org/wiki/NC_(complexity) | |
| Apr 5, 2023 at 18:36 | comment | added | KConrad | I am unfamiliar with the phrase "NC reduce". Please edit that part of the question to avoid the abbreviation by spelling out what is meant there. | |
| Apr 5, 2023 at 18:18 | history | edited | LSpice | CC BY-SA 4.0 |
More consistent: non-math out of math mode
|
| Apr 5, 2023 at 17:48 | comment | added | Robert Israel | But @Aeryk's suggestion could be useful in case $q$ is known to be prime. | |
| Apr 5, 2023 at 17:33 | comment | added | Aeryk | You could compute $a^{\phi(q)-1}$ via square-and-multiply. But this is probably not what you're looking for as computation of $\phi(q)$ could be nontrivial. | |
| Apr 5, 2023 at 16:22 | history | asked | Turbo | CC BY-SA 4.0 |