Debian Codegraph @

help/pt_BR/html/ch11s07.html

raw
1 <html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Teoria dos números</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot"><link rel="home" href="index.html" title="Manual do Genius"><link rel="up" href="ch11.html" title="Chapter 11. List of GEL functions"><link rel="prev" href="ch11s06.html" title="Trigonometria"><link rel="next" href="ch11s08.html" title="Manipulação de matrizes"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Teoria dos números</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch11s06.html">Prev</a> </td><th width="60%" align="center">Chapter 11. List of GEL functions</th><td width="20%" align="right"> <a accesskey="n" href="ch11s08.html">Next</a></td></tr></table><hr></div><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="genius-gel-function-list-number-theory"></a>Teoria dos números</h2></div></div></div><div class="variablelist"><dl class="variablelist"><dt><span lang="en" class="term"><a name="gel-function-AreRelativelyPrime"></a>AreRelativelyPrime</span></dt><dd><pre lang="en" class="synopsis">AreRelativelyPrime (a,b)</pre><p lang="en">
2 Are the real integers <code class="varname">a</code> and <code class="varname">b</code> relatively prime?
3 Returns <code class="constant">true</code> or <code class="constant">false</code>.
4 </p><p lang="en">
5 See
6 <a class="ulink" href="https://en.wikipedia.org/wiki/Coprime_integers" target="_top">Wikipedia</a> or
7 <a class="ulink" href="http://planetmath.org/RelativelyPrime" target="_top">Planetmath</a> or
8 <a class="ulink" href="http://mathworld.wolfram.com/RelativelyPrime.html" target="_top">Mathworld</a> for more information.
9 </p></dd><dt><span lang="en" class="term"><a name="gel-function-BernoulliNumber"></a>BernoulliNumber</span></dt><dd><pre lang="en" class="synopsis">BernoulliNumber (n)</pre><p lang="en">Return the <code class="varname">n</code>th Bernoulli number.</p><p lang="en">
10 See
11 <a class="ulink" href="https://en.wikipedia.org/wiki/Bernoulli_number" target="_top">Wikipedia</a> or
12 <a class="ulink" href="http://mathworld.wolfram.com/BernoulliNumber.html" target="_top">Mathworld</a> for more information.
13 </p></dd><dt><span lang="en" class="term"><a name="gel-function-ChineseRemainder"></a>ChineseRemainder</span></dt><dd><pre lang="en" class="synopsis">ChineseRemainder (a,m)</pre><p lang="en">Aliases: <code class="function">CRT</code></p><p lang="en">Find the <code class="varname">x</code> that solves the system given by
14 the vector <code class="varname">a</code> and modulo the elements of
15 <code class="varname">m</code>, using the Chinese Remainder Theorem.
16 </p><p lang="en">
17 See
18 <a class="ulink" href="https://en.wikipedia.org/wiki/Chinese_remainder_theorem" target="_top">Wikipedia</a> or
19 <a class="ulink" href="http://planetmath.org/ChineseRemainderTheorem" target="_top">Planetmath</a> or
20 <a class="ulink" href="http://mathworld.wolfram.com/ChineseRemainderTheorem.html" target="_top">Mathworld</a> for more information.
21 </p></dd><dt><span lang="en" class="term"><a name="gel-function-CombineFactorizations"></a>CombineFactorizations</span></dt><dd><pre lang="en" class="synopsis">CombineFactorizations (a,b)</pre><p lang="en">Given two factorizations, give the factorization of the
22 product.</p><p lang="en">See <a class="link" href="ch11s07.html#gel-function-Factorize">Factorize</a>.</p></dd><dt><span lang="en" class="term"><a name="gel-function-ConvertFromBase"></a>ConvertFromBase</span></dt><dd><pre lang="en" class="synopsis">ConvertFromBase (v,b)</pre><p lang="en">Convert a vector of values indicating powers of b to a number.</p></dd><dt><span lang="en" class="term"><a name="gel-function-ConvertToBase"></a>ConvertToBase</span></dt><dd><pre lang="en" class="synopsis">ConvertToBase (n,b)</pre><p lang="en">Convert a number to a vector of powers for elements in base <code class="varname">b</code>.</p></dd><dt><span lang="en" class="term"><a name="gel-function-DiscreteLog"></a>DiscreteLog</span></dt><dd><pre lang="en" class="synopsis">DiscreteLog (n,b,q)</pre><p lang="en">Find discrete log of <code class="varname">n</code> base <code class="varname">b</code> in
23 F<sub>q</sub>, the finite field of order <code class="varname">q</code>, where <code class="varname">q</code>
24 is a prime, using the Silver-Pohlig-Hellman algorithm.</p><p lang="en">
25 See
26 <a class="ulink" href="https://en.wikipedia.org/wiki/Discrete_logarithm" target="_top">Wikipedia</a>,
27 <a class="ulink" href="http://planetmath.org/DiscreteLogarithm" target="_top">Planetmath</a>, or
28 <a class="ulink" href="http://mathworld.wolfram.com/DiscreteLogarithm.html" target="_top">Mathworld</a> for more information.
29 </p></dd><dt><span lang="en" class="term"><a name="gel-function-Divides"></a>Divides</span></dt><dd><pre lang="en" class="synopsis">Divides (m,n)</pre><p lang="en">Checks divisibility (if <code class="varname">m</code> divides <code class="varname">n</code>).</p></dd><dt><span lang="en" class="term"><a name="gel-function-EulerPhi"></a>EulerPhi</span></dt><dd><pre lang="en" class="synopsis">EulerPhi (n)</pre><p lang="en">
30 Compute the Euler phi function for <code class="varname">n</code>, that is
31 the number of integers between 1 and <code class="varname">n</code>
32 relatively prime to <code class="varname">n</code>.
33 </p><p lang="en">
34 See
35 <a class="ulink" href="https://en.wikipedia.org/wiki/Euler_phi" target="_top">Wikipedia</a>,
36 <a class="ulink" href="http://planetmath.org/EulerPhifunction" target="_top">Planetmath</a>, or
37 <a class="ulink" href="http://mathworld.wolfram.com/TotientFunction.html" target="_top">Mathworld</a> for more information.
38 </p></dd><dt><span lang="en" class="term"><a name="gel-function-ExactDivision"></a>ExactDivision</span></dt><dd><pre lang="en" class="synopsis">ExactDivision (n,d)</pre><p lang="en">
39 Return <strong class="userinput"><code>n/d</code></strong> but only if <code class="varname">d</code>
40 divides <code class="varname">n</code>. If <code class="varname">d</code>
41 does not divide <code class="varname">n</code> then this function returns
42 garbage. This is a lot faster for very large numbers
43 than the operation <strong class="userinput"><code>n/d</code></strong>, but it is only
44 useful if you know that the division is exact.
45 </p></dd><dt><span lang="en" class="term"><a name="gel-function-Factorize"></a>Factorize</span></dt><dd><pre lang="en" class="synopsis">Factorize (n)</pre><p lang="en">
46 Return factorization of a number as a matrix. The first
47 row is the primes in the factorization (including 1) and the
48 second row are the powers. So for example:
49 </p><pre lang="en" class="screen"><code class="prompt">genius&gt;</code> <strong class="userinput"><code>Factorize(11*11*13)</code></strong>
50 =
51 [1 11 13
52 1 2 1]</pre><p lang="en">
53 </p><p lang="en">
54 See
55 <a class="ulink" href="https://en.wikipedia.org/wiki/Factorization" target="_top">Wikipedia</a> for more information.
56 </p></dd><dt><span lang="en" class="term"><a name="gel-function-Factors"></a>Factors</span></dt><dd><pre lang="en" class="synopsis">Factors (n)</pre><p lang="en">
57 Return all factors of <code class="varname">n</code> in a vector. This
58 includes all the non-prime factors as well. It includes 1 and the
59 number itself. So to print all the perfect numbers
60 (those that are sums of their factors) up to the number 1000 you
61 could do (this is clearly very inefficient)
62 </p><pre lang="en" class="programlisting">for n=1 to 1000 do (
63 if MatrixSum (Factors(n)) == 2*n then
64 print(n)
65 )
66 </pre><p lang="en">
67 </p></dd><dt><span lang="en" class="term"><a name="gel-function-FermatFactorization"></a>FermatFactorization</span></dt><dd><pre lang="en" class="synopsis">FermatFactorization (n,tries)</pre><p lang="en">
68 Attempt Fermat factorization of <code class="varname">n</code> into
69 <strong class="userinput"><code>(t-s)*(t+s)</code></strong>, returns <code class="varname">t</code>
70 and <code class="varname">s</code> as a vector if possible, <code class="constant">null</code> otherwise.
71 <code class="varname">tries</code> specifies the number of tries before
72 giving up.
73 </p><p lang="en">
74 This is a fairly good factorization if your number is the product
75 of two factors that are very close to each other.
76 </p><p lang="en">
77 See
78 <a class="ulink" href="https://en.wikipedia.org/wiki/Fermat_factorization" target="_top">Wikipedia</a> for more information.
79 </p></dd><dt><span lang="en" class="term"><a name="gel-function-FindPrimitiveElementMod"></a>FindPrimitiveElementMod</span></dt><dd><pre lang="en" class="synopsis">FindPrimitiveElementMod (q)</pre><p lang="en">Find the first primitive element in F<sub>q</sub>, the finite
80 group of order <code class="varname">q</code>. Of course <code class="varname">q</code> must be a prime.</p></dd><dt><span lang="en" class="term"><a name="gel-function-FindRandomPrimitiveElementMod"></a>FindRandomPrimitiveElementMod</span></dt><dd><pre lang="en" class="synopsis">FindRandomPrimitiveElementMod (q)</pre><p lang="en">Find a random primitive element in F<sub>q</sub>, the finite
81 group of order <code class="varname">q</code> (q must be a prime).</p></dd><dt><span lang="en" class="term"><a name="gel-function-IndexCalculus"></a>IndexCalculus</span></dt><dd><pre lang="en" class="synopsis">IndexCalculus (n,b,q,S)</pre><p lang="en">Compute discrete log base <code class="varname">b</code> of n in F<sub>q</sub>, the finite
82 group of order <code class="varname">q</code> (<code class="varname">q</code> a prime), using the
83 factor base <code class="varname">S</code>. <code class="varname">S</code> should be a column of
84 primes possibly with second column precalculated by
85 <a class="link" href="ch11s07.html#gel-function-IndexCalculusPrecalculation"><code class="function">IndexCalculusPrecalculation</code></a>.</p></dd><dt><span lang="en" class="term"><a name="gel-function-IndexCalculusPrecalculation"></a>IndexCalculusPrecalculation</span></dt><dd><pre lang="en" class="synopsis">IndexCalculusPrecalculation (b,q,S)</pre><p lang="en">Run the precalculation step of
86 <a class="link" href="ch11s07.html#gel-function-IndexCalculus"><code class="function">IndexCalculus</code></a> for logarithms base <code class="varname">b</code> in
87 F<sub>q</sub>, the finite group of order <code class="varname">q</code>
88 (<code class="varname">q</code> a prime), for the factor base <code class="varname">S</code> (where
89 <code class="varname">S</code> is a column vector of primes). The logs will be
90 precalculated and returned in the second column.</p></dd><dt><span lang="en" class="term"><a name="gel-function-IsEven"></a>IsEven</span></dt><dd><pre lang="en" class="synopsis">IsEven (n)</pre><p lang="en">Tests if an integer is even.</p></dd><dt><span lang="en" class="term"><a name="gel-function-IsMersennePrimeExponent"></a>IsMersennePrimeExponent</span></dt><dd><pre lang="en" class="synopsis">IsMersennePrimeExponent (p)</pre><p lang="en">
91 Tests if a positive integer <code class="varname">p</code> is a
92 Mersenne prime exponent. That is if
93 2<sup>p</sup>-1 is a prime. It does this
94 by looking it up in a table of known values, which is relatively
95 short.
96 See also
97 <a class="link" href="ch11s07.html#gel-function-MersennePrimeExponents">MersennePrimeExponents</a>
98 and
99 <a class="link" href="ch11s07.html#gel-function-LucasLehmer">LucasLehmer</a>.
100 </p><p lang="en">
101 See
102 <a class="ulink" href="https://en.wikipedia.org/wiki/Mersenne_prime" target="_top">Wikipedia</a>,
103 <a class="ulink" href="http://planetmath.org/MersenneNumbers" target="_top">Planetmath</a>,
104 <a class="ulink" href="http://mathworld.wolfram.com/MersennePrime.html" target="_top">Mathworld</a> or
105 <a class="ulink" href="http://www.mersenne.org/" target="_top">GIMPS</a>
106 for more information.
107 </p></dd><dt><span lang="en" class="term"><a name="gel-function-IsNthPower"></a>IsNthPower</span></dt><dd><pre lang="en" class="synopsis">IsNthPower (m,n)</pre><p lang="en">
108 Tests if a rational number <code class="varname">m</code> is a perfect
109 <code class="varname">n</code>th power. See also
110 <a class="link" href="ch11s07.html#gel-function-IsPerfectPower">IsPerfectPower</a>
111 and
112 <a class="link" href="ch11s07.html#gel-function-IsPerfectSquare">IsPerfectSquare</a>.
113 </p></dd><dt><span lang="en" class="term"><a name="gel-function-IsOdd"></a>IsOdd</span></dt><dd><pre lang="en" class="synopsis">IsOdd (n)</pre><p lang="en">Tests if an integer is odd.</p></dd><dt><span lang="en" class="term"><a name="gel-function-IsPerfectPower"></a>IsPerfectPower</span></dt><dd><pre lang="en" class="synopsis">IsPerfectPower (n)</pre><p lang="en">Check an integer for being any perfect power, a<sup>b</sup>.</p></dd><dt><span lang="en" class="term"><a name="gel-function-IsPerfectSquare"></a>IsPerfectSquare</span></dt><dd><pre lang="en" class="synopsis">IsPerfectSquare (n)</pre><p lang="en">
114 Check an integer for being a perfect square of an integer. The number must
115 be an integer. Negative integers are never perfect
116 squares of integers.
117 </p></dd><dt><span lang="en" class="term"><a name="gel-function-IsPrime"></a>IsPrime</span></dt><dd><pre lang="en" class="synopsis">IsPrime (n)</pre><p lang="en">
118 Tests primality of integers, for numbers less than 2.5e10 the
119 answer is deterministic (if Riemann hypothesis is true). For
120 numbers larger, the probability of a false positive
121 depends on
122 <a class="link" href="ch11s03.html#gel-function-IsPrimeMillerRabinReps">
123 <code class="function">IsPrimeMillerRabinReps</code></a>. That
124 is the probability of false positive is 1/4 to the power
125 <code class="function">IsPrimeMillerRabinReps</code>. The default
126 value of 22 yields a probability of about 5.7e-14.
127 </p><p lang="en">
128 If <code class="constant">false</code> is returned, you can be sure that
129 the number is a composite. If you want to be absolutely sure
130 that you have a prime you can use
131 <a class="link" href="ch11s07.html#gel-function-MillerRabinTestSure">
132 <code class="function">MillerRabinTestSure</code></a> but it may take
133 a lot longer.
134 </p><p lang="en">
135 See
136 <a class="ulink" href="http://planetmath.org/PrimeNumber" target="_top">Planetmath</a> or
137 <a class="ulink" href="http://mathworld.wolfram.com/PrimeNumber.html" target="_top">Mathworld</a> for more information.
138 </p></dd><dt><span lang="en" class="term"><a name="gel-function-IsPrimitiveMod"></a>IsPrimitiveMod</span></dt><dd><pre lang="en" class="synopsis">IsPrimitiveMod (g,q)</pre><p lang="en">Check if <code class="varname">g</code> is primitive in F<sub>q</sub>, the finite
139 group of order <code class="varname">q</code>, where <code class="varname">q</code> is a prime. If <code class="varname">q</code> is not prime results are bogus.</p></dd><dt><span lang="en" class="term"><a name="gel-function-IsPrimitiveModWithPrimeFactors"></a>IsPrimitiveModWithPrimeFactors</span></dt><dd><pre lang="en" class="synopsis">IsPrimitiveModWithPrimeFactors (g,q,f)</pre><p lang="en">Check if <code class="varname">g</code> is primitive in F<sub>q</sub>, the finite
140 group of order <code class="varname">q</code>, where <code class="varname">q</code> is a prime and
141 <code class="varname">f</code> is a vector of prime factors of <code class="varname">q</code>-1.
142 If <code class="varname">q</code> is not prime results are bogus.</p></dd><dt><span lang="en" class="term"><a name="gel-function-IsPseudoprime"></a>IsPseudoprime</span></dt><dd><pre lang="en" class="synopsis">IsPseudoprime (n,b)</pre><p lang="en">If <code class="varname">n</code> is a pseudoprime base <code class="varname">b</code> but not a prime,
143 that is if <strong class="userinput"><code>b^(n-1) == 1 mod n</code></strong>. This calls the <a class="link" href="ch11s07.html#gel-function-PseudoprimeTest"><code class="function">PseudoprimeTest</code></a></p></dd><dt><span lang="en" class="term"><a name="gel-function-IsStrongPseudoprime"></a>IsStrongPseudoprime</span></dt><dd><pre lang="en" class="synopsis">IsStrongPseudoprime (n,b)</pre><p lang="en">Test if <code class="varname">n</code> is a strong pseudoprime to base <code class="varname">b</code> but not a prime.</p></dd><dt><span lang="en" class="term"><a name="gel-function-Jacobi"></a>Jacobi</span></dt><dd><pre lang="en" class="synopsis">Jacobi (a,b)</pre><p lang="en">Aliases: <code class="function">JacobiSymbol</code></p><p lang="en">Calculate the Jacobi symbol (a/b) (b should be odd).</p></dd><dt><span lang="en" class="term"><a name="gel-function-JacobiKronecker"></a>JacobiKronecker</span></dt><dd><pre lang="en" class="synopsis">JacobiKronecker (a,b)</pre><p lang="en">Aliases: <code class="function">JacobiKroneckerSymbol</code></p><p lang="en">Calculate the Jacobi symbol (a/b) with the Kronecker extension (a/2)=(2/a) when a odd, or (a/2)=0 when a even.</p></dd><dt><span lang="en" class="term"><a name="gel-function-LeastAbsoluteResidue"></a>LeastAbsoluteResidue</span></dt><dd><pre lang="en" class="synopsis">LeastAbsoluteResidue (a,n)</pre><p lang="en">Return the residue of <code class="varname">a</code> mod <code class="varname">n</code> with the least absolute value (in the interval -n/2 to n/2).</p></dd><dt><span lang="en" class="term"><a name="gel-function-Legendre"></a>Legendre</span></dt><dd><pre lang="en" class="synopsis">Legendre (a,p)</pre><p lang="en">Aliases: <code class="function">LegendreSymbol</code></p><p lang="en">Calculate the Legendre symbol (a/p).</p><p lang="en">
144 See
145 <a class="ulink" href="http://planetmath.org/LegendreSymbol" target="_top">Planetmath</a> or
146 <a class="ulink" href="http://mathworld.wolfram.com/LegendreSymbol.html" target="_top">Mathworld</a> for more information.
147 </p></dd><dt><span lang="en" class="term"><a name="gel-function-LucasLehmer"></a>LucasLehmer</span></dt><dd><pre lang="en" class="synopsis">LucasLehmer (p)</pre><p lang="en">Test if 2<sup>p</sup>-1 is a Mersenne prime using the Lucas-Lehmer test.
148 See also
149 <a class="link" href="ch11s07.html#gel-function-MersennePrimeExponents">MersennePrimeExponents</a>
150 and
151 <a class="link" href="ch11s07.html#gel-function-IsMersennePrimeExponent">IsMersennePrimeExponent</a>.
152 </p><p lang="en">
153 See
154 <a class="ulink" href="https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test" target="_top">Wikipedia</a>,
155 <a class="ulink" href="http://planetmath.org/LucasLhemer" target="_top">Planetmath</a>, or
156 <a class="ulink" href="http://mathworld.wolfram.com/Lucas-LehmerTest.html" target="_top">Mathworld</a> for more information.
157 </p></dd><dt><span lang="en" class="term"><a name="gel-function-LucasNumber"></a>LucasNumber</span></dt><dd><pre lang="en" class="synopsis">LucasNumber (n)</pre><p lang="en">Returns the <code class="varname">n</code>th Lucas number.</p><p lang="en">
158 See
159 <a class="ulink" href="https://en.wikipedia.org/wiki/Lucas_number" target="_top">Wikipedia</a>,
160 <a class="ulink" href="http://planetmath.org/LucasNumbers" target="_top">Planetmath</a>, or
161 <a class="ulink" href="http://mathworld.wolfram.com/LucasNumber.html" target="_top">Mathworld</a> for more information.
162 </p></dd><dt><span lang="en" class="term"><a name="gel-function-MaximalPrimePowerFactors"></a>MaximalPrimePowerFactors</span></dt><dd><pre lang="en" class="synopsis">MaximalPrimePowerFactors (n)</pre><p lang="en">Return all maximal prime power factors of a number.</p></dd><dt><span lang="en" class="term"><a name="gel-function-MersennePrimeExponents"></a>MersennePrimeExponents</span></dt><dd><pre lang="en" class="synopsis">MersennePrimeExponents</pre><p lang="en">
163 A vector of known Mersenne prime exponents, that is
164 a list of positive integers
165 <code class="varname">p</code> such that
166 2<sup>p</sup>-1 is a prime.
167 See also
168 <a class="link" href="ch11s07.html#gel-function-IsMersennePrimeExponent">IsMersennePrimeExponent</a>
169 and
170 <a class="link" href="ch11s07.html#gel-function-LucasLehmer">LucasLehmer</a>.
171 </p><p lang="en">
172 See
173 <a class="ulink" href="https://en.wikipedia.org/wiki/Mersenne_prime" target="_top">Wikipedia</a>,
174 <a class="ulink" href="http://planetmath.org/MersenneNumbers" target="_top">Planetmath</a>,
175 <a class="ulink" href="http://mathworld.wolfram.com/MersennePrime.html" target="_top">Mathworld</a> or
176 <a class="ulink" href="http://www.mersenne.org/" target="_top">GIMPS</a>
177 for more information.
178 </p></dd><dt><span lang="en" class="term"><a name="gel-function-MillerRabinTest"></a>MillerRabinTest</span></dt><dd><pre lang="en" class="synopsis">MillerRabinTest (n,reps)</pre><p lang="en">
179 Use the Miller-Rabin primality test on <code class="varname">n</code>,
180 <code class="varname">reps</code> number of times. The probability of false
181 positive is <strong class="userinput"><code>(1/4)^reps</code></strong>. It is probably
182 usually better to use
183 <a class="link" href="ch11s07.html#gel-function-IsPrime">
184 <code class="function">IsPrime</code></a> since that is faster and
185 better on smaller integers.
186 </p><p lang="en">
187 See
188 <a class="ulink" href="https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test" target="_top">Wikipedia</a> or
189 <a class="ulink" href="http://planetmath.org/MillerRabinPrimeTest" target="_top">Planetmath</a> or
190 <a class="ulink" href="http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html" target="_top">Mathworld</a> for more information.
191 </p></dd><dt><span lang="en" class="term"><a name="gel-function-MillerRabinTestSure"></a>MillerRabinTestSure</span></dt><dd><pre lang="en" class="synopsis">MillerRabinTestSure (n)</pre><p lang="en">
192 Use the Miller-Rabin primality test on <code class="varname">n</code> with
193 enough bases that assuming the Generalized Riemann Hypothesis the
194 result is deterministic.
195 </p><p lang="en">
196 See
197 <a class="ulink" href="https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test" target="_top">Wikipedia</a>,
198 <a class="ulink" href="http://planetmath.org/MillerRabinPrimeTest" target="_top">Planetmath</a>, or
199 <a class="ulink" href="http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html" target="_top">Mathworld</a> for more information.
200 </p></dd><dt><span lang="en" class="term"><a name="gel-function-ModInvert"></a>ModInvert</span></dt><dd><pre lang="en" class="synopsis">ModInvert (n,m)</pre><p lang="en">Returns inverse of n mod m.</p><p lang="en">
201 See
202 <a class="ulink" href="http://mathworld.wolfram.com/ModularInverse.html" target="_top">Mathworld</a> for more information.
203 </p></dd><dt><span lang="en" class="term"><a name="gel-function-MoebiusMu"></a>MoebiusMu</span></dt><dd><pre lang="en" class="synopsis">MoebiusMu (n)</pre><p lang="en">
204 Return the Moebius mu function evaluated in <code class="varname">n</code>.
205 That is, it returns 0 if <code class="varname">n</code> is not a product
206 of distinct primes and <strong class="userinput"><code>(-1)^k</code></strong> if it is
207 a product of <code class="varname">k</code> distinct primes.
208 </p><p lang="en">
209 See
210 <a class="ulink" href="http://planetmath.org/MoebiusFunction" target="_top">Planetmath</a> or
211 <a class="ulink" href="http://mathworld.wolfram.com/MoebiusFunction.html" target="_top">Mathworld</a> for more information.
212 </p></dd><dt><span lang="en" class="term"><a name="gel-function-NextPrime"></a>NextPrime</span></dt><dd><pre lang="en" class="synopsis">NextPrime (n)</pre><p lang="en">
213 Returns the least prime greater than <code class="varname">n</code>.
214 Negatives of primes are considered prime and so to get the
215 previous prime you can use <strong class="userinput"><code>-NextPrime(-n)</code></strong>.
216 </p><p lang="en">
217 This function uses the GMPs <code class="function">mpz_nextprime</code>,
218 which in turn uses the probabilistic Miller-Rabin test
219 (See also <a class="link" href="ch11s07.html#gel-function-MillerRabinTest"><code class="function">MillerRabinTest</code></a>).
220 The probability
221 of false positive is not tunable, but is low enough
222 for all practical purposes.
223 </p><p lang="en">
224 See
225 <a class="ulink" href="http://planetmath.org/PrimeNumber" target="_top">Planetmath</a> or
226 <a class="ulink" href="http://mathworld.wolfram.com/PrimeNumber.html" target="_top">Mathworld</a> for more information.
227 </p></dd><dt><span lang="en" class="term"><a name="gel-function-PadicValuation"></a>PadicValuation</span></dt><dd><pre lang="en" class="synopsis">PadicValuation (n,p)</pre><p lang="en">Returns the p-adic valuation (number of trailing zeros in base <code class="varname">p</code>).</p><p lang="en">
228 See
229 <a class="ulink" href="https://en.wikipedia.org/wiki/P-adic_order" target="_top">Wikipedia</a> or
230 <a class="ulink" href="http://planetmath.org/PAdicValuation" target="_top">Planetmath</a> for more information.
231 </p></dd><dt><span lang="en" class="term"><a name="gel-function-PowerMod"></a>PowerMod</span></dt><dd><pre lang="en" class="synopsis">PowerMod (a,b,m)</pre><p lang="en">
232 Compute <strong class="userinput"><code>a^b mod m</code></strong>. The
233 <code class="varname">b</code>'s power of <code class="varname">a</code> modulo
234 <code class="varname">m</code>. It is not necessary to use this function
235 as it is automatically used in modulo mode. Hence
236 <strong class="userinput"><code>a^b mod m</code></strong> is just as fast.
237 </p></dd><dt><span lang="en" class="term"><a name="gel-function-Prime"></a>Prime</span></dt><dd><pre lang="en" class="synopsis">Prime (n)</pre><p lang="en">Aliases: <code class="function">prime</code></p><p lang="en">Return the <code class="varname">n</code>th prime (up to a limit).</p><p lang="en">
238 See
239 <a class="ulink" href="http://planetmath.org/PrimeNumber" target="_top">Planetmath</a> or
240 <a class="ulink" href="http://mathworld.wolfram.com/PrimeNumber.html" target="_top">Mathworld</a> for more information.
241 </p></dd><dt><span lang="en" class="term"><a name="gel-function-PrimeFactors"></a>PrimeFactors</span></dt><dd><pre lang="en" class="synopsis">PrimeFactors (n)</pre><p lang="en">Return all prime factors of a number as a vector.</p><p lang="en">
242 See
243 <a class="ulink" href="https://en.wikipedia.org/wiki/Prime_factor" target="_top">Wikipedia</a> or
244 <a class="ulink" href="http://mathworld.wolfram.com/PrimeFactor.html" target="_top">Mathworld</a> for more information.
245 </p></dd><dt><span lang="en" class="term"><a name="gel-function-PseudoprimeTest"></a>PseudoprimeTest</span></dt><dd><pre lang="en" class="synopsis">PseudoprimeTest (n,b)</pre><p lang="en">Pseudoprime test, returns <code class="constant">true</code> if and only if
246 <strong class="userinput"><code>b^(n-1) == 1 mod n</code></strong></p><p lang="en">
247 See
248 <a class="ulink" href="http://planetmath.org/Pseudoprime" target="_top">Planetmath</a> or
249 <a class="ulink" href="http://mathworld.wolfram.com/Pseudoprime.html" target="_top">Mathworld</a> for more information.
250 </p></dd><dt><span lang="en" class="term"><a name="gel-function-RemoveFactor"></a>RemoveFactor</span></dt><dd><pre lang="en" class="synopsis">RemoveFactor (n,m)</pre><p lang="en">Removes all instances of the factor <code class="varname">m</code> from the number <code class="varname">n</code>. That is divides by the largest power of <code class="varname">m</code>, that divides <code class="varname">n</code>.</p><p lang="en">
251 See
252 <a class="ulink" href="http://planetmath.org/Divisibility" target="_top">Planetmath</a> or
253 <a class="ulink" href="http://mathworld.wolfram.com/Factor.html" target="_top">Mathworld</a> for more information.
254 </p></dd><dt><span lang="en" class="term"><a name="gel-function-SilverPohligHellmanWithFactorization"></a>SilverPohligHellmanWithFactorization</span></dt><dd><pre lang="en" class="synopsis">SilverPohligHellmanWithFactorization (n,b,q,f)</pre><p lang="en">Find discrete log of <code class="varname">n</code> base <code class="varname">b</code> in F<sub>q</sub>, the finite group of order <code class="varname">q</code>, where <code class="varname">q</code> is a prime using the Silver-Pohlig-Hellman algorithm, given <code class="varname">f</code> being the factorization of <code class="varname">q</code>-1.</p></dd><dt><span lang="en" class="term"><a name="gel-function-SqrtModPrime"></a>SqrtModPrime</span></dt><dd><pre lang="en" class="synopsis">SqrtModPrime (n,p)</pre><p lang="en">Find square root of <code class="varname">n</code> modulo <code class="varname">p</code> (where <code class="varname">p</code> is a prime). Null is returned if not a quadratic residue.</p><p lang="en">
255 See
256 <a class="ulink" href="http://planetmath.org/QuadraticResidue" target="_top">Planetmath</a> or
257 <a class="ulink" href="http://mathworld.wolfram.com/QuadraticResidue.html" target="_top">Mathworld</a> for more information.
258 </p></dd><dt><span lang="en" class="term"><a name="gel-function-StrongPseudoprimeTest"></a>StrongPseudoprimeTest</span></dt><dd><pre lang="en" class="synopsis">StrongPseudoprimeTest (n,b)</pre><p lang="en">Run the strong pseudoprime test base <code class="varname">b</code> on <code class="varname">n</code>.</p><p lang="en">
259 See
260 <a class="ulink" href="https://en.wikipedia.org/wiki/Strong_pseudoprime" target="_top">Wikipedia</a>,
261 <a class="ulink" href="http://planetmath.org/StrongPseudoprime" target="_top">Planetmath</a>, or
262 <a class="ulink" href="http://mathworld.wolfram.com/StrongPseudoprime.html" target="_top">Mathworld</a> for more information.
263 </p></dd><dt><span lang="en" class="term"><a name="gel-function-gcd"></a>gcd</span></dt><dd><pre lang="en" class="synopsis">gcd (a,args...)</pre><p lang="en">Aliases: <code class="function">GCD</code></p><p lang="en">
264 Greatest common divisor of integers. You can enter as many
265 integers as you want in the argument list, or you can give
266 a vector or a matrix of integers. If you give more than
267 one matrix of the same size then GCD is done element by
268 element.
269 </p><p lang="en">
270 See
271 <a class="ulink" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" target="_top">Wikipedia</a>,
272 <a class="ulink" href="http://planetmath.org/GreatestCommonDivisor" target="_top">Planetmath</a>, or
273 <a class="ulink" href="http://mathworld.wolfram.com/GreatestCommonDivisor.html" target="_top">Mathworld</a> for more information.
274 </p></dd><dt><span lang="en" class="term"><a name="gel-function-lcm"></a>lcm</span></dt><dd><pre lang="en" class="synopsis">lcm (a,args...)</pre><p lang="en">Aliases: <code class="function">LCM</code></p><p lang="en">
275 Least common multiplier of integers. You can enter as many
276 integers as you want in the argument list, or you can give a
277 vector or a matrix of integers. If you give more than one
278 matrix of the same size then LCM is done element by element.
279 </p><p lang="en">
280 See
281 <a class="ulink" href="https://en.wikipedia.org/wiki/Least_common_multiple" target="_top">Wikipedia</a>,
282 <a class="ulink" href="http://planetmath.org/LeastCommonMultiple" target="_top">Planetmath</a>, or
283 <a class="ulink" href="http://mathworld.wolfram.com/LeastCommonMultiple.html" target="_top">Mathworld</a> for more information.
284 </p></dd></dl></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch11s06.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="ch11.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="ch11s08.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Trigonometria </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Manipulação de matrizes</td></tr></table></div></body></html>