The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
2answers
73 views

Understanding Intel's algorithm for reducing a polynomial modulo an irreducible polynomial

I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of ...
1
vote
1answer
69 views

NFA for right left multiplication

Given the following multiplication table how could one construct an NFA such that it accepts all strings that have a certain product (say a) ? The string "abcb" would be evaluated as (a(b(cb))) = a ...
1
vote
2answers
83 views

Does the performance of matrix multiplication depend on the storage of the array?

Two matrices can be stored in either row major or column major order in contiguous memory. Does the time complexity of computing their multiplication vary depending on the storage scheme? That is, I ...
3
votes
1answer
446 views

Shift-and-or multiplication operation

Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold): Let $r = p \oplus q$ be an operation similar to multiplication, but ...
3
votes
2answers
127 views

Carry-free multiplication operation

In long-multiplication, you shift and add, once for each $1$ bit in the lower number. Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via ...