<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> <title>M4RI: testsuite/test_elimination.c</title> <link href="tabs.css" rel="stylesheet" type="text/css"/> <link href="doxygen.css" rel="stylesheet" type="text/css"/> </head> <body> <!-- Generated by Doxygen 1.7.4 --> <div id="top"> <div id="titlearea"> <table cellspacing="0" cellpadding="0"> <tbody> <tr style="height: 56px;"> <td style="padding-left: 0.5em;"> <div id="projectname">M4RI <span id="projectnumber">1.0.1</span></div> </td> </tr> </tbody> </table> </div> <div id="navrow1" class="tabs"> <ul class="tablist"> <li><a href="index.html"><span>Main Page</span></a></li> <li><a href="pages.html"><span>Related Pages</span></a></li> <li><a href="annotated.html"><span>Data Structures</span></a></li> <li><a href="files.html"><span>Files</span></a></li> <li><a href="examples.html"><span>Examples</span></a></li> </ul> </div> </div> <div class="header"> <div class="headertitle"> <div class="title">testsuite/test_elimination.c</div> </div> </div> <div class="contents"> <p>Matrix elimination using the 'Method of the Four Russians' (M4RI). The M4RI algorithm was proposed in Gregory Bard; Accelerating Cryptanalysis with the Method of Four Russians; 2006; <a href="http://eprint.iacr.org/2006/251">http://eprint.iacr.org/2006/251</a></p> <p>Our implementatation is discussed in in Martin Albrecht and ClĂ©ment Pernet; Efficient Decomposition of Dense Matrices over GF(2); <a href="http://arxiv.org/abs/1006.1744">http://arxiv.org/abs/1006.1744</a></p> <dl><dt><b>Parameters:</b></dt><dd> <table class="params"> <tr><td class="paramname">M</td><td>Matrix to be reduced. </td></tr> <tr><td class="paramname">full</td><td>Return the reduced row echelon form, not only upper triangular form. </td></tr> <tr><td class="paramname">k</td><td>M4RI parameter, may be 0 for auto-choose.</td></tr> </table> </dd> </dl> <div class="fragment"><pre class="fragment"><span class="preprocessor">#include <stdlib.h></span> <span class="preprocessor">#include "m4ri/m4ri.h"</span> <span class="keywordtype">int</span> elim_test_equality(<span class="keywordtype">int</span> nr, <span class="keywordtype">int</span> nc) { <span class="keywordtype">int</span> ret = 0; printf(<span class="stringliteral">"elim: m: %4d, n: %4d "</span>,nr,nc); <a name="_a0"></a><a class="code" href="structmzd__t.html" title="Dense matrices over GF(2).">mzd_t</a> *A = <a name="a1"></a>mzd_init(nr, nc); <a name="a2"></a>mzd_randomize(A); <a class="code" href="structmzd__t.html" title="Dense matrices over GF(2).">mzd_t</a> *B = <a name="a3"></a>mzd_copy(NULL, A); <a class="code" href="structmzd__t.html" title="Dense matrices over GF(2).">mzd_t</a> *C = mzd_copy(NULL, A); <a class="code" href="structmzd__t.html" title="Dense matrices over GF(2).">mzd_t</a> *D = mzd_copy(NULL, A); <a class="code" href="structmzd__t.html" title="Dense matrices over GF(2).">mzd_t</a> *E = mzd_copy(NULL, A); <a class="code" href="structmzd__t.html" title="Dense matrices over GF(2).">mzd_t</a> *F = mzd_copy(NULL, A); <a class="code" href="structmzd__t.html" title="Dense matrices over GF(2).">mzd_t</a> *G = mzd_copy(NULL, A); <span class="comment">/* M4RI k=auto */</span> <a name="a4"></a>mzd_echelonize_m4ri(A, 1, 0); <span class="comment">/* M4RI k=8 */</span> mzd_echelonize_m4ri(B, 1, 8); <span class="comment">/* M4RI Upper Triangular k=auto*/</span> mzd_echelonize_m4ri(C, 0, 0); <a name="a5"></a>mzd_top_echelonize_m4ri(C, 0); <span class="comment">/* M4RI Upper Triangular k=4*/</span> mzd_echelonize_m4ri(D, 0, 4); mzd_top_echelonize_m4ri(D, 4); <span class="comment">/* Gauss */</span> <a name="a6"></a>mzd_echelonize_naive(E, 1); <span class="comment">/* Gauss Upper Triangular */</span> mzd_echelonize_naive(F, 0); mzd_top_echelonize_m4ri(F, 0); <span class="comment">/* PLUQ */</span> <a name="a7"></a>mzd_echelonize_pluq(G, 1); <span class="keywordflow">if</span>(<a name="a8"></a>mzd_equal(A, B) != <a name="a9"></a><a class="code" href="misc_8h.html#aa8cecfc5c5c054d2875c03e77b7be15d" title="Pretty for 1.">TRUE</a>) { printf(<span class="stringliteral">"A != B "</span>); ret -= 1; } <span class="keywordflow">if</span>(mzd_equal(B, C) != <a class="code" href="misc_8h.html#aa8cecfc5c5c054d2875c03e77b7be15d" title="Pretty for 1.">TRUE</a>) { printf(<span class="stringliteral">"B != C "</span>); ret -= 1; } <span class="keywordflow">if</span>(mzd_equal(D, E) != <a class="code" href="misc_8h.html#aa8cecfc5c5c054d2875c03e77b7be15d" title="Pretty for 1.">TRUE</a>) { printf(<span class="stringliteral">"D != E "</span>); ret -= 1; } <span class="keywordflow">if</span>(mzd_equal(E, F) != <a class="code" href="misc_8h.html#aa8cecfc5c5c054d2875c03e77b7be15d" title="Pretty for 1.">TRUE</a>) { printf(<span class="stringliteral">"E != F "</span>); ret -= 1; } <span class="keywordflow">if</span>(mzd_equal(F, G) != <a class="code" href="misc_8h.html#aa8cecfc5c5c054d2875c03e77b7be15d" title="Pretty for 1.">TRUE</a>) { printf(<span class="stringliteral">"F != G "</span>); ret -= 1; } <span class="keywordflow">if</span>(mzd_equal(G, A) != <a class="code" href="misc_8h.html#aa8cecfc5c5c054d2875c03e77b7be15d" title="Pretty for 1.">TRUE</a>) { printf(<span class="stringliteral">"G != A "</span>); ret -= 1; } <a name="a10"></a>mzd_free(A); mzd_free(B); mzd_free(C); mzd_free(D); mzd_free(E); mzd_free(F); mzd_free(G); <span class="keywordflow">if</span>(ret == 0) { printf(<span class="stringliteral">" ... passed\n"</span>); } <span class="keywordflow">else</span> { printf(<span class="stringliteral">" ... FAILED\n"</span>); } <span class="keywordflow">return</span> ret; } <span class="keywordtype">int</span> main(<span class="keywordtype">int</span> argc, <span class="keywordtype">char</span> **argv) { <span class="keywordtype">int</span> status = 0; status += elim_test_equality(100, 100); status += elim_test_equality(21, 171); status += elim_test_equality(31, 121); status += elim_test_equality(193, 65); status += elim_test_equality(1025, 1025); status += elim_test_equality(2048, 2048); status += elim_test_equality(64, 64); status += elim_test_equality(128, 128); status += elim_test_equality(4096, 3528); status += elim_test_equality(1024, 1025); status += elim_test_equality(1000,1000); status += elim_test_equality(1000,10); status += elim_test_equality(1710,1290); status += elim_test_equality(1290, 1710); status += elim_test_equality(1290, 1710); status += elim_test_equality(1290, 1290); status += elim_test_equality(1000, 210); <span class="keywordflow">if</span> (status == 0) { printf(<span class="stringliteral">"All tests passed.\n"</span>); <span class="keywordflow">return</span> 0; } <span class="keywordflow">else</span> { <span class="keywordflow">return</span> -1; } } </pre></div> </div> </div> <hr class="footer"/><address class="footer"><small>Generated on Sat Apr 23 2011 for M4RI by  <a href="http://www.doxygen.org/index.html"> <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.4 </small></address> </body> </html>