Timeline for Computing the decimation ratio between two m-sequences
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 18, 2017 at 14:17 | vote | accept | Jason S | ||
| Nov 18, 2017 at 14:17 | comment | added | Jason S | After some work to understand and implement, Cantor-Zassenhaus worked nicely for me. This article helped (ignore the title, it discusses $GF(2)$ also). Thanks for the suggestion! | |
| Nov 18, 2017 at 2:45 | comment | added | Jason S | oh wait, no, it would be awful because all the factors here are linear, so I need an equal-degree factorization method. | |
| Nov 18, 2017 at 2:43 | comment | added | Jason S | Ok, thanks. Would distinct-degree factorization work well here? I understand that one for the most part; understanding Cantor-Zassenhaus has eluded me. | |
| Nov 18, 2017 at 2:38 | comment | added | Max Alekseyev | @JasonS: See pari.math.u-bordeaux.fr/dochtml/html-stable/… and en.wikipedia.org/wiki/… | |
| Nov 17, 2017 at 23:57 | comment | added | Jason S | Ugh, how do you factor a polynomial in $F_1[y]$? I like McEliece's algorithm for factoring in $GF(2)[x]$ because it's a product of two gcd's, but if I were to use it in $F_1[y]$ I would have to evaluate gcd for each element in $F_1$ which is not practical with large degree polynomials. | |
| Nov 17, 2017 at 23:51 | comment | added | Jason S |
I tried running PARI/GP in my browser and following your example with some more print statements to see what is going on. How does it know whether to factor with respect to $x$ or to $y$?
|
|
| Nov 16, 2017 at 22:46 | comment | added | Max Alekseyev | $F_1$ is simply a realization of $\mathrm{GF}(2^N)$ in polynomials modulo $p_1$ over $\mathrm{GF}(2)$. So $F_1[y]$ is the ring of polynomials with coefficients from the finite field $\mathrm{GF}(2^N)$. | |
| Nov 16, 2017 at 22:25 | comment | added | Jason S | I guess the thing that confuses me is that $F_1[y]$ is a polynomial ring where the each element is a polynomial with coefficients that are elements of $F_1 = GF(2)[x]/p_1(x)$ which are themselves represented by polynomials. | |
| Nov 16, 2017 at 22:22 | comment | added | Jason S | OH -- okay, oops. Haha. | |
| Nov 16, 2017 at 22:21 | comment | added | Jason S | Everything else looks promising -- I have to check my mental model of all this to make sure I understand all the pieces but I'm familiar with polynomial factoring techniques so I think I can translate this to the Python code I work with. Does it work with any value of $j$, or just the ones that are relatively prime to $2^N-1$ where $p_2(x)$ is a primitive polynomial? | |
| Nov 16, 2017 at 22:20 | comment | added | Max Alekseyev | @JasonS: You defined $F_1$ in your question. | |
| Nov 16, 2017 at 22:16 | comment | added | Jason S | dumb question, what's $F_1$? is that the infinite set of integers? I'm familiar with the notation $F_{q^n}$ for finite fields. | |
| Nov 16, 2017 at 22:05 | history | edited | Max Alekseyev | CC BY-SA 3.0 |
added 194 characters in body
|
| Nov 16, 2017 at 21:55 | history | edited | Max Alekseyev | CC BY-SA 3.0 |
deleted 6 characters in body; deleted 1 character in body
|
| Nov 16, 2017 at 21:50 | history | answered | Max Alekseyev | CC BY-SA 3.0 |