Théorie des nombres

AreRelativelyPrime
AreRelativelyPrime (a,b)

Si les entiers a et b sont premiers entre eux ? Renvoie true (vrai) ou false (faux).

See Wikipedia or Planetmath or Mathworld for more information.

BernoulliNumber
BernoulliNumber (n)

Renvoie le n-ième nombre de Bernoulli.

See Wikipedia or Mathworld for more information.

ChineseRemainder
ChineseRemainder (a,m)

Alias : CRT

Recherche x qui résout le système défini par le vecteur a et modulo les éléments de m, en utilisant le théorème des restes chinois.

See Wikipedia or Planetmath or Mathworld for more information.

CombineFactorizations
CombineFactorizations (a,b)

Étant donné deux factorisations, donne la factorisation du produit.

Consultez Factorize.

ConvertFromBase
ConvertFromBase (v,b)

Convertit un vecteur de valeurs indiquant les puissances de b en un nombre.

ConvertToBase
ConvertToBase (n,b)

Convertit un nombre en un vecteur contenant les puissances des éléments dans la base b.

DiscreteLog
DiscreteLog (n,b,q)

Calcule le logarithme discret de n base b dans Fq, le corps fini d'ordre qq est un nombre premier, en utilisant l'algorithme de Silver-Pohlig-Hellman.

See Wikipedia, Planetmath, or Mathworld for more information.

Divides
Divides (m,n)

Vérifie la divisibilité (si m divise n).

EulerPhi
EulerPhi (n)

Calcule la fonction d'Euler phi, c'est-à-dire le nombre d'entiers compris entre 1 et n qui sont premiers avec n.

See Wikipedia, Planetmath, or Mathworld for more information.

ExactDivision
ExactDivision (n,d)

Renvoie n/d mais seulement si d divise n. Si d ne divise pas n alors cette fonction ne renvoie rien d'utile. Cette fonction est beaucoup plus rapide pour les très grands nombres que l'opération n/d, mais bien sûr utile seulement si vous savez que la division est exacte.

Factorize
Factorize (n)

Renvoie la factorisation d'un nombre sous la forme d'une matrice. La première ligne contient les nombres premiers dans la factorisation (y compris 1) et la seconde ligne sont les puissances. Par exemple :

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

See Wikipedia for more information.

Factors
Factors (n)

Renvoie tous les facteurs de n dans un vecteur. Cela inclut tous les facteurs non premiers également mais aussi 1 et le nombre lui-même. Ainsi par exemple pour afficher tous les nombres parfaits (ceux qui sont la somme de leurs facteurs) jusqu'au nombre 1000, vous pouvez écrire (ce n'est bien sûr pas efficace) :

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

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.

C'est une assez bonne factorisation si votre nombre est le produit de deux facteurs très proches l'un de l'autre.

See Wikipedia for more information.

FindPrimitiveElementMod
FindPrimitiveElementMod (q)

Cherche le premier élément primitif dans Fq, le groupe fini d'ordre q. Bien sûr, q doit être premier.

FindRandomPrimitiveElementMod
FindRandomPrimitiveElementMod (q)

Cherche un élément primitif au hasard dans Fq, le groupe fini d'ordre q (q doit être premier).

IndexCalculus
IndexCalculus (n,b,q,S)

Compute discrete log base b of n in Fq, the finite group of order q (q a prime), using the factor base S. S should be a column of primes possibly with second column precalculated by IndexCalculusPrecalculation.

IndexCalculusPrecalculation
IndexCalculusPrecalculation (b,q,S)

Run the precalculation step of IndexCalculus for logarithms base b in Fq, the finite group of order 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
IsEven (n)

Teste si un entier est pair.

IsMersennePrimeExponent
IsMersennePrimeExponent (p)

Tests if a positive integer p is a Mersenne prime exponent. That is if 2p-1 is a prime. It does this by looking it up in a table of known values, which is relatively short. See also MersennePrimeExponents and LucasLehmer.

See Wikipedia, Planetmath, Mathworld or GIMPS for more information.

IsNthPower
IsNthPower (m,n)

Vérifie si un nombre rationnel m est une puissance n-ième parfaite. Consultez aussi IsPerfectPower et IsPerfectSquare.

IsOdd
IsOdd (n)

Teste si un entier est impair.

IsPerfectPower
IsPerfectPower (n)

Check an integer for being any perfect power, ab.

IsPerfectSquare
IsPerfectSquare (n)

Check an integer for being a perfect square of an integer. The number must be an integer. Negative integers are of course never perfect squares of integers.

IsPrime
IsPrime (n)

Teste la primalité des entiers ; pour les nombres inférieurs à 2,5e10 la réponse est déterministe (si l'hypothèse de Riemann est vérifiée). Pour des nombres plus grands, la probabilité d'une erreur de détermination dépend du paramètre IsPrimeMillerRabinReps. C'est-à-dire la probabilité d'une erreur de détermination vaut 1/4 à la puissance IsPrimeMillerRabinReps. La valeur par défaut de 22 mène à une probabilité d'environ 5.7e-14.

Si false (faux) est renvoyé, vous êtes sûr que le nombre est composé. Si vous voulez être absolument certain d'avoir un nombre premier vous pouvez utiliser la fonction MillerRabinTestSure mais cela peut prendre beaucoup plus de temps.

See Planetmath or Mathworld for more information.

IsPrimitiveMod
IsPrimitiveMod (g,q)

Vérifie que g est primitif dans Fq, le groupe fini d'ordre q, où q est premier. Si q n'est pas premier, les résultats sont erronés.

IsPrimitiveModWithPrimeFactors
IsPrimitiveModWithPrimeFactors (g,q,f)

Vérifie que g est primitif dans Fq, le groupe fini d'ordre q, où q est premier et f est un vecteur de facteurs premiers de q-1. Si q n'est pas premier, les résultats sont erronés.

IsPseudoprime
IsPseudoprime (n,b)

If n is a pseudoprime base b but not a prime, that is if b^(n-1) == 1 mod n. This calls the PseudoprimeTest

IsStrongPseudoprime
IsStrongPseudoprime (n,b)

Teste si n est un nombre pseudopremier fort en base b mais pas un nombre premier.

Jacobi
Jacobi (a,b)

Alias : JacobiSymbol

Calcule le symbole de Jacobi (a/b) (b doit être impair).

JacobiKronecker
JacobiKronecker (a,b)

Alias : JacobiKroneckerSymbol

Calcule le symbole de Jacobi (a/b) avec l'extension de Kronecker (a/2)=(2/a) si impair, ou (a/2)=0 si pair.

LeastAbsoluteResidue
LeastAbsoluteResidue (a,n)

Renvoie le résidu de a modulo n avec la plus petite valeur absolue (entre -n/2 et n/2).

Legendre
Legendre (a,p)

Alias : LegendreSymbol

Calcule le symbole de Legendre (a/p).

See Planetmath or Mathworld for more information.

LucasLehmer
LucasLehmer (p)

Teste si 2p-1 est un nombre premier de Mersenne en utilisant le test de Lucas-Lehmer. Consultez aussi MersennePrimeExponents et IsMersennePrimeExponent.

See Wikipedia, Planetmath, or Mathworld for more information.

LucasNumber
LucasNumber (n)

Renvoie le n-ième nombre de Lucas.

See Wikipedia, Planetmath, or Mathworld for more information.

MaximalPrimePowerFactors
MaximalPrimePowerFactors (n)

Renvoie les puissances premières d'un nombre.

MersennePrimeExponents
MersennePrimeExponents

Renvoie un vecteur de nombres premiers de Mersenne qui est une liste d'entiers positifs p tels que 2p-1 est entier. Consultez aussi IsMersennePrimeExponent et LucasLehmer.

See Wikipedia, Planetmath, Mathworld or GIMPS for more information.

MillerRabinTest
MillerRabinTest (n,reps)

Utilise le test de primalité de Miller-Rabin sur n, en faisant reps essais. La probabilité d'une erreur de détermination est (1/4)^reps. Il est probablement préférable d'utiliser la fonction IsPrime puisqu'elle est plus rapide et meilleure pour les entiers les plus petits.

See Wikipedia or Planetmath or Mathworld for more information.

MillerRabinTestSure
MillerRabinTestSure (n)

Use the Miller-Rabin primality test on n with enough bases that assuming the Generalized Riemann Hypothesis the result is deterministic.

See Wikipedia, Planetmath, or Mathworld for more information.

ModInvert
ModInvert (n,m)

Renvoie l'inverse de n mod m.

Consultez Mathworld pour plus d'informations.

MoebiusMu
MoebiusMu (n)

Renvoie la fonction mu de Moebius évaluée dans n. C'est-à-dire renvoie 0 si n n'est pas un produit de nombres premiers différents et (-1)^k si c'est un produit de k nombres premiers différents.

See Planetmath or Mathworld for more information.

NextPrime
NextPrime (n)

Renvoie le plus petit nombre premier supérieur à n. L'opposé d'un nombre premier est considéré comme un nombre premier donc pour obtenir le nombre premier précédent, vous pouvez utiliser -NextPrime(-n).

This function uses the GMPs 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
PadicValuation (n,p)

Renvoie la valuation p-adic (nombre de zéros après la virgule en base p).

See Wikipedia or Planetmath for more information.

PowerMod
PowerMod (a,b,m)

Compute a^b mod m. The b's power of a modulo m. It is not necessary to use this function as it is automatically used in modulo mode. Hence a^b mod m is just as fast.

Prime
Prime (n)

Alias : prime

Renvoie le n-ième nombre premier (jusqu'à une limite) .

See Planetmath or Mathworld for more information.

PrimeFactors
PrimeFactors (n)

Renvoie tous les facteurs premiers d'un nombre sous la forme d'un vecteur.

See Wikipedia or Mathworld for more information.

PseudoprimeTest
PseudoprimeTest (n,b)

Test de pseudoprimalité, renvoie true (vrai) si et seulement si b^(n-1) == 1 mod n

See Planetmath or Mathworld for more information.

RemoveFactor
RemoveFactor (n,m)

Supprime toutes les instances du facteur m dans le nombre n. C'est-à-dire divise par la plus grande puissance de m qui divise n.

See Planetmath or Mathworld for more information.

SilverPohligHellmanWithFactorization
SilverPohligHellmanWithFactorization (n,b,q,f)

Calcule le logarithme discret de n base b dans Fq, le corps fini d'ordre qq est un nombre premier, en utilisant l'algorithme de Silver-Pohlig-Hellman, sachant que f est la factorisation de q-1.

SqrtModPrime
SqrtModPrime (n,p)

Cherche la racine carrée de n modulo p (où p est premier). null est renvoyé si ce n'est pas un résidu quadratique.

See Planetmath or Mathworld for more information.

StrongPseudoprimeTest
StrongPseudoprimeTest (n,b)

Lance le test de pseudo-primarité forte en base b sur n.

See Wikipedia, Planetmath, or Mathworld for more information.

gcd
gcd (a,params...)

Alias : GCD

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.

See Wikipedia, Planetmath, or Mathworld for more information.

lcm
lcm (a,params...)

Alias : LCM

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.

See Wikipedia, Planetmath, or Mathworld for more information.