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)

Devuelve n/d pero solo si d es divisible entre n. Si d no es divisible entre n entonces esta función devuelve basura. Esto es mucho mas rápido para números muy grandes que la operación n/d, pero sólo es útil si se sabe que la división es exacta.

Factorize
Factorize (n)

Devuelve la factorización de un número como una matriz. La primera fila son los números primos en la factorización (incluido el 1) y la segunda fila son las potencias. Por ejemplo:

genius> Factorize(11*11*13)
=
[1      11      13
 1      2       1]

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

Factors
Factors (n)

Devuelve todos los factores de n en un vector. Esto incluye todos los factores no primos como buenos. Incluye 1 y el mismo número. Así por ejemplo, para imprimir todos los números perfectos (aquellos que son sumas de sus factores) hasta el número 1000 (esto es muy ineficiente) haga

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)

Comprobar si un entero es un cuadrado perfecto de un entero. El número será un entero real. Los enteros negativos, por supuesto, no son perfectos cuadrados de enteros reales.

IsPrime
IsPrime (n)

Comprueba si dos números enteros son primos, para números menores que 2.5e10 la respuesta es determinista (si la hipótesis de Riemann es verdadera). Para números más grandes, la probabilidad de un falso positivo depende de IsPrimeMillerRabinReps. Significa que la probabilidad de un falso positivo es 1/4 de la potencia IsPrimeMillerRabinReps. De manera predeterminada el valor de 22 produce una probabilidad entorno a 5.7e-14.

Si se devuelve false, puede estar seguro de que el número es un compuesto. Si quiere estar totalmente seguro de que tiene un número primo use MillerRabinTestSure pero esto le puede llevar mucho más tiempo.

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)

Utiliza la prueba de números primarios Miller-Rabin de n, reps número de veces. La probabilidad de falso positivo es (1/4)^reps. Probablemente es mejor usar IsPrime ya que es más rápido y mejor sobre enteros más pequeños.

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)

Prueba de pseudo-primo, devuelve true sólo si 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.