Quelle chap14.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/doc/ref/chap14.html |
 |
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (ref) - Chapter 14: Integers</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap14" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chap17.html">17</a> <a href="chap18.html">18</a> <a href="chap19.html">19</a> <a href="chap20.html">20</a> <a href="chap21.html">21</a> <a href="chap22.html">22</a> <a href="chap23.html">23</a> <a href="chap24.html">24</a> <a href="chap25.html">25</a> <a href="chap26.html">26</a> <a href="chap27.html">27</a> <a href="chap28.html">28</a> <a href="chap29.html">29</a> <a href="chap30.html">30</a> <a href="chap31.html">31</a> <a href="chap32.html">32</a> <a href="chap33.html">33</a> <a href="chap34.html">34</a> <a href="chap35.html">35</a> <a href="chap36.html">36</a> <a href="chap37.html">37</a> <a href="chap38.html">38</a> <a href="chap39.html">39</a> <a href="chap40.html">40</a> <a href="chap41.html">41</a> <a href="chap42.html">42</a> <a href="chap43.html">43</a> <a href="chap44.html">44</a> <a href="chap45.html">45</a> <a href="chap46.html">46</a> <a href="chap47.html">47</a> <a href="chap48.html">48</a> <a href="chap49.html">49</a> <a href="chap50.html">50</a> <a href="chap51.html">51</a> <a href="chap52.html">52</a> <a href="chap53.html">53</a> <a href="chap54.html">54</a> <a href="chap55.html">55</a> <a href="chap56.html">56</a> <a href="chap57.html">57</a> <a href="chap58.html">58</a> <a href="chap59.html">59</a> <a href="chap60.html">60</a> <a href="chap61.html">61</a> <a href="chap62.html">62</a> <a href="chap63.html">63</a> <a href="chap64.html">64</a> <a href="chap65.html">65</a> <a href="chap66.html">66</a> <a href="chap67.html">67</a> <a href="chap68.html">68</a> <a href="chap69.html">69</a> <a href="chap70.html">70</a> <a href="chap71.html">71</a> <a href="chap72.html">72</a> <a href="chap73.html">73</a> <a href="chap74.html">74</a> <a href="chap75.html">75</a> <a href="chap76.html">76</a> <a href="chap77.html">77</a> <a href="chap78.html">78</a> <a href="chap79.html">79</a> <a href="chap80.html">80</a> <a href="chap81.html">81</a> <a href="chap82.html">82</a> <a href="chap83.html">83</a> <a href="chap84.html">84</a> <a href="chap85.html">85</a> <a href="chap86.html">86</a> <a href="chap87.html">87</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap13.html">[Previous Chapter]</a> <a href="chap15.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap14_mj.html">[MathJax on]</a></p>
<p><a id="X853DF11B80068ED5" name="X853DF11B80068ED5"></a></p>
<div class="ChapSects"><a href="chap14.html#X853DF11B80068ED5">14 <span class="Heading">Integers</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14.html#X838230CE810107A3">14.1 <span class="Heading">Integers: Global Variables</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X7E20D82B79DE5129">14.1-1 Integers</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X818683B17F8C97F3">14.1-2 IsIntegers</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14.html#X80CF510B8080C7CA">14.2 <span class="Heading">Elementary Operations for Integers</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X87AEADF07DC8303B">14.2-1 IsInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X82A854757DFA9C76">14.2-2 IsPosInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X87CA734380B5F68C">14.2-3 Int</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X87DD1EEE7EF18036">14.2-4 IsEvenInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X8621BA927CD12EFB">14.2-5 IsOddInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X782095927FB9F1DB">14.2-6 AbsInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X842614817FE48D62">14.2-7 SignInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X8197C4E882BAF14E">14.2-8 LogInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X83D9B5C87EEA2A77">14.2-9 RootInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X7F98A0CE7B9FD366">14.2-10 SmallestRootInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X83B998E486893FED">14.2-11 IsSquareInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X862D1BD786EFFDA9">14.2-12 ListOfDigits</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X8185784B7E228DEA">14.2-13 Random</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14.html#X7A9FD25D81D88D1B">14.3 <span class="Heading">Quotients and Remainders</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X849D0F807F697D35">14.3-1 QuoInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X795170A385AC8FEE">14.3-2 BestQuoInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X805ADD5A826D844D">14.3-3 RemInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X7A4FEFCA8128E3C3">14.3-4 GcdInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X8775930486BD0C5B">14.3-5 Gcdex</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X7B33143E78A8DDE3">14.3-6 LcmInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X79B466E984CD52D4">14.3-7 CoefficientsQadic</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X83124F86839DC7E6">14.3-8 CoefficientsMultiadic</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X84A1900E82902B5F">14.3-9 ChineseRem</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X7E404B1183DBC82A">14.3-10 PowerModInt</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14.html#X82005E587F0CB02A">14.4 <span class="Heading">Prime Integers and Factorization</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X86F5E4CD82FEB9F4">14.4-1 Primes</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X78FDA4437EDCA70C">14.4-2 IsPrimeInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X7CD977B17B4A7A4B">14.4-3 PrimalityProof</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X8443125D7FD6F2A6">14.4-4 IsPrimePowerInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X78744C367A94C69F">14.4-5 NextPrimeInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X819060E17E83728A">14.4-6 PrevPrimeInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X82C989DB84744B36">14.4-7 FactorsInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X80E7A5D381C64CC9">14.4-8 PrimeDivisors</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X786FF92C7C54BF97">14.4-9 PartialFactorization</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X803D431087B6FF28">14.4-10 PrintFactorsInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X82148B347E294C87">14.4-11 PrimePowersInt</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X809E0E1B83AF7695">14.4-12 DivisorsInt</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14.html#X864BF040862409FC">14.5 <span class="Heading">Residue Class Rings</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X87B1210B8581D5B2"><code>14.5-1 \mod</code></a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X79CE76AD82B3E2B2">14.5-2 ZmodnZ</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X838F36507D985EDA">14.5-3 ZmodnZObj</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X7D0107DD79753901">14.5-4 IsZmodnZObj</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14.html#X7904B6D681EBF091">14.6 <span class="Heading">Check Digits</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X82BABA8F868BD425">14.6-1 CheckDigitISBN</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X85F1A6A5870485B9">14.6-2 CheckDigitTestFunction</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14.html#X85361FAE8088C006">14.7 <span class="Heading">Random Sources</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X82E31A697E389F1D">14.7-1 IsRandomSource</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X821004F286282D49">14.7-2 Random</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X86FFFBC9790F9742">14.7-3 <span class="Heading">State and Reset for Random Sources</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X7AC96008820FAF1F">14.7-4 <span class="Heading">Kinds of Random Sources</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X7CB0B5BC82F8FD8F">14.7-5 RandomSource</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X8653AE447D94C1DC">14.7-6 <span class="Heading">Implementing new kinds of random sources</span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap14.html#X7A0311DF78DB4FD8">14.8 <span class="Heading">Bitfields</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X85C7BD9E7FCC6C10">14.8-1 MakeBitfields</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap14.html#X8068CE3781F4003C">14.8-2 BuildBitfields</a></span>
</div></div>
</div>
<h3>14 <span class="Heading">Integers</span></h3>
<p>One of the most fundamental datatypes in every programming language is the integer type. <strong class="pkg">GAP</strong> is no exception.</p>
<p><strong class="pkg">GAP</strong> integers are entered as a sequence of decimal digits optionally preceded by a <q><code class="code">+</code></q> sign for positive integers or a <q><code class="code">-</code></q> sign for negative integers. The size of integers in <strong class="pkg">GAP</strong> is only limited by the amount of available memory, so you can compute with integers having thousands of digits.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">-1234;</span>
-1234
<span class="GAPprompt">gap></span> <span class="GAPinput">123456789012345678901234567890123456789012345678901234567890;</span>
123456789012345678901234567890123456789012345678901234567890
</pre></div>
<p>Note that in a few places, only certain small integer values can be used. A <em>small integer</em> (also referred to as <em>immediate integer</em>) is an integer <span class="SimpleMath">n</span> satisfying <code class="code">INTOBJ_MIN</code> <span class="SimpleMath">≤ n ≤</span> <code class="code">INTOBJ_MAX</code>, where <code class="code">INTOBJ_MIN</code> and <code class="code">INTOBJ_MAX</code> equal either <span class="SimpleMath">-2^28</span> and <span class="SimpleMath">2^28-1</span> (on 32-bit systems) or <span class="SimpleMath">-2^60</span> and <span class="SimpleMath">2^60-1</span> (on 64-bit systems). For example, the elements of a range are restricted to small integers (see <a href="chap21.html#X79596BDE7CAF8491"><span class="RefLink">21.22</span></a>).</p>
<p>Many more functions that are mainly related to the prime residue group of integers modulo an integer are described in chapter <a href="chap15.html#X7FB995737B7ED8A2"><span class="RefLink">15</span></a>, and functions dealing with combinatorics can be found in chapter <a href="chap16.html#X7BDA99EE7CEADA7C"><span class="RefLink">16</span></a>.</p>
<p><a id="X838230CE810107A3" name="X838230CE810107A3"></a></p>
<h4>14.1 <span class="Heading">Integers: Global Variables</span></h4>
<p><a id="X7E20D82B79DE5129" name="X7E20D82B79DE5129"></a></p>
<h5>14.1-1 Integers</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Integers</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PositiveIntegers</code></td><td class="tdright">( global variable )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NonnegativeIntegers</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>These global variables represent the ring of integers and the semirings of positive and nonnegative integers, respectively.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size( Integers ); 2 in Integers;</span>
infinity
true
</pre></div>
<p><code class="func">Integers</code> is a subset of <code class="func">Rationals</code> (<a href="chap17.html#X7B6029D18570C08A"><span class="RefLink">17.1-1</span></a>), which is a subset of <code class="func">Cyclotomics</code> (<a href="chap18.html#X863D1E017BC9EB7F"><span class="RefLink">18.1-2</span></a>). See Chapter <a href="chap18.html#X7DFC03C187DE4841"><span class="RefLink">18</span></a> for arithmetic operations and comparison of integers.</p>
<p><a id="X818683B17F8C97F3" name="X818683B17F8C97F3"></a></p>
<h5>14.1-2 IsIntegers</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsIntegers</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPositiveIntegers</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsNonnegativeIntegers</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>are the defining categories for the domains <code class="func">Integers</code> (<a href="chap14.html#X7E20D82B79DE5129"><span class="RefLink">14.1-1</span></a>), <code class="func">PositiveIntegers</code> (<a href="chap14.html#X7E20D82B79DE5129"><span class="RefLink">14.1-1</span></a>), and <code class="func">NonnegativeIntegers</code> (<a href="chap14.html#X7E20D82B79DE5129"><span class="RefLink">14.1-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsIntegers( Integers ); IsIntegers( Rationals ); IsIntegers( 7 );</span>
true
false
false
</pre></div>
<p><a id="X80CF510B8080C7CA" name="X80CF510B8080C7CA"></a></p>
<h4>14.2 <span class="Heading">Elementary Operations for Integers</span></h4>
<p><a id="X87AEADF07DC8303B" name="X87AEADF07DC8303B"></a></p>
<h5>14.2-1 IsInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsInt</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Every rational integer lies in the category <code class="func">IsInt</code>, which is a subcategory of <code class="func">IsRat</code> (<a href="chap17.html#X7ED018F5794935F7"><span class="RefLink">17.2-1</span></a>).</p>
<p><a id="X82A854757DFA9C76" name="X82A854757DFA9C76"></a></p>
<h5>14.2-2 IsPosInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPosInt</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Every positive integer lies in the category <code class="func">IsPosInt</code>.</p>
<p><a id="X87CA734380B5F68C" name="X87CA734380B5F68C"></a></p>
<h5>14.2-3 Int</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Int</code>( <var class="Arg">elm</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><code class="func">Int</code> returns an integer <code class="code">int</code> whose meaning depends on the type of <var class="Arg">elm</var>. For example:</p>
<p>If <var class="Arg">elm</var> is a rational number (see Chapter <a href="chap17.html#X87003045878E74DF"><span class="RefLink">17</span></a>) then <code class="code">int</code> is the integer part of the quotient of numerator and denominator of <var class="Arg">elm</var> (see <code class="func">QuoInt</code> (<a href="chap14.html#X849D0F807F697D35"><span class="RefLink">14.3-1</span></a>)).</p>
<p>If <var class="Arg">elm</var> is an element of a finite prime field (see Chapter <a href="chap59.html#X7893ABF67A028802"><span class="RefLink">59</span></a>) then <code class="code">int</code> is the smallest nonnegative integer such that <code class="code"><var class="Arg">elm</var> = int * One( <var class="Arg">elm</var> )</code>.</p>
<p>If <var class="Arg">elm</var> is a string (see Chapter <a href="chap27.html#X7D28329B7EDB8F47"><span class="RefLink">27</span></a>) consisting entirely of decimal digits <code class="code">'0'</code>, <code class="code">'1'</code>, <span class="SimpleMath">...</span>, <code class="code">'9'</code>, and optionally a sign <code class="code">'-'</code> (at the first position), then <code class="code">int</code> is the integer described by this string. For all other strings, <code class="code">fail</code> is returned. See <code class="func">Int</code> (<a href="chap27.html#X7B6D118184F692A0"><span class="RefLink">27.9-1</span></a>).</p>
<p>The operation <code class="func">String</code> (<a href="chap27.html#X81FB5BE27903EC32"><span class="RefLink">27.7-6</span></a>) can be used to compute a string for rational integers, in fact for all cyclotomics.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Int( 4/3 ); Int( -2/3 );</span>
1
0
<span class="GAPprompt">gap></span> <span class="GAPinput">int:= Int( Z(5) ); int * One( Z(5) );</span>
2
Z(5)
<span class="GAPprompt">gap></span> <span class="GAPinput">Int( "12345" ); Int( "-27" ); Int( "-27/3" );</span>
12345
-27
fail
</pre></div>
<p><a id="X87DD1EEE7EF18036" name="X87DD1EEE7EF18036"></a></p>
<h5>14.2-4 IsEvenInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsEvenInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>tests if the integer <var class="Arg">n</var> is divisible by 2.</p>
<p><a id="X8621BA927CD12EFB" name="X8621BA927CD12EFB"></a></p>
<h5>14.2-5 IsOddInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsOddInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>tests if the integer <var class="Arg">n</var> is not divisible by 2.</p>
<p><a id="X782095927FB9F1DB" name="X782095927FB9F1DB"></a></p>
<h5>14.2-6 AbsInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AbsInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">AbsInt</code> returns the absolute value of the integer <var class="Arg">n</var>, i.e., <var class="Arg">n</var> if <var class="Arg">n</var> is positive, -<var class="Arg">n</var> if <var class="Arg">n</var> is negative and 0 if <var class="Arg">n</var> is 0.</p>
<p><code class="func">AbsInt</code> is a special case of the general operation <code class="func">EuclideanDegree</code> (<a href="chap56.html#X784234088350D4E4"><span class="RefLink">56.6-2</span></a>).</p>
<p>See also <code class="func">AbsoluteValue</code> (<a href="chap18.html#X81DD58BB81FB3426"><span class="RefLink">18.1-8</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AbsInt( 33 );</span>
33
<span class="GAPprompt">gap></span> <span class="GAPinput">AbsInt( -214378 );</span>
214378
<span class="GAPprompt">gap></span> <span class="GAPinput">AbsInt( 0 );</span>
0
</pre></div>
<p><a id="X842614817FE48D62" name="X842614817FE48D62"></a></p>
<h5>14.2-7 SignInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SignInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">SignInt</code> returns the sign of the integer <var class="Arg">n</var>, i.e., 1 if <var class="Arg">n</var> is positive, -1 if <var class="Arg">n</var> is negative and 0 if <var class="Arg">n</var> is 0.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SignInt( 33 );</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">SignInt( -214378 );</span>
-1
<span class="GAPprompt">gap></span> <span class="GAPinput">SignInt( 0 );</span>
0
</pre></div>
<p><a id="X8197C4E882BAF14E" name="X8197C4E882BAF14E"></a></p>
<h5>14.2-8 LogInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LogInt</code>( <var class="Arg">n</var>, <var class="Arg">base</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">LogInt</code> returns the integer part of the logarithm of the positive integer <var class="Arg">n</var> with respect to the positive integer <var class="Arg">base</var>, i.e., the largest positive integer <span class="SimpleMath">e</span> such that <span class="SimpleMath"><var class="Arg">base</var>^e ≤ <var class="Arg">n</var></span>. The function <code class="func">LogInt</code> will signal an error if either <var class="Arg">n</var> or <var class="Arg">base</var> is not positive.</p>
<p>For <var class="Arg">base</var> <span class="SimpleMath">= 2</span> this is very efficient because the internal binary representation of the integer is used.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">LogInt( 1030, 2 );</span>
10
<span class="GAPprompt">gap></span> <span class="GAPinput">2^10;</span>
1024
<span class="GAPprompt">gap></span> <span class="GAPinput">LogInt( 1, 10 );</span>
0
</pre></div>
<p><a id="X83D9B5C87EEA2A77" name="X83D9B5C87EEA2A77"></a></p>
<h5>14.2-9 RootInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RootInt</code>( <var class="Arg">n</var>[, <var class="Arg">k</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">RootInt</code> returns the integer part of the <var class="Arg">k</var>th root of the integer <var class="Arg">n</var>. If the optional integer argument <var class="Arg">k</var> is not given it defaults to 2, i.e., <code class="func">RootInt</code> returns the integer part of the square root in this case.</p>
<p>If <var class="Arg">n</var> is positive, <code class="func">RootInt</code> returns the largest positive integer <span class="SimpleMath">r</span> such that <span class="SimpleMath">r^<var class="Arg">k</var> ≤ <var class="Arg">n</var></span>. If <var class="Arg">n</var> is negative and <var class="Arg">k</var> is odd <code class="func">RootInt</code> returns <code class="code">-RootInt( -<var class="Arg">n</var>, <var class="Arg">k</var> )</code>. If <var class="Arg">n</var> is negative and <var class="Arg">k</var> is even <code class="func">RootInt</code> will cause an error. <code class="func">RootInt</code> will also cause an error if <var class="Arg">k</var> is 0 or negative.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RootInt( 361 );</span>
19
<span class="GAPprompt">gap></span> <span class="GAPinput">RootInt( 2 * 10^12 );</span>
1414213
<span class="GAPprompt">gap></span> <span class="GAPinput">RootInt( 17000, 5 );</span>
7
<span class="GAPprompt">gap></span> <span class="GAPinput">7^5;</span>
16807
</pre></div>
<p><a id="X7F98A0CE7B9FD366" name="X7F98A0CE7B9FD366"></a></p>
<h5>14.2-10 SmallestRootInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SmallestRootInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">SmallestRootInt</code> returns the smallest root of the integer <var class="Arg">n</var>.</p>
<p>The smallest root of an integer <var class="Arg">n</var> is the integer <span class="SimpleMath">r</span> of smallest absolute value for which a positive integer <span class="SimpleMath">k</span> exists such that <span class="SimpleMath"><var class="Arg">n</var> = r^k</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestRootInt( 2^30 );</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestRootInt( -(2^30) );</span>
-4
</pre></div>
<p>Note that <span class="SimpleMath">(-2)^30 = +(2^30)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestRootInt( 279936 );</span>
6
<span class="GAPprompt">gap></span> <span class="GAPinput">LogInt( 279936, 6 );</span>
7
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestRootInt( 1001 );</span>
1001
</pre></div>
<p><a id="X83B998E486893FED" name="X83B998E486893FED"></a></p>
<h5>14.2-11 IsSquareInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSquareInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IsSquareInt</code> tests whether the integer <var class="Arg">n</var> is the square of an integer or not. This test is much faster than the simpler <code class="code">RootInt</code><span class="SimpleMath">(n)^2=n</span> because it first tests whether <var class="Arg">n</var> is a square residue modulo some small integers.</p>
<p><a id="X862D1BD786EFFDA9" name="X862D1BD786EFFDA9"></a></p>
<h5>14.2-12 ListOfDigits</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ListOfDigits</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For a positive integer <var class="Arg">n</var> this function returns a list <var class="Arg">l</var>, consisting of the digits of <var class="Arg">n</var> in decimal representation.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ListOfDigits(3142);</span>
[ 3, 1, 4, 2 ]
</pre></div>
<p><a id="X8185784B7E228DEA" name="X8185784B7E228DEA"></a></p>
<h5>14.2-13 Random</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Random</code>( <var class="Arg">Integers</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><code class="func">Random</code> for integers returns pseudo random integers between <span class="SimpleMath">-10</span> and <span class="SimpleMath">10</span> distributed according to a binomial distribution. To generate uniformly distributed integers from a range, use the construction <code class="code">Random( [ <var class="Arg">low</var> .. <var class="Arg">high</var> ] )</code> (see <code class="func">Random</code> (<a href="chap30.html#X7FF906E57D6936F8"><span class="RefLink">30.7-1</span></a>)).</p>
<p><a id="X7A9FD25D81D88D1B" name="X7A9FD25D81D88D1B"></a></p>
<h4>14.3 <span class="Heading">Quotients and Remainders</span></h4>
<p><a id="X849D0F807F697D35" name="X849D0F807F697D35"></a></p>
<h5>14.3-1 QuoInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ QuoInt</code>( <var class="Arg">n</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">QuoInt</code> returns the integer part of the quotient of its integer operands.</p>
<p>If <var class="Arg">n</var> and <var class="Arg">m</var> are positive, <code class="func">QuoInt</code> returns the largest positive integer <span class="SimpleMath">q</span> such that <span class="SimpleMath">q * <var class="Arg">m</var> ≤ <var class="Arg">n</var></span>. If <var class="Arg">n</var> or <var class="Arg">m</var> or both are negative the absolute value of the integer part of the quotient is the quotient of the absolute values of <var class="Arg">n</var> and <var class="Arg">m</var>, and the sign of it is the product of the signs of <var class="Arg">n</var> and <var class="Arg">m</var>.</p>
<p><code class="func">QuoInt</code> is used in a method for the general operation <code class="func">EuclideanQuotient</code> (<a href="chap56.html#X7A93FA788318B147"><span class="RefLink">56.6-3</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">QuoInt(5,3); QuoInt(-5,3); QuoInt(5,-3); QuoInt(-5,-3);</span>
1
-1
-1
1
</pre></div>
<p><a id="X795170A385AC8FEE" name="X795170A385AC8FEE"></a></p>
<h5>14.3-2 BestQuoInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BestQuoInt</code>( <var class="Arg">n</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">BestQuoInt</code> returns the best quotient <span class="SimpleMath">q</span> of the integers <var class="Arg">n</var> and <var class="Arg">m</var>. This is the quotient such that <span class="SimpleMath"><var class="Arg">n</var>-q*<var class="Arg">m</var></span> has minimal absolute value. If there are two quotients whose remainders have the same absolute value, then the quotient with the smaller absolute value is chosen.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">BestQuoInt( 5, 3 ); BestQuoInt( -5, 3 );</span>
2
-2
</pre></div>
<p><a id="X805ADD5A826D844D" name="X805ADD5A826D844D"></a></p>
<h5>14.3-3 RemInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RemInt</code>( <var class="Arg">n</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">RemInt</code> returns the remainder of its two integer operands.</p>
<p>If <var class="Arg">m</var> is not equal to zero, <code class="func">RemInt</code> returns <code class="code"><var class="Arg">n</var> - <var class="Arg">m</var> * QuoInt( <var class="Arg">n</var>, <var class="Arg">m</var> )</code>. Note that the rules given for <code class="func">QuoInt</code> (<a href="chap14.html#X849D0F807F697D35"><span class="RefLink">14.3-1</span></a>) imply that the return value of <code class="func">RemInt</code> has the same sign as <var class="Arg">n</var> and its absolute value is strictly less than the absolute value of <var class="Arg">m</var>. Note also that the return value equals <code class="code"><var class="Arg">n</var> mod <var class="Arg">m</var></code> when both <var class="Arg">n</var> and <var class="Arg">m</var> are nonnegative. Dividing by <code class="code">0</code> signals an error.</p>
<p><code class="func">RemInt</code> is used in a method for the general operation <code class="func">EuclideanRemainder</code> (<a href="chap56.html#X7B5E9639865E91BA"><span class="RefLink">56.6-4</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RemInt(5,3); RemInt(-5,3); RemInt(5,-3); RemInt(-5,-3);</span>
2
-2
2
-2
</pre></div>
<p><a id="X7A4FEFCA8128E3C3" name="X7A4FEFCA8128E3C3"></a></p>
<h5>14.3-4 GcdInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GcdInt</code>( <var class="Arg">m</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">GcdInt</code> returns the greatest common divisor of its two integer operands <var class="Arg">m</var> and <var class="Arg">n</var>, i.e., the greatest integer that divides both <var class="Arg">m</var> and <var class="Arg">n</var>. The greatest common divisor is never negative, even if the arguments are. We define <code class="code">GcdInt( <var class="Arg">m</var>, 0 ) = GcdInt( 0, <var class="Arg">m</var> ) = AbsInt( <var class="Arg">m</var> )</code> and <code class="code">GcdInt( 0, 0 ) = 0</code>.</p>
<p><code class="func">GcdInt</code> is a method used by the general function <code class="func">Gcd</code> (<a href="chap56.html#X7DE207718456F98F"><span class="RefLink">56.7-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GcdInt( 123, 66 );</span>
3
</pre></div>
<p><a id="X8775930486BD0C5B" name="X8775930486BD0C5B"></a></p>
<h5>14.3-5 Gcdex</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Gcdex</code>( <var class="Arg">m</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns a record <code class="code">g</code> describing the extended greatest common divisor of <var class="Arg">m</var> and <var class="Arg">n</var>. The component <code class="code">gcd</code> is this gcd, the components <code class="code">coeff1</code> and <code class="code">coeff2</code> are integer cofactors such that <code class="code">g.gcd = g.coeff1 * <var class="Arg">m</var> + g.coeff2 * <var class="Arg">n</var></code>, and the components <code class="code">coeff3</code> and <code class="code">coeff4</code> are integer cofactors such that <code class="code">0 = g.coeff3 * <var class="Arg">m</var> + g.coeff4 * <var class="Arg">n</var></code>.</p>
<p>If <var class="Arg">m</var> and <var class="Arg">n</var> both are nonzero, <code class="code">AbsInt( g.coeff1 )</code> is less than or equal to <code class="code">AbsInt(<var class="Arg">n</var>) / (2 * g.gcd)</code>, and <code class="code">AbsInt( g.coeff2 )</code> is less than or equal to <code class="code">AbsInt(<var class="Arg">m</var>) / (2 * g.gcd)</code>.</p>
<p>If <var class="Arg">m</var> or <var class="Arg">n</var> or both are zero <code class="code">coeff3</code> is <code class="code">-<var class="Arg">n</var> / g.gcd</code> and <code class="code">coeff4</code> is <code class="code"><var class="Arg">m</var> / g.gcd</code>.</p>
<p>The coefficients always form a unimodular matrix, i.e., the determinant <code class="code">g.coeff1 * g.coeff4 - g.coeff3 * g.coeff2</code> is <span class="SimpleMath">1</span> or <span class="SimpleMath">-1</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Gcdex( 123, 66 );</span>
rec( coeff1 := 7, coeff2 := -13, coeff3 := -22, coeff4 := 41,
gcd := 3 )
</pre></div>
<p>This means <span class="SimpleMath">3 = 7 * 123 - 13 * 66</span>, <span class="SimpleMath">0 = -22 * 123 + 41 * 66</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Gcdex( 0, -3 );</span>
rec( coeff1 := 0, coeff2 := -1, coeff3 := 1, coeff4 := 0, gcd := 3 )
<span class="GAPprompt">gap></span> <span class="GAPinput">Gcdex( 0, 0 );</span>
rec( coeff1 := 1, coeff2 := 0, coeff3 := 0, coeff4 := 1, gcd := 0 )
</pre></div>
<p><code class="func">GcdRepresentation</code> (<a href="chap56.html#X7ABB91EF838075EF"><span class="RefLink">56.7-3</span></a>) provides similar functionality over arbitrary Euclidean rings.</p>
<p><a id="X7B33143E78A8DDE3" name="X7B33143E78A8DDE3"></a></p>
<h5>14.3-6 LcmInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LcmInt</code>( <var class="Arg">m</var>, <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the least common multiple of the integers <var class="Arg">m</var> and <var class="Arg">n</var>.</p>
<p><code class="func">LcmInt</code> is a method used by the general operation <code class="func">Lcm</code> (<a href="chap56.html#X7ABA92057DD6C7AF"><span class="RefLink">56.7-6</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">LcmInt( 123, 66 );</span>
2706
</pre></div>
<p><a id="X79B466E984CD52D4" name="X79B466E984CD52D4"></a></p>
<h5>14.3-7 CoefficientsQadic</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CoefficientsQadic</code>( <var class="Arg">i</var>, <var class="Arg">q</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the <var class="Arg">q</var>-adic representation of the integer <var class="Arg">i</var> as a list <span class="SimpleMath">l</span> of coefficients satisfying the equality <span class="SimpleMath"><var class="Arg">i</var> = ∑_{j = 0} <var class="Arg">q</var>^j ⋅ l[j+1]</span> for an integer <span class="SimpleMath"><var class="Arg">q</var> > 1</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:=CoefficientsQadic(462,3);</span>
[ 0, 1, 0, 2, 2, 1 ]
</pre></div>
<p><a id="X83124F86839DC7E6" name="X83124F86839DC7E6"></a></p>
<h5>14.3-8 CoefficientsMultiadic</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CoefficientsMultiadic</code>( <var class="Arg">ints</var>, <var class="Arg">int</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns the multiadic expansion of the integer <var class="Arg">int</var> modulo the integers given in <var class="Arg">ints</var> (in ascending order). It returns a list of coefficients in the <em>reverse</em> order to that in <var class="Arg">ints</var>.</p>
<p><a id="X84A1900E82902B5F" name="X84A1900E82902B5F"></a></p>
<h5>14.3-9 ChineseRem</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ChineseRem</code>( <var class="Arg">moduli</var>, <var class="Arg">residues</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">ChineseRem</code> returns the combination of the <var class="Arg">residues</var> modulo the <var class="Arg">moduli</var>, i.e., the unique integer <code class="code">c</code> from <code class="code">[0..Lcm(<var class="Arg">moduli</var>)-1]</code> such that <code class="code">c = <var class="Arg">residues</var>[i]</code> modulo <code class="code"><var class="Arg">moduli</var>[i]</code> for all <code class="code">i</code>, if it exists. If no such combination exists <code class="func">ChineseRem</code> signals an error.</p>
<p>Such a combination does exist if and only if <code class="code"><var class="Arg">residues</var>[i] = <var class="Arg">residues</var>[k] mod Gcd( <var class="Arg">moduli</var>[i], <var class="Arg">moduli</var>[k] )</code> for every pair <code class="code">i</code>, <code class="code">k</code>. Note that this implies that such a combination exists if the moduli are pairwise relatively prime. This is called the Chinese remainder theorem.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ChineseRem( [ 2, 3, 5, 7 ], [ 1, 2, 3, 4 ] );</span>
53
<span class="GAPprompt">gap></span> <span class="GAPinput">ChineseRem( [ 6, 10, 14 ], [ 1, 3, 5 ] );</span>
103
</pre></div>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ChineseRem( [ 6, 10, 14 ], [ 1, 2, 3 ] );</span>
Error, the residues must be equal modulo 2 called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
<span class="GAPbrkprompt">brk></span> <span class="GAPinput">gap></span>
</pre></div>
<p><a id="X7E404B1183DBC82A" name="X7E404B1183DBC82A"></a></p>
<h5>14.3-10 PowerModInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PowerModInt</code>( <var class="Arg">r</var>, <var class="Arg">e</var>, <var class="Arg">m</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns <span class="SimpleMath"><var class="Arg">r</var>^<var class="Arg">e</var> mod <var class="Arg">m</var></span> for integers <var class="Arg">r</var>, <var class="Arg">e</var> and <var class="Arg">m</var>.</p>
<p>Note that <code class="func">PowerModInt</code> can reduce intermediate results and thus will generally be faster than using <var class="Arg">r</var><code class="code">^</code><var class="Arg">e</var><code class="code"> mod </code><var class="Arg">m</var>, which would compute <span class="SimpleMath"><var class="Arg">r</var>^<var class="Arg">e</var></span> first and reduces the result afterwards.</p>
<p><code class="func">PowerModInt</code> is a method for the general operation <code class="func">PowerMod</code> (<a href="chap56.html#X805A35D684B7A952"><span class="RefLink">56.7-9</span></a>).</p>
<p><a id="X82005E587F0CB02A" name="X82005E587F0CB02A"></a></p>
<h4>14.4 <span class="Heading">Prime Integers and Factorization</span></h4>
<p><a id="X86F5E4CD82FEB9F4" name="X86F5E4CD82FEB9F4"></a></p>
<h5>14.4-1 Primes</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Primes</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p><code class="func">Primes</code> is a strictly sorted list of the 168 primes less than 1000.</p>
<p>This is used in <code class="func">IsPrimeInt</code> (<a href="chap14.html#X78FDA4437EDCA70C"><span class="RefLink">14.4-2</span></a>) and <code class="func">FactorsInt</code> (<a href="chap14.html#X82C989DB84744B36"><span class="RefLink">14.4-7</span></a>) to cast out small primes quickly.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Primes[1];</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">Primes[100];</span>
541
</pre></div>
<p><a id="X78FDA4437EDCA70C" name="X78FDA4437EDCA70C"></a></p>
<h5>14.4-2 IsPrimeInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPrimeInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsProbablyPrimeInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IsPrimeInt</code> returns <code class="keyw">false</code> if it can prove that the integer <var class="Arg">n</var> is composite and <code class="keyw">true</code> otherwise. By convention <code class="code">IsPrimeInt(0) = IsPrimeInt(1) = false</code> and we define <code class="code">IsPrimeInt(-</code><var class="Arg">n</var><code class="code">) = IsPrimeInt(</code><var class="Arg">n</var><code class="code">)</code>.</p>
<p><code class="func">IsPrimeInt</code> will return <code class="keyw">true</code> for every prime <var class="Arg">n</var>. <code class="func">IsPrimeInt</code> will return <code class="keyw">false</code> for all composite <var class="Arg">n</var> <span class="SimpleMath">< 10^18</span> and for all composite <var class="Arg">n</var> that have a factor <span class="SimpleMath">p < 1000</span>. So for integers <var class="Arg">n</var> <span class="SimpleMath">< 10^18</span>, <code class="func">IsPrimeInt</code> is a proper primality test. It is conceivable that <code class="func">IsPrimeInt</code> may return <code class="keyw">true</code> for some composite <var class="Arg">n</var> <span class="SimpleMath">> 10^18</span>, but no such <var class="Arg">n</var> is currently known. So for integers <var class="Arg">n</var> <span class="SimpleMath">> 10^18</span>, <code class="func">IsPrimeInt</code> is a probable-primality test. <code class="func">IsPrimeInt</code> will issue a warning when its argument is probably prime but not a proven prime. (The function <code class="func">IsProbablyPrimeInt</code> will do a similar calculation but not issue a warning.) The warning can be switched off by <code class="code">SetInfoLevel( InfoPrimeInt, 0 );</code>, the default level is <span class="SimpleMath">1</span> (also see <code class="func">SetInfoLevel</code> (<a href="chap7.html#X7A43B9E68765EE9E"><span class="RefLink">7.4-3</span></a>) ).</p>
<p>If composites that fool <code class="func">IsPrimeInt</code> do exist, they would be extremely rare, and finding one by pure chance might be less likely than finding a bug in <strong class="pkg">GAP</strong>. We would appreciate being informed about any example of a composite number <var class="Arg">n</var> for which <code class="func">IsPrimeInt</code> returns <code class="keyw">true</code>.</p>
<p><code class="func">IsPrimeInt</code> is a deterministic algorithm, i.e., the computations involve no random numbers, and repeated calls will always return the same result. <code class="func">IsPrimeInt</code> first does trial divisions by the primes less than 1000. Then it tests that <var class="Arg">n</var> is a strong pseudoprime w.r.t. the base 2. Finally it tests whether <var class="Arg">n</var> is a Lucas pseudoprime w.r.t. the smallest quadratic nonresidue of <var class="Arg">n</var>. A better description can be found in the comment in the library file <code class="file">primality.gi</code>.</p>
<p>The time taken by <code class="func">IsPrimeInt</code> is approximately proportional to the third power of the number of digits of <var class="Arg">n</var>. Testing numbers with several hundreds digits is quite feasible.</p>
<p><code class="func">IsPrimeInt</code> is a method for the general operation <code class="func">IsPrime</code> (<a href="chap56.html#X7AA107AE7F79C6D8"><span class="RefLink">56.5-8</span></a>).</p>
<p>Remark: In future versions of <strong class="pkg">GAP</strong> we hope to change the definition of <code class="func">IsPrimeInt</code> to return <code class="keyw">true</code> only for proven primes (currently, we lack a sufficiently good primality proving function). In applications, use explicitly <code class="func">IsPrimeInt</code> or <code class="func">IsProbablyPrimeInt</code> with this change in mind.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimeInt( 2^31 - 1 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimeInt( 10^42 + 1 );</span>
false
</pre></div>
<p><a id="X7CD977B17B4A7A4B" name="X7CD977B17B4A7A4B"></a></p>
<h5>14.4-3 PrimalityProof</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PrimalityProof</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Construct a machine verifiable proof of the primality of (the probable prime) <var class="Arg">n</var>, following the ideas of <a href="chapBib.html#biBBLS1975">[BLS75]</a>. The proof consists of various Fermat and Lucas pseudoprimality tests, which taken as a whole prove the primality. The proof is represented as a list of witnesses of two kinds. The first kind, <code class="code">[ "F", divisor, base ]</code>, indicates a successful Fermat pseudoprimality test, where <var class="Arg">n</var> is a strong pseudoprime at <code class="keyw">base</code> with order not divisible by <span class="SimpleMath">(<var class="Arg">n</var>-1)/divisor</span>. The second kind, <code class="code">[ "L", divisor, discriminant, P ]</code> indicates a successful Lucas pseudoprimality test, for a quadratic form of given <code class="keyw">discriminant</code> and middle term <code class="keyw">P</code> with an extra check at <span class="SimpleMath">(<var class="Arg">n</var>+1)/divisor</span>.</p>
<p><a id="X8443125D7FD6F2A6" name="X8443125D7FD6F2A6"></a></p>
<h5>14.4-4 IsPrimePowerInt</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPrimePowerInt</code>( <var class="Arg">n</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><code class="func">IsPrimePowerInt</code> returns <code class="keyw">true</code> if the integer <var class="Arg">n</var> is a prime power and <code class="keyw">false</code> otherwise.</p>
<p>An integer <span class="SimpleMath">n</span> is a <em>prime power</em> if there exists a prime <span class="SimpleMath">p</span> and a positive integer <span class="SimpleMath">i</span> such that <span class="SimpleMath">p^i = n</span>. If <span class="SimpleMath">n</span> is negative the condition is that there must exist a negative prime <span class="SimpleMath">p</span> and an odd positive integer <span class="SimpleMath">i</span> such that <span class="SimpleMath">p^i = n</span>. The integers 1 and -1 are not prime powers.</p>
<p>Note that <code class="func">IsPrimePowerInt</code> uses <code class="func">SmallestRootInt</code> (<a href="chap14.html#X7F98A0CE7B9FD366"><span class="RefLink">14.2-10</span></a>) and a probable-primality test (see <code class="func">IsPrimeInt</code> (<a href="chap14.html#X78FDA4437EDCA70C"><span class="RefLink">14.4-2</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimePowerInt( 31^5 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimePowerInt( 2^31-1 ); # 2^31-1 is actually a prime</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPrimePowerInt( 2^63-1 );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">Filtered( [-10..10], IsPrimePowerInt );</ | |
