Talteori
Föregående | Kapitel 11. Lista över GEL-funktioner | Nästa

## 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 `b` på `n`.

  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.

Föregående | Upp | Nästa
Trigonometri | Hem | Matrismanipulation