AreRelativelyPrime (a,b)
Är de reella heltalen a
och b
relativt prima? Returnerar true
eller false
.
Se Wikipedia eller Planetmath eller Mathworld för mer information.
BernoulliNumber (n)
Returnerar det n
:e Bernoullitalet.
ChineseRemainder (a,m)
Alias: CRT
Hitta det x
som löser systemet givet av vektorn a
modulo elementen i m
med den kinesiska restsatsen.
Se Wikipedia eller Planetmath eller Mathworld för mer information.
CombineFactorizations (a,b)
Givet två faktoriseringar, ange faktoriseringen av produkten.
Se Factorize.
ConvertFromBase (v,b)
Konvertera en vektor av värden som indikerar potenser av b till ett tal.
ConvertToBase (n,b)
Konvertera ett tal till en vektor av potenser för element i bas b
.
DiscreteLog (n,b,q)
Hitta diskret logaritm av n
bas b
i Fq, den ändliga kroppen av ordning q
, där q
är ett primtal, med Silver-Pohlig-Hellman-algoritmen.
Se Wikipedia, Planetmath eller Mathworld för mer information.
Divides (m,n)
Kontrollerar delbarhet (om m
delar n
).
EulerPhi (n)
Beräkna Eulers φ-funktion för n
, det vill säga antalet heltal mellan 1 och n
som är relativt prima till n
.
Se Wikipedia, Planetmath eller Mathworld för mer information.
ExactDivision (n,d)
Returnera n/d
men endast om d
delar n
. Om d
inte delar n
kommer denna funktion returnera skräpvärden. Detta är mycket snabbare för väldigt stora tal än operationen n/d
, men bara användbart om du vet att divisionen är exakt.
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]
Se Wikipedia för mer 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,försök)
Försök med Fermatfaktorisering av n
till (t-s)*(t+s)
, returnerar t
och s
som en vektor om möjligt, annars null
. försök
anger antalet försök innan vi ger upp.
Detta är en rätt bra faktorisering om ditt tal är produkten av två faktorer som ligger väldigt nära varandra.
Se Wikipedia för mer information.
FindPrimitiveElementMod (q)
Hitta det första primitiva elementet i Fq, den finita gruppen av ordning q
. Givetvis måste q
vara ett primtal.
FindRandomPrimitiveElementMod (q)
Hitta ett slumpmässigt primitivt element i Fq, den ändliga gruppen av ordning q
(q måste vara ett primtal).
IndexCalculus (n,b,q,S)
Beräkna diskret logaritm av n bas b
i Fq, den ändliga gruppen av ordning q
(q
ett primtal) med faktorbas S
. S
ska vara en kolumn av primtal, möjligen med en andra kolumn förberäknad av IndexCalculusPrecalculation
.
IndexCalculusPrecalculation (b,q,S)
Kör förberäkningssteget av IndexCalculus
för logaritmer bas b
i Fq, den ändliga gruppen av ordning q
(q
ett primtal) för faktorbasen S
(där S
är en kolumnvektor av primtal). Logaritmerna kommer vara förberäknade och returneras i den andra kolumnen.
IsEven (n)
Testar om ett heltal är jämnt.
IsMersennePrimeExponent (p)
Testar om ett positivt heltal p
är en Mersenneprimtalsexponent. Det vill säga om 2p-1 är ett primtal. Det gör detta genom att slå upp det i en tabell med kända värden, vilken är relativt kort. Se även MersennePrimeExponents och LucasLehmer.
Se Wikipedia, Planetmath, Mathworld eller GIMPS för mer information.
IsNthPower (m,n)
Testar om ett rationellt tal m
är lika med något heltal upphöjt till n
. Se även IsPerfectPower och IsPerfectSquare.
IsOdd (n)
Testar om ett heltal är udda.
IsPerfectPower (n)
Kontrollera om ett heltal är en perfekt potens, ab.
IsPerfectSquare (n)
Kontrollera om ett heltal är en perfekt kvadrat av ett heltal. Talet måste vara ett heltal. Negativa heltal kan aldrig vara perfekta kvadrater av heltal.
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.
Se Planetmath eller Mathworld för mer information.
IsPrimitiveMod (g,q)
Kontrollera om g
är primitiv i Fq, den finita gruppen av ordning q
, där q
är ett primtal. Om q
inte är ett primtal kommer resultat vara felaktiga.
IsPrimitiveModWithPrimeFactors (g,q,f)
Kontrollera om g
är primitiv i Fq, den finita gruppen av ordning q
, där q
är ett primtal och f
är en vektor av primtalsfaktorer av q
-1. Om q
inte är ett primtal kommer resultat vara felaktiga.
IsPseudoprime (n,b)
Om n
är ett pseudoprimtal för basen b
men inte ett primtal, det vill säga om b^(n-1) == 1 mod n
. Detta anropar PseudoprimeTest
IsStrongPseudoprime (n,b)
Testa om n
är ett starkt pseudoprimtal för basen b
men inte ett primtal.
Jacobi (a,b)
Alias: JacobiSymbol
Beräkna Jacobi-symbolen (a/b) (b måste vara udda).
JacobiKronecker (a,b)
Alias: JacobiKroneckerSymbol
Beräkna Jacobi-symbolen (a/b) med Kronecker-tillägget (a/2)=(2/a) när a är udda, eller (a/2)=0 när a är jämnt.
LeastAbsoluteResidue (a,n)
Returnera residualen av a
mod n
med det minsta absolutbeloppet (i intervallet -n/2 till n/2).
Legendre (a,p)
Alias: LegendreSymbol
Beräkna Legendre-symbolen (a/p).
Se Planetmath eller Mathworld för mer information.
LucasLehmer (p)
Testa om 2p-1 är ett Mersenne-primtal med Lucas-Lehmer-testet. Se även MersennePrimeExponents och IsMersennePrimeExponent.
Se Wikipedia, Planetmath eller Mathworld för mer information.
LucasNumber (n)
Returnerar det n
:e Lucas-talet.
Se Wikipedia, Planetmath eller Mathworld för mer information.
MaximalPrimePowerFactors (n)
Returnera alla maximala potenser av primtalsfaktorer för ett tal.
MersennePrimeExponents
En vektor av kända Mersenne-primtalsexponenter, det vill säga en lista över positiva heltal p
så att 2p-1 är ett primtal. Se även IsMersennePrimeExponent och LucasLehmer.
Se Wikipedia, Planetmath, Mathworld eller GIMPS för mer 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.
Se Wikipedia eller Planetmath eller Mathworld för mer information.
MillerRabinTestSure (n)
Använd Miller-Rabin-primalitetstestet på n
med tillräckliga baser för att, givet den allmänna Riemann-hypotesen, resultatet ska vara deterministiskt.
Se Wikipedia, Planetmath eller Mathworld för mer information.
ModInvert (n,m)
Returnerar inversen av n mod m.
Se Mathworld för mer information.
MoebiusMu (n)
Returnera Möbiusfunktionen µ(n) beräknad i n
. Det vill säga, returnerar 0 om n
inte är en produkt av distinkta primtal och (-1)^k
om det är en produkt av k
distinkta primtal.
Se Planetmath eller Mathworld för mer information.
NextPrime (n)
Returnerar det minsta primtalet större än n
. Negativer av primtal anses vara primtal så för att få det föregående primtalet kan du använda -NextPrime(-n)
.
Denna funktion använder GMP:s mpz_nextprime
, som i sin tur använder det probabilistiska Miller-Rabin-testet (Se även MillerRabinTest
). Sannolikheten för att få falska positiva går inte att ställa in, men är låg nog för alla praktiska användningsområden.
Se Planetmath eller Mathworld för mer information.
PadicValuation (n,p)
Returnera den p-adiska beräkningen (antal efterföljande nollor i bas p
).
Se Wikipedia eller Planetmath för mer information.
PowerMod (a,b,m)
Beräkna a^b mod m
. b
-potensen av a
modulo m
. Det är inte nödvändigt att använda denna funktion eftersom den används automatiskt i moduloläge. Därför går a^b mod m
precis lika snabbt.
Prime (n)
Alias: prime
Returnera det n
:e primtalet (upp till en gräns).
Se Planetmath eller Mathworld för mer information.
PrimeFactors (n)
Returnera alla primtalsfaktorer för ett tal som en vektor.
PseudoprimeTest (n,b)
Pseudoprime test, returns true
if and only if
b^(n-1) == 1 mod n
Se Planetmath eller Mathworld för mer information.
RemoveFactor (n,m)
Tar bort alla förekomster av faktorn m
från talet n
. Det vill säga dividerar med den största potensen av m
som delar n
.
Se Planetmath eller Mathworld för mer information.
SilverPohligHellmanWithFactorization (n,b,q,f)
Hitta diskret logaritm av n
bas b
i Fq, den finita gruppen av ordning q
, där q
är ett primtal med Silver-Pohlig-Hellman-algoritmen, givet att f
är faktoriseringen av q
-1.
SqrtModPrime (n,p)
Hitta kvadratrot av n
mod p
(där p
är ett primtal). Null returneras om inte en kvadratisk rest.
Se Planetmath eller Mathworld för mer information.
StrongPseudoprimeTest (n,b)
Kör det starka pseudoprimtalstestet bas b
på n
.
Se Wikipedia, Planetmath eller Mathworld för mer information.
gcd (a,arg...)
Alias: GCD
Största gemensamma delare av heltal. Du kan mata in så många heltal som du vill i argumentlistan, eller så kan du ange en vektor eller en matris av heltal. Om du anger mer än en matris av samma storlek kommer SGD att utföras elementvis.
Se Wikipedia, Planetmath eller Mathworld för mer information.
lcm (a,arg...)
Alias: LCM
Minsta gemensamma multipel av heltal. Du kan mata in så många heltal som du vill i argumentlistan, eller så kan du ange en vektor eller en matris av heltal. Om du anger mer än en matris av samma storlek kommer MGM att utföras elementvis.
Se Wikipedia, Planetmath eller Mathworld för mer information.