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 självklart bara användbart om du vet att divisionen är exakt.

Factorize
Factorize (n)

Returnera faktoriseringen av ett tal som en matris. Den första raden är primtalen i faktoriseringen (inklusive 1) och den andra raden är exponenterna. Till exempel:

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

Se Wikipedia för mer information.

Factors
Factors (n)

Returnera alla faktorer av n i en vektor. Detta inkluderar även alla icke-primtalsfaktorer. Det inkluderar 1 och talet självt. Så för att till exempel skriva ut alla perfekta tal (de som är summan av sina faktorer) upp till talet 1000 kan du göra följande (detta är förstås väldigt ineffektivt)

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 givetvis aldrig vara perfekta kvadrater av heltal.

IsPrime
IsPrime (n)

Testar om heltal är primtal. För tal mindre än 2.5e10 är svaret deterministiskt (om Riemann-hypotesen är sann). För större tal beror sannolikheten för ett falskt positivt svar på IsPrimeMillerRabinReps. Det vill säga sannolikheten för ett falskt positivt värde är 1/4 upphöjt till IsPrimeMillerRabinReps. Standardvärdet 22 ger en sannolikhet på ungefär 5.7e-14.

Om false returneras kan du vara säker på att talet är sammansatt. Om du vill vara fullständigt säker på att du har ett primtal kan du använda MillerRabinTestSure men det kan ta mycket längre tid.

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)

Använd Miller-Rabin-primalitetstestet på n, reps gånger. Sannolikheten för falska positiva är (1/4)^reps. Det är troligen vanligen bättre att använda IsPrime eftersom det är snabbare och bättre för mindre heltal.

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)

Pseudoprimtalstest, returnerar true om och endast om 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.