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