Talteori

AreRelativelyPrime
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
BernoulliNumber (n)

Returnerar det n:e Bernoullitalet.

Se Wikipedia eller Mathworld för mer information.

ChineseRemainder
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
CombineFactorizations (a,b)

Givet två faktoriseringar, ange faktoriseringen av produkten.

Se Factorize.

ConvertFromBase
ConvertFromBase (v,b)

Konvertera en vektor av värden som indikerar potenser av b till ett tal.

ConvertToBase
ConvertToBase (n,b)

Konvertera ett tal till en vektor av potenser för element i bas b.

DiscreteLog
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
Divides (m,n)

Kontrollerar delbarhet (om m delar n).

EulerPhi
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
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
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
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,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
FindPrimitiveElementMod (q)

Hitta det första primitiva elementet i Fq, den finita gruppen av ordning q. Givetvis måste q vara ett primtal.

FindRandomPrimitiveElementMod
FindRandomPrimitiveElementMod (q)

Hitta ett slumpmässigt primitivt element i Fq, den ändliga gruppen av ordning q (q måste vara ett primtal).

IndexCalculus
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
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
IsEven (n)

Testar om ett heltal är jämnt.

IsMersennePrimeExponent
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
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
IsOdd (n)

Testar om ett heltal är udda.

IsPerfectPower
IsPerfectPower (n)

Kontrollera om ett heltal är en perfekt potens, ab.

IsPerfectSquare
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
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
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
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
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
IsStrongPseudoprime (n,b)

Testa om n är ett starkt pseudoprimtal för basen b men inte ett primtal.

Jacobi
Jacobi (a,b)

Alias: JacobiSymbol

Beräkna Jacobi-symbolen (a/b) (b måste vara udda).

JacobiKronecker
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
LeastAbsoluteResidue (a,n)

Returnera residualen av a mod n med det minsta absolutbeloppet (i intervallet -n/2 till n/2).

Legendre
Legendre (a,p)

Alias: LegendreSymbol

Beräkna Legendre-symbolen (a/p).

Se Planetmath eller Mathworld för mer information.

LucasLehmer
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
LucasNumber (n)

Returnerar det n:e Lucas-talet.

Se Wikipedia, Planetmath eller Mathworld för mer information.

MaximalPrimePowerFactors
MaximalPrimePowerFactors (n)

Returnera alla maximala potenser av primtalsfaktorer för ett tal.

MersennePrimeExponents
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
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
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
ModInvert (n,m)

Returnerar inversen av n mod m.

Se Mathworld för mer information.

MoebiusMu
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
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
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
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
Prime (n)

Alias: prime

Returnera det n:e primtalet (upp till en gräns).

Se Planetmath eller Mathworld för mer information.

PrimeFactors
PrimeFactors (n)

Returnera alla primtalsfaktorer för ett tal som en vektor.

Se Wikipedia eller Mathworld för mer information.

PseudoprimeTest
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
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
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
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
StrongPseudoprimeTest (n,b)

Kör det starka pseudoprimtalstestet bas bn.

Se Wikipedia, Planetmath eller Mathworld för mer information.

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