Teoría de números

AreRelativelyPrime
AreRelativelyPrime (a,b)

¿Son los números reales a and b primos entre sí? Devuelve true o false.

Consulte la Wikipedia o Planetmath o Mathworld para obtener más información.

BernoulliNumber
BernoulliNumber (n)

Devolver el n-ésimo número de Bernoulli.

Consulte la Wikipedia o Mathworld para obtener más información.

ChineseRemainder
ChineseRemainder (a,m)

Alias: CRT

Encontrar la x que resuelve el sistema dado por el vector a y el módulo de los elementos de m, utilizando el «teorema chino del resto».

Consulte la Wikipedia o Planetmath o Mathworld para obtener más información.

CombineFactorizations
CombineFactorizations (a,b)

Dadas dos factorizaciones, dar la factorización del producto.

Consulte la secciónfactorizar.

ConvertFromBase
ConvertFromBase (v,b)

Convertir un vector de valores mostrando potencias de b a un número.

ConvertToBase
ConvertToBase (n,b)

Convertir un número en un vector de potencias para elementos en base b.

DiscreteLog
DiscreteLog (n,b,q)

Encontrar el logaritmo discreto de n en base b en Fq, el campo finito de orden q, donde q es primo, utilizando el algoritmo de Silver-Pohlig-Hellman.

Consulte la Wikipedia, Planetmath, o Mathworld para obtener más información.

Divides
Divides (m,n)

Comprueba la divisibilidad (si m divide a n).

EulerPhi
EulerPhi (n)

Calcular la función phi de Euler para n, que es el número de enteros entre 1 y n primo relativo con n.

Consulte la Wikipedia, Planetmath, o Mathworld para obtener más información.

ExactDivision
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 it is only useful if you know that the division is exact.

Factorize
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]

Consulte la Wikipedia para obtener más información.

Factors
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 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)

for n=1 to 1000 do (
    if MatrixSum (Factors(n)) == 2*n then
        print(n)
)

FermatFactorization
FermatFactorization (n,tries)

Probar la factorización de Fermat de n en (t-s)*(t+s), devuelve t y s como un vector si es posible, null de otra manera tries especifica el número de intentos antes de abandonar

Es una buena factorización si su número es el producto de dos factores que están muy cerca.

Consulte la Wikipedia para obtener más información.

FindPrimitiveElementMod
FindPrimitiveElementMod (q)

Encontrar el primer elemento primitivo en Fq, en el grupo de orden finitoq. Por supuesto, q debe de ser primo.

FindRandomPrimitiveElementMod
FindRandomPrimitiveElementMod (q)

Encontrar un elemento primitivo aleatorio en Fq, en el grupo de orden finito q (q debe de ser primo)

IndexCalculus
IndexCalculus (n,b,q,S)

Calcula la base del logaritmo discreto b de n en Fq, el grupo finito de orden q (q un primo), utilizando el factor base S. S será una columna de números primos y una segunda columna precalculada por IndexCalculusPrecalculation.

IndexCalculusPrecalculation
IndexCalculusPrecalculation (b,q,S)

Ejecuta los pasos para los cálculos previos de IndexCalculus para logaritmos de base b en Fq, del grupo finito de orden q (q un primo), para el factor base S (donde S es una columna de vector de primos). Los registros se calculan previamente y se devuelven en la segunda columna.

IsEven
IsEven (n)

Comprueba si un entero es par.

IsMersennePrimeExponent
IsMersennePrimeExponent (p)

Comprueba si un entero positivo p es un exponente primo de Mersenne. Esto es si 2p-1 es un primo. Esto lo hace mirando en una tabla de valores conocidos que es relativamente corta. Vea también MersennePrimeExponents y LucasLehmer.

Consulte la Wikipedia, Planetmath, Mathworld o GIMPS para obtener más información.

IsNthPower
IsNthPower (m,n)

Comprueba si un número racional m es una potencia n-ésima perfecta. Consulte IsPerfectPower y IsPerfectSquare.

IsOdd
IsOdd (n)

Comprueba su un entero es impar.

IsPerfectPower
IsPerfectPower (n)

Comprobar si un entero es una potencia perfecta, ab.

IsPerfectSquare
IsPerfectSquare (n)

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.

IsPrime
IsPrime (n)

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

Consulte Planetmath o Mathworld para obtener más información.

IsPrimitiveMod
IsPrimitiveMod (g,q)

Comprobar si g es primario en Fq, el grupo finito de orden q, donde q es un primo. Si q no es un primo los resultados son falsos.

IsPrimitiveModWithPrimeFactors
IsPrimitiveModWithPrimeFactors (g,q,f)

Comprobar si g es primario en Fq, el grupo finito de orden q, donde q es un primo y f es un vector de factores primos de q-1. Si q no es primo los resultados son falsos.

IsPseudoprime
IsPseudoprime (n,b)

Si n es pseudo-primo en base b pero no un primo, esto es si b^(n-1) == 1 mod n. Esto llama a PseudoprimeTest

IsStrongPseudoprime
IsStrongPseudoprime (n,b)

Compruebe si n es un pseudo-primo fuerte en base b pero no un primo.

Jacobi
Jacobi (a,b)

Alias: JacobiSymbol

Calcular el símbolo de Jacobi (a/b) (b debe ser impar).

JacobiKronecker
JacobiKronecker (a,b)

Alias: JacobiKroneckerSymbol

Calcular el símbolo de Jacobi (a/b) con extensión de Kronecker (a/2)=(2/a) cuando sea impar, o (a/2)=0 cuando sea par.

LeastAbsoluteResidue
LeastAbsoluteResidue (a,n)

Devuelve el resto de a mod n con el último valor absoluto (en el intervalo -n/2 to n/2).

Legendre
Legendre (a,p)

Alias: LegendreSymbol

Calcular el símbolo de Legendre (a/p).

Consulte Planetmath o Mathworld para obtener más información.

LucasLehmer
LucasLehmer (p)

Compruebe si 2p-1 es un primo de Mersenne utilizando la prueba de Lucas-Lehmer. Consulte también MersennePrimeExponents y IsMersennePrimeExponent.

Consulte la Wikipedia, Planetmath, o Mathworld para obtener más información.

LucasNumber
LucasNumber (n)

Devuelve el n-ésimo número de Lucas.

Consulte la Wikipedia, Planetmath, o Mathworld para obtener más información.

MaximalPrimePowerFactors
MaximalPrimePowerFactors (n)

Devuelve todos los factores primos de un número.

MersennePrimeExponents
MersennePrimeExponents

Un vector de Mersenne de exponentes primos conocidos, esto es una lista de enteros positivos p tal que 2p-1 es un primo. Consulte también IsMersennePrimeExponent y LucasLehmer.

Consulte la Wikipedia, Planetmath, Mathworld o GIMPS para obtener más información.

MillerRabinTest
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.

Consulte la Wikipedia o Planetmath o Mathworld para obtener más información.

MillerRabinTestSure
MillerRabinTestSure (n)

Utiliza la prueba Miller-Rabin de números primos de n con las bases suficientes que asuman la hipótesis generalizada de Reimann, el resultado es determinista.

Consulte la Wikipedia, Planetmath, o Mathworld para obtener más información.

ModInvert
ModInvert (n,m)

Devuelve el inverso de n módulo m.

Consulte Mathworld para obtener más información.

MoebiusMu
MoebiusMu (n)

Devuelve la función de Moebius «mu» de n. Esto es, devuelve 0 si n no es un producto entre primos distintos y (-1)^k si es un producto de k primos distintos.

Consulte Planetmath o Mathworld para obtener más información.

NextPrime
NextPrime (n)

Devuelve el primo menor más grande que n. Los primos negativos se consideran primos y así para obtener el primo anterior, puede usar -NextPrime(-n).

Esta función utiliza las GMP mpz_nextprime la cual vuelve a utilizar la prueba probabilística de Miller-Rabin (consulte también MillerRabinTest). La probabilidad de un falso positivo no se da, pero es lo suficientemente baja para prácticamente todos los propósitos.

Consulte Planetmath o Mathworld para obtener más información.

PadicValuation
PadicValuation (n,p)

Devuelve la evaluación del número «p-adic» (número de ceros que va dejando en base p).

Consulte la Wikipedia o Planetmath para obtener más información.

PowerMod
PowerMod (a,b,m)

Calcula a^b mod m. La potencia b de a módulo m. No es necesario utilizar esta función ya que se utiliza automáticamente en modo módulo. Por lo tanto a^b mod m es igual de rápido.

Prime
Prime (n)

Alias: prime

Devuelve el n-ésimo primo (hasta un límite).

Consulte Planetmath o Mathworld para obtener más información.

PrimeFactors
PrimeFactors (n)

Devuelve todos los factores primos de un número como un vector.

Consulte la Wikipedia o Mathworld para obtener más información.

PseudoprimeTest
PseudoprimeTest (n,b)

Pseudoprime test, returns true if and only if b^(n-1) == 1 mod n

Consulte Planetmath o Mathworld para obtener más información.

RemoveFactor
RemoveFactor (n,m)

Elimina todas las instancias del factor m desde el número n. Esto es, lo divide por la potencia mas grande de m, que divide n.

Consulte Planetmath o Mathworld para obtener más información.

SilverPohligHellmanWithFactorization
SilverPohligHellmanWithFactorization (n,b,q,f)

Buscar el logaritmo sencillo de n base b en Fq, de grupo de orden finito q, donde q es un primo que utiliza el algoritmo de Silver-Pohlig-Hellman, dado f es la factorización de q-1.

SqrtModPrime
SqrtModPrime (n,p)

Buscar la raíz cuadrada de n módulo p (donde p es un primo). Se devuelve «null» si el resto no es cuadrático.

Consulte Planetmath o Mathworld para obtener más información.

StrongPseudoprimeTest
StrongPseudoprimeTest (n,b)

Ejecutar la prueba del pseudo-primo fuerte en base b de n.

Consulte la Wikipedia, Planetmath, o Mathworld para obtener más información.

gcd
gcd (a,args...)

Alias: GCD

Máximo común divisor de enteros. Puede introducir tantos enteros en la lista de argumentos, o puede introducir un vector o una matriz de enteros. Si introduce más de una matriz del mismo tamaño, entonces el máximo común divisor se realiza elemento a elemento.

Consulte la Wikipedia, Planetmath, o Mathworld para obtener más información.

lcm
lcm (a,args...)

Alias: LCM

Mínimo común múltiplo de enteros. Puede introducir tantos enteros en la lista de argumentos, o introducir un vector o matriz de enteros. Si introduce mas de una matriz del mismo tamaño, entonces el mínimo común múltiplo se realiza elemento a elemento.

Consulte la Wikipedia, Planetmath, o Mathworld para obtener más información.