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 (n)
Renvoie le n
-ième nombre de Bernoulli.
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 (a,b)
Étant donné deux factorisations, donne la factorisation du produit.
Consultez Factorize.
ConvertFromBase (v,b)
Convertit un vecteur de valeurs indiquant les puissances de b en un nombre.
ConvertToBase (n,b)
Convertit un nombre en un vecteur contenant les puissances des éléments dans la base b
.
DiscreteLog (n,b,q)
Calcule le logarithme discret de n
base b
dans Fq, le corps fini d'ordre q
où q
est un nombre premier, en utilisant l'algorithme de Silver-Pohlig-Hellman.
See Wikipedia, Planetmath, or Mathworld for more information.
Divides (m,n)
Vérifie la divisibilité (si m
divise n
).
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 (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 (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]
See Wikipedia for more information.
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 (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 (q)
Cherche le premier élément primitif dans Fq, le groupe fini d'ordre q
. Bien sûr, q
doit être premier.
FindRandomPrimitiveElementMod (q)
Cherche un élément primitif au hasard dans Fq, le groupe fini d'ordre q
(q doit être premier).
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 (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 (n)
Teste si un entier est pair.
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 (m,n)
Vérifie si un nombre rationnel m
est une puissance n
-ième parfaite. Consultez aussi IsPerfectPower et IsPerfectSquare.
IsOdd (n)
Teste si un entier est impair.
IsPerfectPower (n)
Check an integer for being any perfect power, ab.
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 (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.
See Planetmath or Mathworld for more information.
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 (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 (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 (n,b)
Teste si n
est un nombre pseudopremier fort en base b
mais pas un nombre premier.
Jacobi (a,b)
Alias : JacobiSymbol
Calcule le symbole de Jacobi (a/b) (b doit être impair).
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 (a,n)
Renvoie le résidu de a
modulo n
avec la plus petite valeur absolue (entre -n/2 et n/2).
Legendre (a,p)
Alias : LegendreSymbol
Calcule le symbole de Legendre (a/p).
See Planetmath or Mathworld for more information.
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 (n)
Renvoie le n
-ième nombre de Lucas.
See Wikipedia, Planetmath, or Mathworld for more information.
MaximalPrimePowerFactors (n)
Renvoie les puissances premières d'un nombre.
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 (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 Wikipedia or Planetmath or Mathworld for more information.
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 (n,m)
Renvoie l'inverse de n mod m.
Consultez Mathworld pour plus d'informations.
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 (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 (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 (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 (n)
Alias : prime
Renvoie le n
-ième nombre premier (jusqu'à une limite) .
See Planetmath or Mathworld for more information.
PrimeFactors (n)
Renvoie tous les facteurs premiers d'un nombre sous la forme d'un vecteur.
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)
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 (n,b,q,f)
Calcule le logarithme discret de n
base b
dans Fq, le corps fini d'ordre q
où q
est un nombre premier, en utilisant l'algorithme de Silver-Pohlig-Hellman, sachant que f
est la factorisation de q
-1.
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 (n,b)
Lance le test de pseudo-primarité forte en base b
sur n
.
See Wikipedia, Planetmath, or Mathworld for more information.
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 (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.