Timeline for Efficient algorithm for $x^n-x \bmod P(x)$ over $GF(2^{12})$
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Sep 9 at 17:53 | history | suggested | CommunityBot | CC BY-SA 4.0 |
horizontal spacing is better with \bmod
|
| Sep 9 at 14:08 | review | Suggested edits | |||
| S Sep 9 at 17:53 | |||||
| Feb 17, 2018 at 2:20 | vote | accept | jecado | ||
| Feb 14, 2018 at 1:43 | answer | added | jecado | timeline score: 2 | |
| Feb 14, 2018 at 1:29 | comment | added | jecado | Ah, I see now. It hadn't occurred to me to leave the "$-x$" term for after the exponentiation the others were referring to. It works perfectly now; thank you, everyone! | |
| Feb 14, 2018 at 0:07 | comment | added | Achim Krause | You can compute $x^{2^n}$ mod $f$ by starting with $x$, and then repeatedly squaring and reducing modulo $f$ in each step. Takes you $n$ steps, and the degree of none of the intermediate values gets larger than twice the degree of $f$. | |
| Feb 13, 2018 at 23:10 | comment | added | jecado | I understand reducing by your modulus at each step in the algorithm - but my problem is that my starting point is so high, $g(x)=x^{(2^{12i})}-x$. I'm not sure which intermediate values @WatsonLadd is referring to. | |
| Feb 13, 2018 at 21:19 | comment | added | Taneli Huuskonen | Wikipedia explains it for integer modular arithmetic: en.wikipedia.org/wiki/… | |
| Feb 13, 2018 at 21:07 | comment | added | jecado | @WatsonLadd Thank you - could you elaborate? | |
| Feb 13, 2018 at 20:47 | comment | added | Watson Ladd | There is a standard trick where you reduce the intermediate values in raising x to the q^i and so avoid ever having polynomials of higher degree than that of f. | |
| Feb 13, 2018 at 20:10 | review | First posts | |||
| Feb 13, 2018 at 20:59 | |||||
| Feb 13, 2018 at 20:08 | history | asked | jecado | CC BY-SA 3.0 |