AreRelativelyPrime (a,b)
Are the real integers a and b relatively prime? Returns true or false.
See Planetmath or Mathworld for more information.
BernoulliNumber (n)
Return the nth Bernoulli number
ChineseRemainder (a,m)
Aliases: CRT
Find the x that solves the system given by
the vector a and modulo the elements of
m, using the Chinese Remainder Theorem.
See Planetmath or Mathworld for more information.
CombineFactorizations (a,b)
Given two factorizations, give the factorization of the product.
See Factorize.
ConvertFromBase (v,b)
Convert a vector of values indicating powers of b to a number
ConvertToBase (n,b)
Convert a number to a vector of powers for elements in base b
DiscreteLog (n,b,q)
Find discrete log of n base b in F_q where q is a prime using the Silver-Pohlig-Hellman algoritm
See Planetmath or Mathworld for more information.
Divides (m,n)
Checks divisibility (if m divides n)
EulerPhi (n)
Compute the Euler phi function for n, that is
the number of integers between 1 and n
relatively prime to n.
See Planetmath or Mathworld for more information.
ExactDivision (n,d)
Return n/d but only if d
divides n. If d
does not divide n then this function returns
garbage. This is a lot faster for very large numbers
than the operation n/d, but of course only
useful if you know that the division is exact.
Factorize (n)
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:
genius> Factorize(11*11*13) = [1 11 13 1 2 1]
Factors (n)
Return all factors of n in a vector. This
includes all the non-prime factors as well. It includes 1 and the
number itself. So for example to print all the perfect numbers
(those that are sums of their factors) up to the number 1000 you
could do (this is of course very inefficent)
for n=1 to 1000 do (
if MatrixSum (Factors(n)) == 2*n then
print(n)
)
FermatFactorization (n,tries)
Attempt fermat factorization of n into
(t-s)*(t+s), returns t
and s as a vector if possible, null otherwise.
tries specifies the number of tries before
giving up.
This is a fairly good factorization if your number is the product of two factors that are very close to each other.
FindPrimitiveElementMod (q)
Find the first primitive element in F_q (q must be a prime)
FindRandomPrimitiveElementMod (q)
Find a random primitive element in F_q (q must be a prime)
IndexCalculus (n,b,q,S)
Compute discrete log base b of n in F_q (q a prime) using the factor base S. S should be a column of primes possibly with second column precalculated by IndexCalculusPrecalculation.
IndexCalculusPrecalculation (b,q,S)
Run the precalculation step of IndexCalculus for logarithms base b in F_q (q a prime) for the factor base S (where S is a column vector of primes). The logs will be precalculated and returned in the second column.
IsEven (n)
Tests if an integer is even.
IsNthPower (m,n)
Tests if a rational number m is a perfect
nth power. See also
IsPerfectPower
and
IsPerfectSquare.
IsOdd (n)
Tests if an integer is odd
IsPerfectPower (n)
Check a number for being any perfect power (a^b)
IsPerfectSquare (n)
Check a number for being a perfect square. The number must be a real integer. Negative integers are of course never perfect squares.
IsPrime (n)
Tests primality of integers, for numbers less than 25*10^9 the
answer is deterministic (if Riemann hypothesis is true). For
numbers larger, the probability of a false positive
depends on
IsPrimeMillerRabinReps. That
is the probability of false positive is 1/4 to the power
IsPrimeMillerRabinReps. The default
value of 22 yields a probability of about 5.7e-14.
If false 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
MillerRabinTestSure but it may take
a lot longer.
See Planetmath or Mathworld for more information.
IsPrimitiveMod (g,q)
Check if g is primitive in F_q, where q is a prime. If q is not prime results are bogus.
IsPrimitiveModWithPrimeFactors (g,q,f)
Check if g is primitive in F_q, where q is a prime and f is a vector of prime factors of q-1. If q is not prime results are bogus.
IsPseudoprime (n,b)
If n is a pseudoprime base b but not a prime, that is if b^(n-1) == 1 mod n
IsStrongPseudoprime (n,b)
Test if n is a strong pseudoprime to base b but not a prime
Jacobi (a,b)
Aliases: JacobiSymbol
Calculate the Jacobi symbol (a/b) (b should be odd)
JacobiKronecker (a,b)
Aliases: JacobiKroneckerSymbol
Calculate the Jacobi symbol (a/b) with the Kronecker extension (a/2)=(2/a) when a odd, or (a/2)=0 when a even
LeastAbsoluteResidue (a,n)
Return the residue of a mod n with the least absolute value (in the interval -n/2 to n/2)
Legendre (a,p)
Aliases: LegendreSymbol
Calculate the Legendre symbol (a/p).
See Planetmath or Mathworld for more information.
LucasLehmer (p)
Test if Mp is a Mersenne prime using the Lucas-Lehmer test
See Planetmath or Mathworld for more information.
LucasNumber (n)
Returns the n'th Lucas number
See Planetmath or Mathworld for more information.
MaximalPrimePowerFactors (n)
Return all maximal prime power factors of a number
MillerRabinTest (n,reps)
Use the Miller-Rabin primality test on n,
reps number of times. The probability of false
positive is (1/4)^reps. It is probably
usually better to use
IsPrime since that is faster and
better on smaller integers.
See Planetmath or Mathworld for more information.
MillerRabinTestSure (n)
Use the Miller-Rabin primality test on n with
enough bases that assuming the Generalized Reimann Hypothesis the
result is deterministic.
See Planetmath or Mathworld for more information.
ModInvert (n,m)
Returns inverse of n mod m
See Mathworld for more information.
MoebiusMu (n)
Return the Moebius mu function evaluated in n.
That is, it returns 0 if n is not a product
of distinct primes and (-1)^k if it is
a product of k distinct primes.
See Planetmath or Mathworld for more information.
NextPrime (n)
Returns the least prime greater than n.
Negatives of primes are considered prime and so to get the
previous prime you can use -NextPrime(-n).
This uses the GMP's mpz_nextprime which in
turn uses the probabilistic Miller-Rabin test
(See also MillerRabinTest).
The probability
of false positive is not tunable, but is low enough
for all practical purposes.
See Planetmath or Mathworld for more information.
PadicValuation (n,p)
Returns the padic valuation (number of trailing zeros in base p).
See Planetmath for more information.
PowerMod (a,b,m)
Compute a^b mod m. The
b's power of a modulo
m.
Prime (n)
Aliases: prime
Return the n'th prime (up to a limit)
See Planetmath or Mathworld for more information.
PrimeFactors (n)
Return all prime factors of a number as a vector.
See Mathworld for more information.
PseudoprimeTest (n,b)
Pseudoprime test, returns true if and only if b^(n-1) == 1 mod n
See Planetmath or Mathworld for more information.
RemoveFactor (n,m)
Removes all instances of the factor m from the number n. That is divides by the largest power of m, that divides n.
See Planetmath or Mathworld for more information.
SilverPohligHellmanWithFactorization (n,b,q,f)
Find discrete log of n base b in F_q where q is a prime using the Silver-Pohlig-Hellman algoritm, given f being the factorization of q-1
SqrtModPrime (n,p)
Find square root of n modulo p (where p is a prime). Null is returned if not a quadratic residue.
See Planetmath or Mathworld for more information.
StrongPseudoprimeTest (n,b)
Run the strong pseudoprime test base b on n.
See Planetmath or Mathworld for more information.
gcd (a,args...)
Aliases: GCD
Greatest common divisor of integers. You can enter as many integers 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.
See Planetmath or Mathworld for more information.
lcm (a,args...)
Aliases: LCM
Least common multiplier of integers. You can enter as many integers 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.
See Planetmath or Mathworld for more information.