Decode the contents of this sketch. Returns either a list of elements or None if undecodable.
(self, max_count=None)
| 423 | self.odd_syndromes[i] ^= other.odd_syndromes[i] |
| 424 | |
| 425 | def decode(self, max_count=None): |
| 426 | """Decode the contents of this sketch. |
| 427 | |
| 428 | Returns either a list of elements or None if undecodable. |
| 429 | """ |
| 430 | # We know the odd syndromes s1=x+y+..., s3=x^3+y^3+..., s5=..., and reconstruct the even |
| 431 | # syndromes from this: |
| 432 | # * s2 = x^2+y^2+.... = (x+y+...)^2 = s1^2 |
| 433 | # * s4 = x^4+y^4+.... = (x^2+y^2+...)^2 = s2^2 |
| 434 | # * s6 = x^6+y^6+.... = (x^3+y^3+...)^2 = s3^2 |
| 435 | all_syndromes = [0 for _ in range(2 * len(self.odd_syndromes))] |
| 436 | for i in range(len(self.odd_syndromes)): |
| 437 | all_syndromes[i * 2] = self.odd_syndromes[i] |
| 438 | all_syndromes[i * 2 + 1] = self.gf.sqr(all_syndromes[i]) |
| 439 | # Given the syndromes, find the polynomial that generates them. |
| 440 | poly = berlekamp_massey(all_syndromes, self.gf) |
| 441 | # Deal with failure and trivial cases. |
| 442 | if len(poly) == 0: |
| 443 | return None |
| 444 | if len(poly) == 1: |
| 445 | return [] |
| 446 | if max_count is not None and len(poly) > 1 + max_count: |
| 447 | return None |
| 448 | # If the polynomial can be factored into (1-m1*x)*(1-m2*x)*...*(1-mn*x), then {m1,m2,...,mn} |
| 449 | # is our set. As each factor (1-m*x) has 1/m as root, we're really just looking for the |
| 450 | # inverses of the roots. We find these by reversing the order of the coefficients, and |
| 451 | # finding the roots. |
| 452 | roots = poly_find_roots(list(reversed(poly)), self.gf) |
| 453 | if len(roots) == 0: |
| 454 | return None |
| 455 | return roots |
| 456 | |
| 457 | class TestMinisketch(unittest.TestCase): |
| 458 | """Test class for Minisketch.""" |
no test coverage detected