| 1 |
<!DOCTYPE html> |
| 2 |
<html><head> |
| 3 |
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/> |
| 4 |
<title>highlight.mac</title> |
| 5 |
<meta name="generator" content="KF5::SyntaxHighlighting - Definition (Maxima) - Theme (Breeze Dark)"/> |
| 6 |
</head><body style="background-color:#232629;color:#cfcfc2"><pre> |
| 7 |
<span style="color:#7a7c7d;">/*</span> |
| 8 |
<span style="color:#7a7c7d;">------------------------------------------------------------------------</span> |
| 9 |
<span style="color:#7a7c7d;">Efficient Galois Fields in Maxima</span> |
| 10 |
|
| 11 |
<span style="color:#7a7c7d;">by Alasdair McAndrew</span> |
| 12 |
<span style="color:#7a7c7d;">and later extended by Fabrizio Caruso and Jacopo Daurizio</span> |
| 13 |
|
| 14 |
<span style="color:#7a7c7d;">it is distribuited together with gf_roots by Jacopo Daurizio</span> |
| 15 |
|
| 16 |
<span style="color:#7a7c7d;">Authors:</span> |
| 17 |
|
| 18 |
<span style="color:#7a7c7d;">Fabrizio Caruso (optimizations, testing)</span> |
| 19 |
<span style="color:#7a7c7d;">Jacopo D'Aurizio (optimizations, modular roots)</span> |
| 20 |
<span style="color:#7a7c7d;">Alasdair McAndrew (original version of the package, pohlig-helman log, etc... )</span> |
| 21 |
<span style="color:#7a7c7d;">------------------------------------------------------------------------*/</span> |
| 22 |
|
| 23 |
<span style="color:#7a7c7d;">/* Released under terms of the GNU General Public License, version 2,</span> |
| 24 |
<span style="color:#7a7c7d;"> * by permission of the authors to Robert Dodier circa 2007-12-02.</span> |
| 25 |
<span style="color:#7a7c7d;"> */</span> |
| 26 |
|
| 27 |
<span style="color:#7a7c7d;">/* Defines a flag for dealing with large fields. If it is set to "false",</span> |
| 28 |
<span style="color:#7a7c7d;">then lookup tables are used for exponentiation and logarithms. Otherwise</span> |
| 29 |
<span style="color:#7a7c7d;">other algorithms are used */</span> |
| 30 |
|
| 31 |
<span style="color:#8e44ad;">define_variable</span>(<span style="color:#27aeae;font-weight:bold;">largefield</span>,<span style="font-weight:bold;">true</span>,<span style="color:#27aeae;font-weight:bold;">bool</span>)$ |
| 32 |
<span style="color:#8e44ad;">define_variable</span>(<span style="color:#27aeae;font-weight:bold;">gf_char</span>,<span style="color:#f67400;">0</span>,<span style="color:#27aeae;font-weight:bold;">integer</span>)$ |
| 33 |
<span style="color:#8e44ad;">define_variable</span>(<span style="color:#27aeae;font-weight:bold;">gf_exp</span>,<span style="color:#f67400;">0</span>,<span style="color:#27aeae;font-weight:bold;">integer</span>)$ |
| 34 |
<span style="color:#8e44ad;">define_variable</span>(<span style="color:#27aeae;font-weight:bold;">gf_order</span>,<span style="color:#f67400;">0</span>,<span style="color:#27aeae;font-weight:bold;">integer</span>)$ |
| 35 |
<span style="color:#8e44ad;">define_variable</span> (<span style="color:#27aeae;font-weight:bold;">gf_one</span>, <span style="color:#a43340;font-weight:bold;">'</span><span style="color:#27aeae;font-weight:bold;">gf_one</span>, <span style="color:#27aeae;font-weight:bold;">any_check</span>)$ |
| 36 |
<span style="color:#8e44ad;">define_variable</span> (<span style="color:#27aeae;font-weight:bold;">gf_prim</span>, <span style="color:#a43340;font-weight:bold;">'</span><span style="color:#27aeae;font-weight:bold;">gf_prim</span>, <span style="color:#27aeae;font-weight:bold;">any_check</span>)$ |
| 37 |
<span style="color:#8e44ad;">define_variable</span> (<span style="color:#27aeae;font-weight:bold;">gf_irr</span>, <span style="color:#a43340;font-weight:bold;">'</span><span style="color:#27aeae;font-weight:bold;">gf_irr</span>, <span style="color:#27aeae;font-weight:bold;">any_check</span>)$ |
| 38 |
<span style="color:#8e44ad;">define_variable</span> (<span style="color:#27aeae;font-weight:bold;">gf_list</span>, <span style="color:#a43340;font-weight:bold;">'</span><span style="color:#27aeae;font-weight:bold;">gf_list</span>, <span style="color:#27aeae;font-weight:bold;">any_check</span>)$ |
| 39 |
<span style="color:#8e44ad;">define_variable</span> (<span style="color:#27aeae;font-weight:bold;">gen_powers</span>, <span style="color:#a43340;font-weight:bold;">'</span><span style="color:#27aeae;font-weight:bold;">gf_list</span>, <span style="color:#27aeae;font-weight:bold;">any_check</span>)$ |
| 40 |
<span style="color:#8e44ad;">remvalue</span>(<span style="color:#27aeae;font-weight:bold;">x</span>,<span style="color:#27aeae;font-weight:bold;">z</span>,<span style="color:#27aeae;font-weight:bold;">gf_char</span>,<span style="color:#27aeae;font-weight:bold;">gf_exp</span>,<span style="color:#27aeae;font-weight:bold;">gf_irr</span>,<span style="color:#27aeae;font-weight:bold;">pg</span>,<span style="color:#27aeae;font-weight:bold;">gp</span>,<span style="color:#27aeae;font-weight:bold;">lg</span>,<span style="color:#27aeae;font-weight:bold;">gf_prim</span>,<span style="color:#27aeae;font-weight:bold;">gf_one</span>,<span style="color:#27aeae;font-weight:bold;">gf_order</span>,<span style="color:#27aeae;font-weight:bold;">gf_list</span>,<span style="color:#27aeae;font-weight:bold;">gen_powers</span>)$ |
| 41 |
|
| 42 |
|
| 43 |
<span style="color:#7a7c7d;">/* --------------------------------------------------------------------------------------------- */</span> |
| 44 |
<span style="color:#7a7c7d;">/* Settings */</span> |
| 45 |
|
| 46 |
<span style="color:#27aeae;font-weight:bold;">GF_VERBOSE</span>:<span style="font-weight:bold;">false</span>; <span style="color:#7a7c7d;">/* Verbosity */</span> |
| 47 |
<span style="color:#27aeae;font-weight:bold;">GF_WARNING</span>: <span style="font-weight:bold;">true</span>; <span style="color:#7a7c7d;">/* Warnings */</span> |
| 48 |
<span style="color:#27aeae;font-weight:bold;">GF_IRREDUCIBILITY_CHECK</span>:<span style="font-weight:bold;">false</span>; <span style="color:#7a7c7d;">/* Irreducibility test for the minimal polynomial of the extension */</span> |
| 49 |
|
| 50 |
<span style="color:#7a7c7d;">/*</span> |
| 51 |
<span style="color:#7a7c7d;">------------------------------------------------------------------------------------------------ */</span> |
| 52 |
|
| 53 |
|
| 54 |
<span style="color:#7a7c7d;">/* It defines a new current field with gf_char=b, min. pol.= p of deg= e*/</span> |
| 55 |
<span style="color:#27aeae;font-weight:bold;">gf_set</span>([<span style="color:#27aeae;font-weight:bold;">ars</span>]):=<span style="color:#8e44ad;">block</span>([<span style="color:#27aeae;font-weight:bold;">gj</span>,<span style="color:#27aeae;font-weight:bold;">m</span>,<span style="color:#27aeae;font-weight:bold;">i</span>,<span style="color:#27aeae;font-weight:bold;">j</span>,<span style="color:#27aeae;font-weight:bold;">dg</span>], |
| 56 |
<span style="font-weight:bold;">if</span> <span style="color:#8e44ad;">length</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>)=<span style="color:#f67400;">1</span> <span style="font-weight:bold;">then</span> |
| 57 |
( |
| 58 |
<span style="color:#27aeae;font-weight:bold;">gf_setp</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">1</span>]), |
| 59 |
<span style="color:#8e44ad;">return</span>(<span style="font-weight:bold;">true</span>) |
| 60 |
) |
| 61 |
<span style="font-weight:bold;">else</span> |
| 62 |
( |
| 63 |
<span style="font-weight:bold;">if</span> <span style="color:#8e44ad;">length</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>)=<span style="color:#f67400;">2</span> <span style="font-weight:bold;">then</span> |
| 64 |
( |
| 65 |
<span style="font-weight:bold;">if</span> <span style="color:#8e44ad;">numberp</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">2</span>]) <span style="font-weight:bold;">then</span> |
| 66 |
( |
| 67 |
<span style="font-weight:bold;">if</span> <span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">2</span>]=<span style="color:#f67400;">0</span> <span style="font-weight:bold;">and</span> <span style="color:#27aeae;font-weight:bold;">GF_WARNING</span> <span style="font-weight:bold;">then</span> |
| 68 |
( |
| 69 |
<span style="color:#8e44ad;">print</span>(<span style="color:#f44f4f;">"WARNING: the irreducible is zero! We assume GF("</span>,<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">1</span>],<span style="color:#f44f4f;">")"</span>), |
| 70 |
<span style="color:#27aeae;font-weight:bold;">gf_setp</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">1</span>]), |
| 71 |
<span style="color:#8e44ad;">return</span>(<span style="font-weight:bold;">true</span>) |
| 72 |
) |
| 73 |
<span style="font-weight:bold;">else</span> |
| 74 |
( |
| 75 |
<span style="color:#8e44ad;">error</span>(<span style="color:#f44f4f;">"ERROR: you tried to extend with a non-zero constant!"</span>), |
| 76 |
<span style="color:#8e44ad;">return</span>(<span style="font-weight:bold;">false</span>) |
| 77 |
) |
| 78 |
) |
| 79 |
<span style="font-weight:bold;">else</span> |
| 80 |
( |
| 81 |
<span style="color:#27aeae;font-weight:bold;">dg</span>:<span style="color:#8e44ad;">hipow</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">2</span>],<span style="color:#27aeae;font-weight:bold;">x</span>), |
| 82 |
|
| 83 |
<span style="font-weight:bold;">if</span> <span style="color:#27aeae;font-weight:bold;">dg</span>=<span style="color:#f67400;">1</span> <span style="font-weight:bold;">then</span> |
| 84 |
<span style="color:#27aeae;font-weight:bold;">gf_setp</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">1</span>]), |
| 85 |
<span style="color:#27aeae;font-weight:bold;">gf_irr</span>:<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">2</span>], |
| 86 |
<span style="color:#27aeae;font-weight:bold;">gf_exp</span>:<span style="color:#27aeae;font-weight:bold;">dg</span>, |
| 87 |
<span style="color:#8e44ad;">return</span>(<span style="font-weight:bold;">true</span>) |
| 88 |
) |
| 89 |
) |
| 90 |
<span style="font-weight:bold;">else</span> |
| 91 |
( |
| 92 |
<span style="color:#27aeae;font-weight:bold;">gf_exp</span>:<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">2</span>], |
| 93 |
<span style="font-weight:bold;">if</span> <span style="color:#27aeae;font-weight:bold;">gf_exp</span>=<span style="color:#f67400;">1</span> <span style="font-weight:bold;">then</span> |
| 94 |
( |
| 95 |
<span style="color:#27aeae;font-weight:bold;">gf_setp</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">1</span>]), |
| 96 |
<span style="color:#27aeae;font-weight:bold;">gf_irr</span>:<span style="color:#8e44ad;">rat</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">3</span>]), |
| 97 |
<span style="color:#8e44ad;">return</span>(<span style="font-weight:bold;">true</span>) |
| 98 |
), |
| 99 |
<span style="color:#27aeae;font-weight:bold;">gf_irr</span>:<span style="color:#8e44ad;">rat</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">3</span>]) |
| 100 |
) |
| 101 |
), |
| 102 |
|
| 103 |
<span style="color:#27aeae;font-weight:bold;">gf_char</span>:<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">1</span>], |
| 104 |
<span style="color:#27aeae;font-weight:bold;">gf_one</span>:<span style="color:#8e44ad;">rat</span>(<span style="color:#f67400;">1</span>,<span style="color:#27aeae;font-weight:bold;">x</span>), |
| 105 |
<span style="color:#27aeae;font-weight:bold;">gf_order</span>:<span style="color:#27aeae;font-weight:bold;">gf_char</span>^<span style="color:#27aeae;font-weight:bold;">gf_exp</span><span style="color:#f67400;">-1</span>, |
| 106 |
|
| 107 |
<span style="color:#27aeae;font-weight:bold;">m</span>:<span style="color:#8e44ad;">makelist</span>(<span style="color:#8e44ad;">coeff</span>(<span style="color:#27aeae;font-weight:bold;">gf_irr</span>,<span style="color:#27aeae;font-weight:bold;">x</span>,<span style="color:#27aeae;font-weight:bold;">i</span>),<span style="color:#27aeae;font-weight:bold;">i</span>,<span style="color:#f67400;">0</span>,<span style="color:#27aeae;font-weight:bold;">gf_exp</span>), |
| 108 |
<span style="color:#27aeae;font-weight:bold;">gf_list</span>:[[<span style="color:#8e44ad;">first</span>(<span style="color:#27aeae;font-weight:bold;">m</span>),<span style="color:#f67400;">0</span>]],<span style="color:#27aeae;font-weight:bold;">j</span>:<span style="color:#f67400;">1</span>, |
| 109 |
<span style="font-weight:bold;">for</span> <span style="color:#27aeae;font-weight:bold;">i</span>:<span style="color:#f67400;">2</span> <span style="font-weight:bold;">thru</span> <span style="color:#27aeae;font-weight:bold;">gf_exp</span><span style="color:#f67400;">+1</span> <span style="font-weight:bold;">do</span> <span style="font-weight:bold;">if</span> <span style="color:#27aeae;font-weight:bold;">m</span>[<span style="color:#27aeae;font-weight:bold;">i</span>]=<span style="color:#f67400;">0</span> <span style="font-weight:bold;">then</span> <span style="color:#27aeae;font-weight:bold;">j</span>:<span style="color:#27aeae;font-weight:bold;">j</span><span style="color:#f67400;">+1</span> <span style="font-weight:bold;">else</span> ( <span style="color:#27aeae;font-weight:bold;">gf_list</span>:<span style="color:#8e44ad;">endcons</span>([<span style="color:#27aeae;font-weight:bold;">m</span>[<span style="color:#27aeae;font-weight:bold;">i</span>],<span style="color:#27aeae;font-weight:bold;">j</span>],<span style="color:#27aeae;font-weight:bold;">gf_list</span>), <span style="color:#27aeae;font-weight:bold;">j</span>:<span style="color:#f67400;">1</span> ), |
| 110 |
|
| 111 |
<span style="font-weight:bold;">if</span> <span style="font-weight:bold;">not</span>(<span style="color:#8e44ad;">primep</span>(<span style="color:#27aeae;font-weight:bold;">gf_char</span>)) <span style="font-weight:bold;">then</span> <span style="color:#8e44ad;">error</span>(<span style="color:#f44f4f;">"ERROR: Gf_Char must be a prime number."</span>) |
| 112 |
<span style="font-weight:bold;">else</span> |
| 113 |
<span style="color:#27aeae;font-style:italic;">modulus</span>:<span style="color:#27aeae;font-weight:bold;">gf_char</span>, |
| 114 |
<span style="font-weight:bold;">if</span> <span style="color:#27aeae;font-weight:bold;">GF_IRREDUCIBILITY_CHECK</span> <span style="font-weight:bold;">and</span> |
| 115 |
<span style="color:#8e44ad;">hipow</span>(<span style="color:#8e44ad;">args</span>(<span style="color:#8e44ad;">factor</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">3</span>]))[<span style="color:#f67400;">1</span>],<span style="color:#27aeae;font-weight:bold;">x</span>)#<span style="color:#8e44ad;">hipow</span>(<span style="color:#8e44ad;">rat</span>(<span style="color:#27aeae;font-weight:bold;">ars</span>[<span style="color:#f67400;">3</span>]),<span style="color:#27aeae;font-weight:bold;">x</span>) <span style="font-weight:bold;">then</span> |
| 116 |
<span style="color:#8e44ad;">error</span>(<span style="color:#f44f4f;">"ERROR: Polynomial is not irreducible"</span>), |
| 117 |
|
| 118 |
<span style="font-weight:bold;">if</span> <span style="font-weight:bold;">not</span>(<span style="color:#27aeae;font-weight:bold;">largefield</span>) <span style="font-weight:bold;">then</span> |
| 119 |
( |
| 120 |
<span style="color:#27aeae;font-weight:bold;">pg</span>:<span style="color:#27aeae;font-weight:bold;">mkpowers</span>(), |
| 121 |
<span style="color:#27aeae;font-weight:bold;">lg</span>:<span style="color:#27aeae;font-weight:bold;">mklogs</span>() |
| 122 |
) |
| 123 |
<span style="font-weight:bold;">else</span> |
| 124 |
( |
| 125 |
<span style="font-weight:bold;">if</span> <span style="color:#27aeae;font-weight:bold;">GF_VERBOSE</span> <span style="font-weight:bold;">then</span> |
| 126 |
<span style="color:#8e44ad;">print</span>(<span style="color:#f44f4f;">"finding a primitive element..."</span>), |
| 127 |
|
| 128 |
<span style="color:#27aeae;font-weight:bold;">gf_prim</span>:<span style="color:#8e44ad;">rat</span>(<span style="color:#27aeae;font-weight:bold;">gf_findprim</span>(),<span style="color:#27aeae;font-weight:bold;">x</span>), |
| 129 |
<span style="font-weight:bold;">if</span> <span style="color:#27aeae;font-weight:bold;">GF_VERBOSE</span> <span style="font-weight:bold;">then</span> |
| 130 |
<span style="color:#8e44ad;">print</span>(<span style="color:#f44f4f;">"...primitive element found."</span>) |
| 131 |
|
| 132 |
), |
| 133 |
<span style="color:#27aeae;font-style:italic;">modulus</span>:<span style="font-weight:bold;">false</span>, <span style="color:#7a7c7d;">/* it resets the modulus */</span> |
| 134 |
<span style="color:#8e44ad;">return</span>(<span style="font-weight:bold;">true</span>) |
| 135 |
|
| 136 |
)$ |
| 137 |
|
| 138 |
|
| 139 |
<span style="color:#7a7c7d;">/* Prints out information about the field */</span> |
| 140 |
<span style="color:#27aeae;font-weight:bold;">gf_info</span>():=<span style="color:#8e44ad;">block</span>( |
| 141 |
<span style="color:#8e44ad;">print</span>(<span style="color:#f44f4f;">"Prime gf_char value: "</span>,<span style="color:#27aeae;font-weight:bold;">gf_char</span>), |
| 142 |
<span style="color:#8e44ad;">print</span>(<span style="color:#f44f4f;">"Exponent: "</span>, <span style="color:#27aeae;font-weight:bold;">gf_exp</span>), |
| 143 |
<span style="color:#8e44ad;">print</span>(<span style="color:#f44f4f;">"Multiplicative order: "</span>,<span style="color:#27aeae;font-weight:bold;">gf_order</span>), |
| 144 |
<span style="color:#8e44ad;">print</span>(<span style="color:#f44f4f;">"Irreducible polynomial: "</span>,<span style="color:#27aeae;font-weight:bold;">gf_irr</span>), |
| 145 |
<span style="color:#8e44ad;">print</span>(<span style="color:#f44f4f;">"Primitive element: "</span>,<span style="color:#27aeae;font-weight:bold;">gf_prim</span>), |
| 146 |
<span style="font-weight:bold;">if</span> (<span style="color:#27aeae;font-weight:bold;">largefield</span>) <span style="font-weight:bold;">then</span> |
| 147 |
<span style="color:#8e44ad;">print</span>(<span style="color:#f44f4f;">"Largefield flag is true; powers and logarithms not computed."</span>) |
| 148 |
<span style="font-weight:bold;">else</span> |
| 149 |
<span style="color:#8e44ad;">print</span>(<span style="color:#f44f4f;">"Largefield flag is false; powers and logarithms computed."</span>), |
| 150 |
<span style="color:#8e44ad;">disp</span>() |
| 151 |
)$ |
| 152 |
</pre></body></html> |