Equivalence Algorithms - Revision history

http://boolean.wiki.uib.no/index.php?action=history&feed=atom&title=Equivalence_Algorithms Equivalence Algorithms - Revision history 2026-05-02T21:26:47Z Revision history for this page on the wiki MediaWiki 1.39.6 http://boolean.wiki.uib.no/index.php?title=Equivalence_Algorithms&diff=717&oldid=prev Joakim: /* Linear Equivalence */ 2024-11-23T00:48:15Z

<p><span dir="auto"><span class="autocomment">Linear Equivalence</span></span></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="language"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:48, 23 November 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l6">Line 6:</td> <td colspan="2" class="diff-lineno">Line 6:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>= Linear Equivalence = </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>= Linear Equivalence = </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Given two vectorial boolean functions <math><del style="font-weight: bold; text-decoration: none;">f </del></math> and <math> <del style="font-weight: bold; text-decoration: none;">g </del></math> we want to determine if there exist Linear permutations <math> A_1</math> and <math>A_2 </math> such that <math> F = A_2 \circ G \circ A_1 </math>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Given two vectorial boolean functions <math><ins style="font-weight: bold; text-decoration: none;">F </ins></math> and <math> <ins style="font-weight: bold; text-decoration: none;">G </ins></math> we want to determine if there exist Linear permutations <math> A_1</math> and <math>A_2 </math> such that <math> F = A_2 \circ G \circ A_1 </math>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==The to and from algorithm==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==The to and from algorithm==</div></td></tr> </table>

Joakim http://boolean.wiki.uib.no/index.php?title=Equivalence_Algorithms&diff=716&oldid=prev Joakim at 00:47, 23 November 2024 2024-11-23T00:47:45Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="language"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:47, 23 November 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l43">Line 43:</td> <td colspan="2" class="diff-lineno">Line 43:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We compose functions symbolically as <math>F \circ A_1 = \sum \alpha_u \cdot (M_u \circ A_1 ) </math>. We have that <math>deg(F \circ A_1) \leq deg(F) </math>. We can also compose <math>A_2 \circ F </math> where we replace <math>x_i</math> in <math>A_2</math> by <math>F_i</math>. Let <math>A : F_2^{n-1} \rightarrow F_2^n </math> be an affine transformation with <math>A(x) = L(x) + a</math>. The range of <math>A</math> is an affine <math>n-1</math> dimensional subspace so it's orthogonal subspace is 1 dimensional, so spanned by a single vector <math>h</math>. We call <math>h</math> the half space mask (HSM), since it partitions the space into 2 halves. <math>h \cdot a </math> is the half space free coefficient (HSC). Given an HSM and HSC <math>h</math> and <math>c</math> there is a canonical affine transformation <math>C_{|_{h,c}} : F_2^{n-1} \rightarrow F_2^n </math>. </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We compose functions symbolically as <math>F \circ A_1 = \sum \alpha_u \cdot (M_u \circ A_1 ) </math>. We have that <math>deg(F \circ A_1) \leq deg(F) </math>. We can also compose <math>A_2 \circ F </math> where we replace <math>x_i</math> in <math>A_2</math> by <math>F_i</math>. Let <math>A : F_2^{n-1} \rightarrow F_2^n </math> be an affine transformation with <math>A(x) = L(x) + a</math>. The range of <math>A</math> is an affine <math>n-1</math> dimensional subspace so it's orthogonal subspace is 1 dimensional, so spanned by a single vector <math>h</math>. We call <math>h</math> the half space mask (HSM), since it partitions the space into 2 halves. <math>h \cdot a </math> is the half space free coefficient (HSC). Given an HSM and HSC <math>h</math> and <math>c</math> there is a canonical affine transformation <math>C_{|_{h,c}} : F_2^{n-1} \rightarrow F_2^n </math>. </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We can now define the rank table of <math>F</math> with respect to some constant <math>d</math>. For any <math>h \in F_2^n </math> we calculate <math>u = SR((F \circ C_{|_{h,0}})_{\geq d} )</math> and <math>v = SR((C_{|_{h,1}})_{\geq d}) </math>. The rank table entry for <math>h</math> then becomes <math>(max(u,v),min(u,v))</math>. For any specific tuple <math>(u,v)</math> the rank group is all <math>h</math> such that the rank table entry for <math>h</math> is <math>(u,v)</math>. The rank histogram is a mapping for each <math>(u,v)</math> to the size of the rank group. One last thing we will need is the concept of the rank histogram with with respect to a given rank group. Fix an element <math>h \in F_2^n </math>. The rank histogram of <math>h</math> with respect to the rank group <math>(u,v)</math> </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>We can now define the rank table of <math>F</math> with respect to some constant <math>d</math>. For any <math>h \in F_2^n </math> we calculate <math>u = SR((F \circ C_{|_{h,0}})_{\geq d} )</math> and <math>v = SR((C_{|_{h,1}})_{\geq d}) </math>. The rank table entry for <math>h</math> then becomes <math>(max(u,v),min(u,v))</math>. For any specific tuple <math>(u,v)</math> the rank group is all <math>h</math> such that the rank table entry for <math>h</math> is <math>(u,v)</math>. The rank histogram is a mapping for each <math>(u,v)</math> to the size of the rank group. One last thing we will need is the concept of the rank histogram with with respect to a given rank group. Fix an element <math>h \in F_2^n </math>. The rank histogram of <math>h</math> with respect to the rank group <math>(u,v)</math> <ins style="font-weight: bold; text-decoration: none;">is defined the following way. Add <math>h</math> to all elements of the rank group <math>(u,v)</math> to get a set <math>U \subset F_2^n </math>. For each element <math>h'</math> of <math>U</math> we look at the rank group containing <math>h'</math>, let's say it's <math>(u',v')</math>. The multi set containing the tuples <math>(u',v')</math> for each element <math>h' \in U </math> is the rank histogram of <math>h</math> with respect to <math>(u,v)</math>. The rank group <math>(u,v) </math> with respect to <math>(u',v')</math> is the multiset rank histogram of each element <math>h</math> of the group <math>(u,v)</math> with respect to the group <math>(u',v')</math>.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Algorithm===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Algorithm===</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The main idea of the algorithm is that if <math>F</math> and <math>G</math> are affine equivalent, then <math>SR(F_{\geq d}) = SR(G_{\geq d}) </math>. If <math>F</math> and <math>G</math> are affine equivalent with <math>F = A_2 \circ G \circ A_1 </math> we are going to start by trying to reconstruct <math>A_1</math>. Do do this the idea is that for any element of the rank table of <math>(u,v)</math> of <math>G </math>. So if we find a entry <math>(u,v) </math> which contains only 1 element we know one point of <math>A_1</math>. Now the rank groups can be large so only doing this may still result in a lot of guesses. </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The main idea of the algorithm is that if <math>F</math> and <math>G</math> are affine equivalent, then <math>SR(F_{\geq d}) = SR(G_{\geq d}) </math>. If <math>F</math> and <math>G</math> are affine equivalent with <math>F = A_2 \circ G \circ A_1 </math> we are going to start by trying to reconstruct <math>A_1</math>. Do do this the idea is that for any element of the rank table of <math>(u,v)</math> of <math>G </math>. So if we find a entry <math>(u,v) </math> which contains only 1 element we know one point of <math>A_1</math>. Now the rank groups can be large so only doing this may still result in a lot of guesses<ins style="font-weight: bold; text-decoration: none;">. For some group <math>(u,v)</math> we are going to pick another group <math>(u',v')</math> and calculate the rank group of <math>(u,v)</math> with respect to <math>(u',v')</math>. If this multiset contains an unique element, then the element <math>h</math> of <math>(u,v)</math> corresponding to this element must be matched to the corresponding element of <math>G</math> (Due to the linearity of <math>A_1</math>). We can do this for any pair of groups, and if we find any element in the multiset of low cardinality we obtain a lot of information about possible matchings for <math>A_1</math>. </ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">===Runtime===</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">The algorithm is estimated to be <math>O(n^32^n)</math> for a random permutation. This is based to some assumption about the distribution of the rank tables of random functions</ins>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td></tr> </table>

Joakim http://boolean.wiki.uib.no/index.php?title=Equivalence_Algorithms&diff=715&oldid=prev Joakim at 23:54, 22 November 2024 2024-11-22T23:54:45Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="language"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 23:54, 22 November 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l41">Line 41:</td> <td colspan="2" class="diff-lineno">Line 41:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The algorithm is based on using the rank table of a boolean functions, which we will now introduce. Given a boolean function <math>F: F_2^n \rightarrow F_2 </math>. We are going to consider this object algebraically using the ANF (algebraic normal form). <math>F = \sum_{u \in F_2^n }\alpha_ux^u </math>. We can look at <math>F</math> as a vector spanned by all monomials <math>x^u = x_1^{u_1}...x_n^{u_n} </math>. Let <math>F_{\geq d}</math> be the polynomial containing all monomials of <math>F</math> with degree at least <math>d</math>. Now given a vectorial boolean functions <math>F=(F_1,...,F_m)</math> we define the symbolic rank of <math>F</math> as the rank of the vectors <math> \{F_i\}</math> (where we view <math>F_i</math> as a vector). Denote this as <math>SR(F)</math>. </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The algorithm is based on using the rank table of a boolean functions, which we will now introduce. Given a boolean function <math>F: F_2^n \rightarrow F_2 </math>. We are going to consider this object algebraically using the ANF (algebraic normal form). <math>F = \sum_{u \in F_2^n }\alpha_ux^u </math>. We can look at <math>F</math> as a vector spanned by all monomials <math>x^u = x_1^{u_1}...x_n^{u_n} </math>. Let <math>F_{\geq d}</math> be the polynomial containing all monomials of <math>F</math> with degree at least <math>d</math>. Now given a vectorial boolean functions <math>F=(F_1,...,F_m)</math> we define the symbolic rank of <math>F</math> as the rank of the vectors <math> \{F_i\}</math> (where we view <math>F_i</math> as a vector). Denote this as <math>SR(F)</math>. </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We compose functions symbolically as <math>F \circ A_1 = \sum \alpha_u \cdot (M_u \circ A_1 ) </math>. We have that <math>deg(F \circ A_1) \leq deg(F) </math>. We can also compose <math>A_2 \circ F </math> where we replace <math>x_i</math> in <math>A_2</math> by <math>F_i</math>. Let <math>A : F_2^{n-1} \rightarrow F_2^n </math> be an affine transformation with <math>A(x) = L(x) + a</math>. The range of <math>A</math> is an affine <math>n-1</math> dimensional subspace so it's orthogonal subspace is 1 dimensional, so spanned by a single vector <math>h</math>. We call <math>h</math> the half space mask (HSM), since it partitions the space into 2 halves. <math>h \cdot a </math> is the half space free coefficient (HSC). Given an HSM and HSC <math>h</math> and <math>c</math> there is a canonical affine transformation <math>C_{|_{h,c}} : F_2{n-1} \rightarrow F_2^n </math>. </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>We compose functions symbolically as <math>F \circ A_1 = \sum \alpha_u \cdot (M_u \circ A_1 ) </math>. We have that <math>deg(F \circ A_1) \leq deg(F) </math>. We can also compose <math>A_2 \circ F </math> where we replace <math>x_i</math> in <math>A_2</math> by <math>F_i</math>. Let <math>A : F_2^{n-1} \rightarrow F_2^n </math> be an affine transformation with <math>A(x) = L(x) + a</math>. The range of <math>A</math> is an affine <math>n-1</math> dimensional subspace so it's orthogonal subspace is 1 dimensional, so spanned by a single vector <math>h</math>. We call <math>h</math> the half space mask (HSM), since it partitions the space into 2 halves. <math>h \cdot a </math> is the half space free coefficient (HSC). Given an HSM and HSC <math>h</math> and <math>c</math> there is a canonical affine transformation <math>C_{|_{h,c}} : F_2<ins style="font-weight: bold; text-decoration: none;">^</ins>{n-1} \rightarrow F_2^n </math>. </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We can now define the rank table of <math>F</math> with respect to some constant <math>d</math>. For any <math>h \in F_2^n </math> we calculate <math>u = SR((F \circ C_{|_{h,0}})_{\geq d} )</math> and <math>v = SR((C_{|_{h,1}})_{\geq d}) </math>. <del style="font-weight: bold; text-decoration: none;"> </del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>We can now define the rank table of <math>F</math> with respect to some constant <math>d</math>. For any <math>h \in F_2^n </math> we calculate <math>u = SR((F \circ C_{|_{h,0}})_{\geq d} )</math> and <math>v = SR((C_{|_{h,1}})_{\geq d}) </math>. <ins style="font-weight: bold; text-decoration: none;">The rank table entry for <math>h</math> then becomes <math>(max(u,v),min(u,v))</math>. For any specific tuple <math>(u,v)</math> the rank group is all <math>h</math> such that the rank table entry for <math>h</math> is <math>(u,v)</math>. The rank histogram is a mapping for each <math>(u,v)</math> to the size of the rank group. One last thing we will need is the concept of the rank histogram with with respect to a given rank group. Fix an element <math>h \in F_2^n </math>. The rank histogram of <math>h</math> with respect to the rank group <math>(u,v)</math> </ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The main idea of the algorithm is that if <math>F</math> and <math>G</math> are affine equivalent, then <math>SR(F_{\geq d}) = SR(G_{\geq d}) </math> </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">===Algorithm===</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The main idea of the algorithm is that if <math>F</math> and <math>G</math> are affine equivalent, then <math>SR(F_{\geq d}) = SR(G_{\geq d}) </math><ins style="font-weight: bold; text-decoration: none;">. If <math>F</math> and <math>G</math> are affine equivalent with <math>F = A_2 \circ G \circ A_1 </math> we are going to start by trying to reconstruct <math>A_1</math>. Do do this the idea is that for any element of the rank table of <math>(u,v)</math> of <math>G </math>. So if we find a entry <math>(u,v) </math> which contains only 1 element we know one point of <math>A_1</math>. Now the rank groups can be large so only doing this may still result in a lot of guesses. </ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td></tr> </table>

Joakim http://boolean.wiki.uib.no/index.php?title=Equivalence_Algorithms&diff=714&oldid=prev Joakim at 22:40, 22 November 2024 2024-11-22T22:40:57Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="language"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 22:40, 22 November 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l41">Line 41:</td> <td colspan="2" class="diff-lineno">Line 41:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The algorithm is based on using the rank table of a boolean functions, which we will now introduce. Given a boolean function <math>F: F_2^n \rightarrow F_2 </math>. We are going to consider this object algebraically using the ANF (algebraic normal form). <math>F = \sum_{u \in F_2^n }\alpha_ux^u </math>. We can look at <math>F</math> as a vector spanned by all monomials <math>x^u = x_1^{u_1}...x_n^{u_n} </math>. Let <math>F_{\geq d}</math> be the polynomial containing all monomials of <math>F</math> with degree at least <math>d</math>. Now given a vectorial boolean functions <math>F=(F_1,...,F_m)</math> we define the symbolic rank of <math>F</math> as the rank of the vectors <math> \{F_i\}</math> (where we view <math>F_i</math> as a vector). Denote this as <math>SR(F)</math>. </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>The algorithm is based on using the rank table of a boolean functions, which we will now introduce. Given a boolean function <math>F: F_2^n \rightarrow F_2 </math>. We are going to consider this object algebraically using the ANF (algebraic normal form). <math>F = \sum_{u \in F_2^n }\alpha_ux^u </math>. We can look at <math>F</math> as a vector spanned by all monomials <math>x^u = x_1^{u_1}...x_n^{u_n} </math>. Let <math>F_{\geq d}</math> be the polynomial containing all monomials of <math>F</math> with degree at least <math>d</math>. Now given a vectorial boolean functions <math>F=(F_1,...,F_m)</math> we define the symbolic rank of <math>F</math> as the rank of the vectors <math> \{F_i\}</math> (where we view <math>F_i</math> as a vector). Denote this as <math>SR(F)</math>. </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We compose functions symbolically as <math>F \circ A_1 = \sum \alpha_u \cdot (M_u \circ A_1 ) </math>. We have that <math>deg(F \circ A_1) \leq deg(F) </math>. We can also compose <math>A_2 \circ F </math> where we replace <math>x_i</math> in <math>A_2</math> by <math>F_i</math>. Let <math>A : F_2^{n-1} \rightarrow F_2^n </math> be an affine transformation with <math>A(x) = L(x) + a</math>. The range of <math>A</math> is an affine <math>n-1</math> dimensional subspace so it's orthogonal subspace is 1 dimensional, so spanned by a single vector <math>h</math>. We call <math>h</math> the half space mask (HSM), since it partitions the space into 2 halves. <math>h \cdot a </math> is the half space free coefficient (HSC). Given an HSM and HSC <math>h</math> and <math>c</math> there is a canonical affine transformation <math>C_{|_{h,c}} : F_2{n-1} \rightarrow F_2^n </math> </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>We compose functions symbolically as <math>F \circ A_1 = \sum \alpha_u \cdot (M_u \circ A_1 ) </math>. We have that <math>deg(F \circ A_1) \leq deg(F) </math>. We can also compose <math>A_2 \circ F </math> where we replace <math>x_i</math> in <math>A_2</math> by <math>F_i</math>. Let <math>A : F_2^{n-1} \rightarrow F_2^n </math> be an affine transformation with <math>A(x) = L(x) + a</math>. The range of <math>A</math> is an affine <math>n-1</math> dimensional subspace so it's orthogonal subspace is 1 dimensional, so spanned by a single vector <math>h</math>. We call <math>h</math> the half space mask (HSM), since it partitions the space into 2 halves. <math>h \cdot a </math> is the half space free coefficient (HSC). Given an HSM and HSC <math>h</math> and <math>c</math> there is a canonical affine transformation <math>C_{|_{h,c}} : F_2{n-1} \rightarrow F_2^n <ins style="font-weight: bold; text-decoration: none;"></math>. </ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">We can now define the rank table of <math>F</math> with respect to some constant <math>d</math>. For any <math>h \in F_2^n </math> we calculate <math>u = SR((F \circ C_{|_{h,0}})_{\geq d} )</math> and <math>v = SR((C_{|_{h,1}})_{\geq d}) </math>. </ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">The main idea of the algorithm is that if <math>F</math> and <math>G</math> are affine equivalent, then <math>SR(F_{\geq d}) = SR(G_{\geq d}) </ins></math> </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td></tr> </table>

Joakim http://boolean.wiki.uib.no/index.php?title=Equivalence_Algorithms&diff=713&oldid=prev Joakim at 22:06, 22 November 2024 2024-11-22T22:06:19Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="language"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 22:06, 22 November 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l39">Line 39:</td> <td colspan="2" class="diff-lineno">Line 39:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Rank table===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Rank table===</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The algorithm is based on using the rank table of a boolean functions, which we will now introduce. Given a boolean function <math>F: F_2^n \rightarrow F_2 </math>. We are going to consider this object algebraically using the ANF (algebraic normal form). <math>F = \sum_{u \in F_2^n }\alpha_ux^u </math>. We can look at <math>F</math> as a vector spanned by all monomials <math>x^u = x_1^{u_1}...x_n^{u_n} </math>. Let <math>F_{\geq d}</math> be the polynomial containing all monomials of <math>F</math> with degree at least <math>d</math>. Now given a vectorial boolean functions <math>F=(F_1,...,F_m)</math> we define the symbolic rank of <math>F</math> as the rank of the vectors <math> \{F_i\}</math> (where we view <math>F_i</math> as a vector). Denote this as <math>SR(F)</math>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The algorithm is based on using the rank table of a boolean functions, which we will now introduce. Given a boolean function <math>F: F_2^n \rightarrow F_2 </math>. We are going to consider this object algebraically using the ANF (algebraic normal form). <math>F = \sum_{u \in F_2^n }\alpha_ux^u </math>. We can look at <math>F</math> as a vector spanned by all monomials <math>x^u = x_1^{u_1}...x_n^{u_n} </math>. Let <math>F_{\geq d}</math> be the polynomial containing all monomials of <math>F</math> with degree at least <math>d</math>. Now given a vectorial boolean functions <math>F=(F_1,...,F_m)</math> we define the symbolic rank of <math>F</math> as the rank of the vectors <math> \{F_i\}</math> (where we view <math>F_i</math> as a vector). Denote this as <math>SR(F)</math>. </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">We compose functions symbolically as <math>F \circ A_1 = \sum \alpha_u \cdot (M_u \circ A_1 ) </math>. We have that <math>deg(F \circ A_1) \leq deg(F) </math>. We can also compose <math>A_2 \circ F </math> where we replace <math>x_i</math> in <math>A_2</math> by <math>F_i</math>. Let <math>A : F_2^{n-1} \rightarrow F_2^n </math> be an affine transformation with <math>A(x) = L(x) + a</math>. The range of <math>A</math> is an affine <math>n-1</math> dimensional subspace so it's orthogonal subspace is 1 dimensional, so spanned by a single vector <math>h</math>. We call <math>h</math> the half space mask (HSM), since it partitions the space into 2 halves. <math>h \cdot a </math> is the half space free coefficient (HSC). Given an HSM and HSC <math>h</math> and <math>c</math> there is a canonical affine transformation <math>C_{|_{h,c}} : F_2{n-1} \rightarrow F_2^n </math> </ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td></tr> </table>

Joakim http://boolean.wiki.uib.no/index.php?title=Equivalence_Algorithms&diff=712&oldid=prev Joakim at 21:22, 22 November 2024 2024-11-22T21:22:17Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="language"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 21:22, 22 November 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l36">Line 36:</td> <td colspan="2" class="diff-lineno">Line 36:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Rank Algorithm==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Rank Algorithm==</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>This algorithm <ref name ="rank">Dinur, Itai. "An improved affine equivalence algorithm for random permutations." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer International Publishing, 2018.</ref> is efficient also for non-permutations but only functions of high algebraic degrees.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>This algorithm <ref name ="rank">Dinur, Itai. "An improved affine equivalence algorithm for random permutations." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer International Publishing, 2018.</ref> is efficient also for non-permutations but only functions of high algebraic degrees. </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">===Rank table===</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">The algorithm is based on using the rank table of a boolean functions, which we will now introduce. Given a boolean function <math>F: F_2^n \rightarrow F_2 </math>. We are going to consider this object algebraically using the ANF (algebraic normal form). <math>F = \sum_{u \in F_2^n }\alpha_ux^u </math>. We can look at <math>F</math> as a vector spanned by all monomials <math>x^u = x_1^{u_1}...x_n^{u_n} </math>. Let <math>F_{\geq d}</math> be the polynomial containing all monomials of <math>F</math> with degree at least <math>d</math>. Now given a vectorial boolean functions <math>F=(F_1,...,F_m)</math> we define the symbolic rank of <math>F</math> as the rank of the vectors <math> \{F_i\}</math> (where we view <math>F_i</math> as a vector). Denote this as <math>SR(F)</math>.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Given two boolean functions <math>F,G : F_2^n \rightarrow F_2^m </math> find two affine permutations <math>A_1,A_2</math> and an affine transformation <math>A_3</math> such that <math>F = A_2 \circ G \circ A_1 + A_3 </math></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Given two boolean functions <math>F,G : F_2^n \rightarrow F_2^m </math> find two affine permutations <math>A_1,A_2</math> and an affine transformation <math>A_3</math> such that <math> F = A_2 \circ G \circ A_1 + A_3 </math></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Jacobian algorithm==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Jacobian algorithm==</div></td></tr> </table>

Joakim http://boolean.wiki.uib.no/index.php?title=Equivalence_Algorithms&diff=711&oldid=prev Joakim at 14:52, 22 November 2024 2024-11-22T14:52:51Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="language"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 14:52, 22 November 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l34">Line 34:</td> <td colspan="2" class="diff-lineno">Line 34:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To actually compute the minimal representative of a function <math>F</math> we do the following. We want to construct <math>F'</math>, the minimal permutation which is linear equivalent with <math>F</math>. We start by guessing the value of <math>A_1</math> at the smallest element of <math>F_2^n</math>. Let say <math>A_1(x) = y</math>. We now do the same as before with going back and forth between <math>A_1 </math> and <math>A_2</math>, the only difference we always pick the lowest possible value of <math>A_1</math> to deduce a value of <math>A_2</math> and vise versa. Also whenever we need the value of a undefined point of <math>F'</math>, we simply set to it to the lowest available.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>To actually compute the minimal representative of a function <math>F</math> we do the following. We want to construct <math>F'</math>, the minimal permutation which is linear equivalent with <math>F</math>. We start by guessing the value of <math>A_1</math> at the smallest element of <math>F_2^n</math>. Let say <math>A_1(x) = y</math>. We now do the same as before with going back and forth between <math>A_1 </math> and <math>A_2</math>, the only difference we always pick the lowest possible value of <math>A_1</math> to deduce a value of <math>A_2</math> and vise versa. Also whenever we need the value of a undefined point of <math>F'</math>, we simply set to it to the lowest available.</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==Rank Algorithm==</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">This algorithm <ref name ="rank">Dinur, Itai. "An improved affine equivalence algorithm for random permutations." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer International Publishing, 2018.</ref> is efficient also for non-permutations but only functions of high algebraic degrees.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=EA equivalence=</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> </table>

Joakim http://boolean.wiki.uib.no/index.php?title=Equivalence_Algorithms&diff=710&oldid=prev Joakim at 14:36, 22 November 2024 2024-11-22T14:36:54Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="language"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 14:36, 22 November 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l70">Line 70:</td> <td colspan="2" class="diff-lineno">Line 70:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Runtime===</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>===Runtime===</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">The runtime of this algorithm is related to the rank table which is related to the differential uniformity of the function. Let <math>R = \min R(F)[j] </math>. Then we will at worst have to make around <math>R^s</math> guesses. For each such guess we will have to solve some linear equations which can be done in around <math>(n^2+m^2)^w</math> where <math>w</math> is a matrix multiplication constant. In total we get a time of <math>O(max(n,m)^w2^n + R^s(m^2+n^2)^w)</math>, where the first part is for computing the rank table. Note that when <math>F</math> is APN all the values have the same rank, so <math>R = 2^n</math>. Which is the worst case for this algorithm.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=References=</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=References=</div></td></tr> </table>

Joakim http://boolean.wiki.uib.no/index.php?title=Equivalence_Algorithms&diff=709&oldid=prev Joakim at 14:20, 22 November 2024 2024-11-22T14:20:40Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="language"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 14:20, 22 November 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l65">Line 65:</td> <td colspan="2" class="diff-lineno">Line 65:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>2. Let <math>s</math> be the number of guesses of <math>A_1</math> we are going to make. Let <math>i = \min |R(F)[j]| </math>. Pick <math>s</math> elements of <math>R(F)[i]</math>. We are then gonna guess all possible values of <math>A_1</math> on these points. But we only have to guess values inside <math>R[G][i]</math>. Let's say we made the guesses <math>A_1u_1 = w_1,...,A_1u_s = w_s</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>2. Let <math>s</math> be the number of guesses of <math>A_1</math> we are going to make. Let <math>i = \min |R(F)[j]| </math>. Pick <math>s</math> elements of <math>R(F)[i]</math>. We are then gonna guess all possible values of <math>A_1</math> on these points. But we only have to guess values inside <math>R[G][i]</math>. Let's say we made the guesses <math>A_1u_1 = w_1,...,A_1u_s = w_s</math>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>3. <del style="font-weight: bold; text-decoration: none;">Solve </del>the <math>s</math> system of equations <math>X \cdot Jac_{lin}F(v_i) - Jac_{lin}F(w_i)\cdot Y, Y <del style="font-weight: bold; text-decoration: none;">c</del>\<del style="font-weight: bold; text-decoration: none;">dot </del>v_i = 0 </math></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>3. <ins style="font-weight: bold; text-decoration: none;">Try to solve </ins>the <math>s</math> system of equations <math>X \cdot Jac_{lin}F(v_i) - Jac_{lin}F(w_i)\cdot Y,<ins style="font-weight: bold; text-decoration: none;">\: </ins>Y \<ins style="font-weight: bold; text-decoration: none;">cdot </ins>v_i = 0 </math><ins style="font-weight: bold; text-decoration: none;">. If this system has to many solutions make another guess (increase the value of <math>s</math> temporary).</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">4. When the system of equations does not have to many solutions find all solutions <math>(L_2,A_1)</math>. Then deduce the rest of the values <math>A_3</math>, <math>a_2</math>. If this is possible we are done, otherwise go back to step 2 and make another guess.</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">===Runtime===</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=References=</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=References=</div></td></tr> </table>

Joakim http://boolean.wiki.uib.no/index.php?title=Equivalence_Algorithms&diff=708&oldid=prev Joakim at 14:13, 22 November 2024 2024-11-22T14:13:39Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="language"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 14:13, 22 November 2024</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l62">Line 62:</td> <td colspan="2" class="diff-lineno">Line 62:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>1. Compute the rank table of <math>F</math>. <math>R(F)[j] = \{x \in F_2^n | rank(Jac_{lin}F(x)) = j \} </math>. Do the same for <math>G</math></div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>1. Compute the rank table of <math>F</math>. <math>R(F)[j] = \{x \in F_2^n | rank(Jac_{lin}F(x)) = j \} </math>. Do the same for <math>G</math></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">2. Let <math>s</math> be the number of guesses of <math>A_1</math> we are going to make. Let <math>i = \min |R(F)[j]| </math>. Pick <math>s</math> elements of <math>R(F)[i]</math>. We are then gonna guess all possible values of <math>A_1</math> on these points. But we only have to guess values inside <math>R[G][i]</math>. Let's say we made the guesses <math>A_1u_1 = w_1,...,A_1u_s = w_s</math>.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">3. Solve the <math>s</math> system of equations <math>X \cdot Jac_{lin}F(v_i) - Jac_{lin}F(w_i)\cdot Y, Y c\dot v_i = 0 </math></ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=References=</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=References=</div></td></tr> </table>

Joakim