# Add Python implementation of Minisketch, part 2 (math and cryptography)

https://github.com/sipa/minisketch/pull/26

Host: sipa -

## Notes

This week, we’ll continue our review of the Python implementation of Minisketch.

See the notes from our previous review club on Minisketch.

## Questions

- (previously question 6) To actually find the roots, the
Berlekamp Trace Algorithm is used. It uses the
trace function
`t(x) = x + x^2 + x^4 + ... + x^(fieldsize/2)`

which maps every element of a field of size`2^n`

to`0`

or`1`

. In our 8-bit field that means`t(x) = x + x^2 + x^4 + x^8 + x^16 + x^32 + x^64 + x^128`

. This means that for any non-zero field element`p`

,`tr(p*x)`

also has this property, and every choice of`p`

will map a different subset of field elements to 0 (and the others to 1). How is this property used to recursively split the polynomial into smaller and smaller ones?

## Meeting Log

1 | 18:00 | <jnewbery> #startmeeting |

2 | 18:00 | <jnewbery> hi folks! |

3 | 18:00 | <larryruane_> hi |

4 | 18:00 | <pinheadmz> hi |

5 | 18:00 | <felixweis> hi |

6 | 18:00 | <andozw> yoooo |

7 | 18:00 | <emzy> hi |

8 | 18:00 | <kouloumos> hi! |

9 | 18:00 | <jnewbery> feel free to say hi to let everyone know you're here |

10 | 18:00 | <jnewbery> anyone here for the first time? |

11 | 18:00 | <tkc> hi-new here-first time |

12 | 18:00 | <eoin> hi, my third review |

13 | 18:01 | <jnewbery> tkc: welcome! |

14 | 18:01 | <kouloumos> first time of 2021 ;) |

15 | 18:01 | <jonatack> hi |

16 | 18:01 | <jnewbery> Today we'll be continuing the discussion about Minisketch from two weeks ago |

17 | 18:01 | <tkc> thanks-initial steps in learn to program the core-long road ahead. :) |

18 | 18:01 | <jnewbery> Notes, questions and logs from that meeting are here: https://bitcoincore.reviews/minisketch-26. We got up to question 5 last time I think. |

19 | 18:01 | <jnewbery> ok, over to sipa! |

20 | 18:02 | ℹ ma is now known as Guest8267 |

21 | 18:02 | <sipa> sorry, laptop troubles! |

22 | 18:02 | <sipa> be right there |

23 | 18:02 | <eoin> hi, my third review |

24 | 18:02 | <jnewbery> anyone know any good minisketch puns while sipa sorts out his laptop? |

25 | 18:03 | <jonatack> since i warned about flakey internet, it will probably work flawlessly this time |

26 | 18:03 | <sipa> ok! |

27 | 18:03 | <pinheadmz> I know this many miniskettch puns: x^6 + x^5 + x^4 + x^3 + x^2 + x |

28 | 18:04 | <sipa> i heard there are an infinite number of papers to write about real analysis, but today we don't need to worry about that because we're working in a finite field |

29 | 18:04 | ⚡ pinheadmz *cough* |

30 | 18:04 | <sipa> so |

31 | 18:04 | <glozow> when u trying to solve polynomial it can get kinda berlekamp messy |

32 | 18:04 | <sipa> everybody awake? |

33 | 18:05 | <emzy> *g* |

34 | 18:05 | <sipa> let's go over where we were |

35 | 18:05 | <felixweis> minisketch helps every bitcoiner to get a GF(2)! |

36 | 18:06 | <sipa> we're working in a finite field, which is like numbers, but addition and subtraction multiplication and division are all defined in a weird way |

37 | 18:06 | <glozow> i was in the minisketchy part of town and someone made me do a set reconciliation with the bills in my wallet |

38 | 18:06 | <sipa> a+b and a-b are the same thing |

39 | 18:07 | <Guest8267> XOR |

40 | 18:07 | <pinheadmz> lets all just pay attention to sipa. if you miss anything, its really easy and fast to get whatever you missed from someone else |

41 | 18:07 | <sipa> and then we define "sketches" of a set {a,b,c} as just the list {a+b+c, a^3+b^3+c^3, a^5+b^5+c^5, ...} |

42 | 18:07 | <sipa> up to its capacity |

43 | 18:07 | <glozow> welcome to the frobenius hospital, we only treat odd syndromes because the even ones can be cured by squaring the odd ones |

44 | 18:07 | <jnewbery> thanks glozow |

45 | 18:07 | <glozow> ok sorree i'm done now |

46 | 18:08 | <jonatack> 🤣 |

47 | 18:08 | <sipa> today we'll let Berlekamp be our guide in tracing a euclidean ring through the galois fields, in the hope of finding some hidden roots... |

48 | 18:09 | <sipa> and in general set reconciliation works by sending such a sketch, letting the other side "add" (or subtract, same thing) from it their own sketch |

49 | 18:10 | <sipa> which results in a sketch of the symmetric difference of the two parties' sets |

50 | 18:11 | <sipa> as you can see that say Alice has {a,b} and Carol has {b,c}, the sketches are {a+b,a^3+b^3,...} and {b+c,b^3+c^3,...} and pairwise adding those gives you {a+c,a^3+c^3,...}, the sketch of {a,c} |

51 | 18:11 | <sipa> makes sense? |

52 | 18:12 | <jnewbery> 👍 |

53 | 18:12 | <pinheadmz> very cool yes |

54 | 18:12 | <sipa> now, the hard part is... given this {a+c,a^3+c^3,...} sketch, find {a,c} again |

55 | 18:13 | <larryruane_> so (a+b) + (b+c) = a+2b+c = a+c ? |

56 | 18:13 | <pinheadmz> larryruane_ yes bc + and - cancel out like XOR! |

57 | 18:13 | <sipa> we've already used the Berlekamp-Massey algorithm to turn this sequence into a polynomial that generates the sequence, which in our case would be (1+ax)*(1+cx) |

58 | 18:13 | <pinheadmz> er I shoudl say +b and +b cancel out |

59 | 18:13 | <sipa> larryruane_: yes, characteristic 2 field, so a+a = 0 |

60 | 18:14 | <sipa> but of course we don't get the polynomial in that form, we get just the coefficients of it: [1, a+c, ac] |

61 | 18:15 | <sipa> and if we had more terms, it'd be even more complex |

62 | 18:16 | <sipa> for 3 terms it'd be [1, a+b+c, ab+bc+ac, abc] etc |

63 | 18:16 | <pinheadmz> Berlekamp-Massey turns this: {a+c,a^3+c^3,...} into this: (1+ax)*(1+cx) ? |

64 | 18:16 | <sipa> indeed |

65 | 18:16 | <sipa> and it does so regardless of how big your sketch was |

66 | 18:17 | <sipa> that polynomial defines the pattern underlying the infinite sequence of {a+c,a^3+c^3,a^5+c^5,a^7+c^7,...} |

67 | 18:18 | <sipa> so we work in the "sketch" form because there it's easy to use the cancelling-out property |

68 | 18:18 | <sipa> and that's what we send |

69 | 18:18 | <sipa> but we then use BM to discover the pattern behind it, and that pattern (the polynomial) helps us find what the actual input terms are |

70 | 18:19 | <pinheadmz> (1+ax)*(1+cx) = 1 + cx + ax + ac(x^2) ? |

71 | 18:19 | <sipa> there is a bit deeper explanation here: https://github.com/sipa/minisketch/blob/master/doc/math.md |

72 | 18:19 | <sipa> yes, 1 + (a+c)x + (ac)x^2, so BM finds the coefficients [1,a+c,ac] |

73 | 18:19 | <sipa> what are our next steps? |

74 | 18:19 | <pinheadmz> oh right (a+c)x |

75 | 18:20 | <sipa> assuming we actually want to find a and c |

76 | 18:20 | <glozow> factor it |

77 | 18:20 | <sipa> yeah, of course |

78 | 18:20 | <lightlike> check that it has n roots and can be completely factored |

79 | 18:21 | <sipa> indeed, that too |

80 | 18:21 | <sipa> we could use a fully-fledged factoring algorithm like cantor-zassenhaus, but we don't actually care about factoring it |

81 | 18:21 | <sipa> we want to find its roots |

82 | 18:21 | <sipa> which is the same as saying: factoring into 1st degree factors |

83 | 18:22 | <sipa> but if the polynomial somehow can't be factored fully into 1st degree factors, or those factors aren't all unique, we don't really care at all |

84 | 18:22 | <felixweis> because it can't be fully decoded |

85 | 18:22 | <felixweis> all or nothing |

86 | 18:23 | <sipa> right, we know that if that polynomial is the result of BM on a sketch of sufficient size, it will be factorizable into distinct 1st degree factors |

87 | 18:23 | <sipa> and so we can actually use a significantly simpler algorithm that just finds the roots, and we can even use one that only works if all roots are distinct |

88 | 18:24 | <sipa> but we do need to check ahead of time that this is the case, as the algorithm we'll use would run into an infinite loop or otherwise behave incorrectly if it isn't |

89 | 18:24 | <sipa> how did we do that? |

90 | 18:24 | <sipa> we briefly discussed it last time |

91 | 18:24 | <lightlike> if we find that the polynomial isn't factorizable, can we deduce that the sketch size was too small? or could that have other causes as well? |

92 | 18:24 | <sdaftuar> sipa: under what circumstances would BM give you a polynomial with duplicate roots that live in the field? |

93 | 18:25 | <sipa> lightlike: yeah, it must mean that |

94 | 18:25 | <glozow> use `poly_frobeniusmod` - compute x^{2^b} mod poly, which should be exactly x if it has unique roots |

95 | 18:26 | <felixweis> I was able to generate a sketch(8,4) that decodes 5 numbers. whats the origin of this? |

96 | 18:26 | <sipa> sdaftuar: if the list (sketch) appears to have a polynomial with repeated roots as shortest LFSR that generates it |

97 | 18:27 | <sipa> i believe that e.g. [1,0,1,0,1,0,1,0,...] has (x^2 + 1) as LFSR |

98 | 18:27 | <sipa> which has double root 1 |

99 | 18:27 | <sdaftuar> thanks, will ponder |

100 | 18:27 | <sipa> given that we start from a set where every element can only occur once, that must mean our sketch was just too small |

101 | 18:28 | <sipa> glozow: indeed, why? |

102 | 18:29 | <pinheadmz> sipa guess: some element wrapped around the modulus? and repeated some lower element? |

103 | 18:29 | <glozow> in an order q galois field, x^q - x always has every field element as roots, so if the polynonmial does too, then x^q = x mod poly |

104 | 18:29 | <sipa> right, or in other words: we want to know if poly is a divisor of x^q - x |

105 | 18:30 | <sipa> and if that's the case, (x^q - x) mod poly = 0 |

106 | 18:30 | <sipa> and if poly has degree > 1, that's the same as x^q mod poly = x |

107 | 18:30 | <sipa> because (x^q - x) = x*(x+1)*(x+2)*(x+3)*...*(x+(q-1)) |

108 | 18:30 | <sipa> (i.e. it's the product of all possible 1st degree factors, and thus has every element of the field exactly once as root) |

109 | 18:31 | <sipa> ok, moving on! |

110 | 18:31 | <glozow> yeet |

111 | 18:31 | <sipa> actually finding the root |

112 | 18:31 | <sipa> s |

113 | 18:31 | <sipa> again: we're really trying to find 1st degree factors of our polynomial, but we *know* ahead of time that it factors completely, without any duplicates |

114 | 18:32 | <lightlike> do we do this check only as an optimization to save time, or because the root finding algorithm could run indefinitely? |

115 | 18:32 | <glozow> both? |

116 | 18:32 | <sipa> lightlike: done naively, it could run indefinitely |

117 | 18:32 | <sipa> ok |

118 | 18:32 | <sipa> what's the trace function? |

119 | 18:32 | <sipa> (because it's the Berlekamp Trace algorithm, there must be a trace, right?) |

120 | 18:34 | <sipa> tr(x) = x + x^2 + x^4 + x^8 + ... + x^(q/2) |

121 | 18:34 | <sipa> is the trace function for our field, w.r.t. GF(2) |

122 | 18:34 | <sipa> in general, a trace function is a function that maps elements of some bigger structure to a smaller one |

123 | 18:34 | <glozow> I'm not 100% clear on this. So the Trace function gives us a GF(2)-linear map from the polynomials to GF(2)? |

124 | 18:35 | <sipa> it maps every GF(2^b) element to a GF(2) element, in our case |

125 | 18:35 | <sipa> and more precisely, it maps exactly half of them to 0 and the other half to 1 |

126 | 18:35 | <glozow> right, it'd have to |

127 | 18:35 | <sipa> you can see that this is the case by computing what tr(x) * (1 + tr(x)) is |

128 | 18:37 | <sipa> this also means that for any field element a (not 0), tr(a*x) also has this property |

129 | 18:37 | <sipa> it maps half of the elements to 0, and the other half to 1... but which half that is depends on a |

130 | 18:38 | <sipa> so we start by picking a random a, and trying to separate the roots from poly(x) into the ones for which tr(a*x)=0 and the ones for which tr(a*x)=1 |

131 | 18:38 | <sipa> and then do that recursively with different a values, until everything is split into 1st degree factors |

132 | 18:39 | <sipa> what do you know about poly(x) mod tr(a*x) ? |

133 | 18:39 | <glozow> wait sorry, so the Trace function is defined on GF(2^b), how do we apply it to the polynomial itself? |

134 | 18:39 | <sipa> we'll get there |

135 | 18:40 | <sipa> tr(a*x) is a polynomial in x |

136 | 18:40 | <sipa> if you think about it symbolically |

137 | 18:40 | <sipa> it's a*x + (a^2)*x^2 + (a^4)*x^4 + ... |

138 | 18:41 | <sipa> right? |

139 | 18:41 | <glozow> right, mhm |

140 | 18:41 | <sipa> now: think about what a modulus means: |

141 | 18:41 | <sipa> if r(x) = poly(x) mod tr(x), that means that r(x) equals poly(x) + somefunction(x)*tr(x) |

142 | 18:42 | <sipa> in the same way that 19 mod 8 = 3 means that 3 = 19 + (some number)*8 |

143 | 18:42 | <sipa> (where some number here specifically is -2) |

144 | 18:42 | <sipa> for polynomial modulus it's the same, except it's now some unknown polynomial |

145 | 18:43 | <sipa> plz ask questions if things aren't clear :) |

146 | 18:43 | <glozow> is that polynomial = gcd(poly, trace)? |

147 | 18:43 | <sipa> no no, no gcd yet |

148 | 18:43 | <sipa> just a simple modulus |

149 | 18:43 | <sipa> this is the definition of a modulus |

150 | 18:44 | <glozow> okok ye |

151 | 18:44 | <sipa> or even the definition of division as you learned it in high school probably: when computing a/b, you find a-q*b=r |

152 | 18:44 | <sipa> quotient and residue |

153 | 18:45 | <sipa> the modulus operation is finding the residue and ignoring the quotient |

154 | 18:45 | <glozow> ye |

155 | 18:45 | <sipa> so! |

156 | 18:45 | <sipa> if r(x) = poly(x) mod tr(x), that must mean that r(x) = poly(x) + quotient(x)*tr(x) |

157 | 18:46 | <sipa> but we know tr(x) is 0 for half of the field |

158 | 18:46 | <sipa> (now thinking about concrete x values) |

159 | 18:46 | <sipa> this means that r(x) must have all roots that poly(x) has which coincide with roots of tr(x) (and that's half the field) |

160 | 18:47 | <sipa> because evaluating r(x) = poly(x) + quotient(x)*tr(x) in such an x just gives r(x) = 0 + quotient(x)*0 |

161 | 18:47 | <glozow> r(x)'s roots = shared roots of poly(x) and tr(x) |

162 | 18:47 | <glozow> ? |

163 | 18:47 | <sipa> it must have _at least_ those roots |

164 | 18:47 | <sipa> it can have others |

165 | 18:48 | <glozow> mm okay |

166 | 18:48 | <sipa> but to weed those out, you use a gcd |

167 | 18:48 | <sipa> the (polynomial) gcd of r(x) and poly(x) gives you something which exactly has the shared roots of poly(x) and tr(x) |

168 | 18:49 | <sipa> gcd for polynomials = literally a way to computing the polynomial consisting of all shared factors |

169 | 18:49 | <amiti> if tr(x) is 0, how do we know that poly(x) is 0? |

170 | 18:49 | <sipa> amiti: we don't, we're trying to find that |

171 | 18:50 | <amiti> oh, I see |

172 | 18:50 | <sipa> it's just the case that for all values v for which tr(v)=0, we know that poly(x) mod tr(x), evaluated in v, also gives 0 |

173 | 18:51 | <sipa> if v is a root of poly(x) |

174 | 18:51 | <sipa> and thus poly(x) mod tr(x) must be a polynomial with v as root if it's a root of both tr(x) and poly(x) |

175 | 18:51 | <eoin> what does tr(x) mean? |

176 | 18:51 | <glozow> trace function evaluated on x |

177 | 18:51 | <sipa> 09:34:02 < sipa> tr(x) = x + x^2 + x^4 + x^8 + ... + x^(q/2) |

178 | 18:52 | <sipa> we don't know anything about the other roots of (poly(x) mod tr(x)), though |

179 | 18:52 | <sipa> but after doing a gcd with poly(x), you get a polynomial with exactly the shared roots of poly(x) and tr(x) |

180 | 18:52 | <eoin> gcd? |

181 | 18:52 | <sipa> greatest common divisor |

182 | 18:53 | <eoin> is it greatest common denominator? |

183 | 18:53 | <sipa> no |

184 | 18:54 | <sipa> we're not working with numbers but with polynomials |

185 | 18:54 | <sipa> divisor is generic |

186 | 18:54 | <generic> i am? ;P |

187 | 18:54 | <sipa> hahaha |

188 | 18:54 | <jonatack> https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor |

189 | 18:55 | <sipa> so: we're almost done! |

190 | 18:55 | <sipa> we have f1(x) = gcd(r(x),poly(x)), which is the polynomial with all shared roots of poly(x) and tr(x) |

191 | 18:55 | <sipa> and f2(x) = poly(x) / f1(x), which has all the other roots |

192 | 18:55 | <sipa> f1,f2 are a factorization of poly |

193 | 18:56 | <sipa> f1 has all the roots for which tr(x)=0, f2 has all the roots for which tr(x)=1 |

194 | 18:57 | <sipa> so then you can repeat the process, but with a different a (i've been writing tr(x) everywhere, but i really meant tr(a*x)) |

195 | 18:57 | <sipa> to split f1 and f2 up further |

196 | 18:57 | <sipa> until you hit 1st degree polynomials, and if you have a 1st degree polynomial (x+m), its root is kind of obvious |

197 | 18:58 | <sipa> ok, question! what would happen if there was a duplicate root? |

198 | 18:58 | <sipa> and you'd naively do this? |

199 | 18:59 | <amiti> you'd never hit the 1st degree polynomial, but you'd keep repeating the process tryna get there? |

200 | 18:59 | <glozow> you wouldn't end up with linear factors? |

201 | 18:59 | <sipa> yeah, say you have x^2+1, which has duplicate root 1 |

202 | 18:59 | <sipa> if tr(a*1)=0, you'd always get f1(x)=x^2+1 and f2(x)=1 |

203 | 19:00 | <sipa> if tr(a*1)=1, you'd always get f1(x)=1 and f2(x)=x^2+1 |

204 | 19:00 | <sipa> so both factors would always land on the same side of the split |

205 | 19:00 | <sdaftuar> since you use a special lookup for quadratics anyway, this would only be an issue if you had a triple (or more) root -- is that right? |

206 | 19:00 | <sipa> indeed |

207 | 19:00 | <glozow> why doesn't the loop halt after trying 2^field_size times? would that do anything? |

208 | 19:00 | <sipa> glozow: ah! |

209 | 19:01 | <sipa> well, if you pick the a values randomly, you can't ever stop |

210 | 19:01 | <sipa> it turns out, you can do much better than picking them randomly |

211 | 19:01 | <glozow> is this the randv = gf.mul2(randv) line? |

212 | 19:01 | <sipa> yeah |

213 | 19:01 | <sipa> if you pick (a, 2a, 4a, 8a, 16a, ..., {q/2}a), you'll always find every root |

214 | 19:02 | <jonatack> set {2^i*a for i=0..fieldsize-1} |

215 | 19:02 | <sipa> which just needs b (=log2(q)) steps |

216 | 19:02 | <sipa> and you could indeed just stop after recursing b times |

217 | 19:02 | <sipa> and if you do that, the frobenius check at the start just becomes an optimization |

218 | 19:03 | <sipa> those a values are optimally orthogonal in a way |

219 | 19:03 | <sipa> i discovered that, and was very proud of it, because i couldn't find any implementations of BTA that used this |

220 | 19:03 | <sipa> until i learned that it's actually mentioned in berlekamp's 1967 paper that introduced the algorithm |

221 | 19:04 | <amiti> =P |

222 | 19:04 | ⚡ sdaftuar is still impressed |

223 | 19:05 | <sipa> another optimization we have: if you've computed tr(a*x) mod poly(x), you can compute x^q mod poly(x) from that too |

224 | 19:06 | <sipa> if r(x) = tr(a*x) mod poly(x), then r(x)*(r(x)+1) = (a*x)^q i believe (or (a*x)^q + (a*x), something like that |

225 | 19:07 | <sipa> and in the C++ code we use that to do the frobenius check simultaneously with the first recursion level of the factoring algorithm |

226 | 19:08 | <sipa> sdaftuar: and yeah, with the explicit formula for 2nd degree polynomials, duplicate roots specifically is not a problem (we'd detect them when trying to solve the 2nd factor) |

227 | 19:09 | <sipa> but you could have irreducible 3rd degree polynomials too, for example |

228 | 19:09 | <sipa> it's not just duplicate roots that form a problem |

229 | 19:09 | <sdaftuar> right, makes sense |

230 | 19:09 | ⚡ jonatack clapping 👏 |

231 | 19:09 | <sipa> https://github.com/sipa/minisketch/blob/master/src/sketch_impl.h#L170L202 |

232 | 19:10 | <sipa> that explains how to do the frobenius check simultaneously with splitting |

233 | 19:10 | <sipa> randv there is what i've called a here |

234 | 19:11 | <felixweis> whats randv stand for? |

235 | 19:11 | <sipa> random value |

236 | 19:11 | <sipa> :) |

237 | 19:11 | <felixweis> ok |

238 | 19:11 | <eoin> what is BCH? |

239 | 19:12 | <sipa> eoin: Bose–Chaudhuri–Hocquenghem |

240 | 19:12 | <sipa> https://en.wikipedia.org/wiki/BCH_code |

241 | 19:12 | <jonatack> probably good to add this link to the log too: https://en.wikipedia.org/wiki/GF%282%29 |

242 | 19:13 | <sipa> oh, i guess one last thing: we started from the polynomial (1+ax)(1+cx), and found its roots 1/a and 1/c |

243 | 19:13 | <sipa> but we want a and c |

244 | 19:13 | <sipa> a very simple trick helps with that: reverse the coefficients of polynomials before trying to find the roots |

245 | 19:14 | <sipa> roots of (a*x^3 + b*x^2 + c*x + d) = inverses of roots of (d*x^3 + c*x^2 + b*x + a) |

246 | 19:14 | <glozow> woah nice |

247 | 19:14 | <sipa> there also exists something called a batch inverse, where with 1 inverse + 3*n multiplications you can find the inverses of n elements at once |

248 | 19:14 | <sipa> but we don't even need it here |

249 | 19:15 | <sipa> inverses are many times more expensive than multiplications, fwiw |

250 | 19:15 | <sipa> so... any questions? :) |

251 | 19:15 | <jonatack> sipa: trick used here? roots = poly_find_roots(list(reversed(poly)), self._gf) |

252 | 19:15 | <sipa> jonatack: yes |

253 | 19:16 | <glozow> wait why is the roots of reversed = inverses of roots? |

254 | 19:16 | <sipa> aha! |

255 | 19:16 | <sipa> ok |

256 | 19:16 | <sipa> substitute y = 1/x |

257 | 19:17 | <sipa> so you start with a*x^3 + b*x^2 + c*x + d |

258 | 19:17 | <sipa> and get a*y^-3 + b*y^-2 + c*y^-1 + d |

259 | 19:17 | <sipa> now multiply everything with y^3 |

260 | 19:17 | <glozow> ohhhhhhhh |

261 | 19:17 | <sipa> and you get a + b*y + c*y^2 + d*y^3 |

262 | 19:17 | <sipa> and doing so doesn't change the roots |

263 | 19:18 | <felixweis> nice |

264 | 19:19 | <glozow> this is true in general for polynomials? |

265 | 19:19 | <sipa> yes |

266 | 19:19 | <glozow> why didn't they teach this in school |

267 | 19:19 | <glozow> jeez |

268 | 19:19 | <sipa> haha |

269 | 19:20 | <sipa> what if 0 is one of the roots? |

270 | 19:20 | <sdaftuar> no constant term? |

271 | 19:20 | <sipa> indeed |

272 | 19:20 | <sdaftuar> probably shouldn't do that trick til you factor it out |

273 | 19:20 | <sipa> it still works actually |

274 | 19:20 | <sipa> but you get a polynomial of degree one less |

275 | 19:21 | <sipa> which excludes the infinity root |

276 | 19:21 | <sipa> thankfully, not a problem for us, because we know all our roots are nonzero |

277 | 19:21 | <sipa> oh, question: why did we need the property that we encode our set elements as nonzero field elements? |

278 | 19:21 | <felixweis> https://brilliant.org/discussions/thread/proof-for-inverse-roots-polynomial/ |

279 | 19:22 | <jonatack> so in the C++ code: std::reverse(poly.begin(), poly.end()); |

280 | 19:22 | <sipa> jonatack: indeed |

281 | 19:24 | <glozow> if they're zero, |

282 | 19:24 | <sipa> what would the sketches be for sets {a} and {a,0} ? |

283 | 19:24 | <glozow> they'd be the same :O |

284 | 19:24 | <felixweis> same |

285 | 19:24 | <sipa> exactly |

286 | 19:25 | <felixweis> adding 0 is a NOP |

287 | 19:25 | <sipa> and it's kind of related to this inversion at the end: in the BM representation, the elements become inverses of the roots |

288 | 19:25 | <sipa> but 0 can't be the inverse of a root |

289 | 19:26 | <sipa> it'd be possible to just add 1 bit to every sketch to indicate "contains 0", and xor that along with everything else |

290 | 19:26 | <sipa> but just avoiding 0 is easier |

291 | 19:26 | <sdaftuar> sipa: so are you saying it's impossible for BM to spit out a polynomial with 0 as a root? or just that it means the sketch obviously won't decode? |

292 | 19:26 | <glozow> the sketches would still work, but you wouldn't be able to reconcile an element represented as 0? |

293 | 19:27 | <sipa> sdaftuar: i believe that's the case yes, BM |

294 | 19:27 | <sipa> iirc BM will always produce a polynomial with constant term 1 |

295 | 19:28 | <sipa> not entirely sure, but even if not, it can't even have a constant term 0 |

296 | 19:28 | <sipa> because then by definition it's not a minimal LFSR |

297 | 19:28 | <sdaftuar> ah |

298 | 19:29 | <jonatack> https://en.wikipedia.org/wiki/Linear_feedback_shift_register for the log |

299 | 19:29 | <glozow> is that everything for today sipa? :) |

300 | 19:30 | <sipa> seems like a good place to end :) |

301 | 19:30 | <glozow> #endmeeting |

…/…

302 | 19:37 | <sipa> minisketch started as an attempt to get an implementation of NTL's algorithms needed for erlay that wasn't GPL |

303 | 19:37 | <sipa> NTL is sort of the library people use for low-level finite field arithmetic stuff |

304 | 19:38 | <sipa> (and it was used by the authors of the PinSketch paper for their implementation) |

305 | 19:38 | <sipa> so i learned most of this just from reading the NTL source code... |

306 | 19:38 | <sipa> you can't find much about BTA online |

307 | 19:39 | <sipa> the standard algorithm for factoring polynomials over finite fields is https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm but as described there, it doesn't work for GF(2^b) fields |