| 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></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> |