Timeline for Specializing non-trivial primality tests
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 9, 2017 at 5:58 | vote | accept | Turbo | ||
| Nov 4, 2017 at 22:34 | history | edited | Turbo | CC BY-SA 3.0 |
deleted 62 characters in body
|
| Nov 4, 2017 at 22:24 | comment | added | Turbo | @JohannesHahn 1. I would not know how to compute binomial coefficients mod $q$ in poly time. 2. I do not know why this is useful at all. | |
| Nov 4, 2017 at 22:21 | history | edited | Turbo | CC BY-SA 3.0 |
added 53 characters in body
|
| Nov 4, 2017 at 22:21 | comment | added | Johannes Hahn | @Turbo The very first step of the euclidean algorithm is replacing c with c modulo q. So you can just compute the binomial coefficient modulo q in the first place to avoid that particular problem. | |
| Nov 4, 2017 at 22:17 | answer | added | Jan-Christoph Schlage-Puchta | timeline score: 5 | |
| Nov 4, 2017 at 21:56 | comment | added | Turbo | $c=\binom{b}{a-1}$ could be large (say $a=5\times 10^{100}, b=6\times 10^{100}$ (also I do not get why use $gcd(q,c)$))? | |
| Nov 4, 2017 at 21:53 | comment | added | Gerhard Paseman | If a+2 is less than b+2 is less than a+a, start with gcd(q,c) where c = b choose a-1. Otherwise split the interval up. Gerhard "Best Way Known To Me" Paseman, 2017.11.04. | |
| Nov 4, 2017 at 21:11 | history | asked | Turbo | CC BY-SA 3.0 |