Ring of Integers
- Introduction
- Creation Functions
- Creation of Structures
- Creation of Elements
- Printing of Elements
- Element Conversions
FactorizationToInteger(s): [ <RngIntElt, RngIntElt> ] → RngIntEltFactorisationToInteger(s): [ <RngIntElt, RngIntElt> ] → RngIntEltFacint(s): [ <RngIntElt, RngIntElt> ] → RngIntEltIntegerToSequence(n, b): RngIntElt, RngIntElt → [RngIntElt]Intseq(n, b): RngIntElt, RngIntElt → [RngIntElt]SequenceToInteger(s, b): [RngIntElt], RngIntElt → RngIntEltSeqint(s, b): [RngIntElt], RngIntElt → RngIntEltIntegerToString(n): RngIntElt → ModStgEltIntegerToString(n, b): RngIntElt, RngIntElt → ModStgEltEltseq(n): RngIntElt → [RngIntElt]Denominator(n): RngIntElt → RngIntElt
- Structure Operations
- Element Operations
- Arithmetic Operations
+ n: RngIntElt → RngIntElt- n: RngIntElt → RngIntEltm + n: RngIntElt, RngIntElt → RngIntEltm - n: RngIntElt, RngIntElt → RngIntEltm * n: RngIntElt, RngIntElt → RngIntEltn ^ k: RngIntElt, RngIntElt → RngIntEltm / n: RngIntElt, RngIntElt → RngIntEltm +:= n: RngIntElt, RngIntElt → RngIntEltm -:= n: RngIntElt, RngIntElt → RngIntEltm *:= n: RngIntElt, RngIntElt → RngIntEltm /:= n: RngIntElt, RngIntElt → RngIntEltm ^:= k: RngIntElt, RngIntElt → RngIntEltn div m: RngIntElt, RngIntElt → RngIntEltn mod m: RngIntElt, RngIntElt → RngIntEltExactQuotient(n, d): RngIntElt, RngIntElt → RngIntEltn div:= m: RngIntElt, RngIntElt → RngIntEltn mod:= m: RngIntElt, RngIntElt → RngIntElt
- Bit Operations
- Bitwise Operations
- Equality and Membership
- Parent and Category
- Predicates on Ring Elements
- Comparison of Ring Elements
- Conjugates, Norm, and Trace
- Other Elementary Functions
AbsoluteValue(n): RngIntElt → RngIntEltAbs(n): RngIntElt → RngIntEltIlog2(n): RngIntElt → RngIntEltIlog(b, n): RngIntElt, RngIntElt → RngIntEltQuotrem(m, n): RngIntElt, RngIntElt → RngIntElt, RngIntEltValuation(x, p): RngIntElt, RngIntElt → RngIntElt, RngIntEltIroot(a, n): RngIntElt, RngIntElt → RngIntEltSign(n): RngIntElt → RngIntEltCeiling(n): RngIntElt → RngIntEltFloor(n): RngIntElt → RngIntEltRound(n): RngIntElt → RngIntEltTruncate(n): RngIntElt → RngIntEltSquarefreeFactorization(n): RngIntElt → RngIntElt, RngIntEltIsqrt(n): RngIntElt → RngIntElt
- Random Numbers
Random(a, b): RngIntElt, RngIntElt → RngIntEltRandom(b): RngIntElt → RngIntEltRandomBits(n): RngIntElt → RngIntEltRandomPrime(n: parameter): RngIntElt → RngIntEltRandomPrime(n, a, b, x: parameter): RngIntElt, RngIntElt, RngIntElt → BoolElt, RngIntEltRandomConsecutiveBits(n, a, b): RngIntElt, RngIntElt → RngIntElt
- GCD and LCM
GreatestCommonDivisor(m, n): RngIntElt, RngIntElt → RngIntEltGcd(m, n): RngIntElt, RngIntElt → RngIntEltGCD(m, n): RngIntElt, RngIntElt → RngIntEltGreatestCommonDivisor(s): [RngIntElt] → RngIntEltGcd(s): [RngIntElt] → RngIntEltGCD(s): [RngIntElt] → RngIntEltExtendedGreatestCommonDivisor(m, n): RngIntElt, RngIntElt → RngIntElt, RngIntElt, RngIntEltXgcd(m, n): RngIntElt, RngIntElt → RngIntElt, RngIntElt, RngIntEltXGCD(m, n): RngIntElt, RngIntElt → RngIntElt, RngIntElt, RngIntEltExtendedGreatestCommonDivisor(s): [RngIntElt] → RngIntElt, [RngIntElt]Xgcd(s): [RngIntElt] → RngIntElt, [RngIntElt]XGCD(s): [RngIntElt] → RngIntElt, [RngIntElt]LeastCommonMultiple(m, n): RngIntElt, RngIntElt → RngIntEltLcm(m, n): RngIntElt, RngIntElt → RngIntEltLCM(m, n): RngIntElt, RngIntElt → RngIntEltLeastCommonMultiple(s): [RngIntElt] → RngIntEltLcm(s): [RngIntElt] → RngIntEltLCM(s): [RngIntElt] → RngIntElt
- Arithmetic Functions
CarmichaelLambda(n): RngIntElt → RngIntEltCarmichaelLambda(Q): RngIntEltFact → RngIntEltCarmichaelLambda(Q): [Tup] → RngIntEltDickmanRho(u): FldReElt → FldReEltFactoredCarmichaelLambda(n): RngIntElt → RngIntEltFactFactoredCarmichaelLambda(Q): RngIntEltFact → RngIntEltFactFactoredCarmichaelLambda(Q): [Tup] → RngIntEltFactDivisorSigma(i, n): RngIntElt, RngIntElt → RngIntEltDivisorSigma(i, Q): RngIntElt, RngIntEltFact → RngIntEltNumberOfDivisors(n): RngIntElt → RngIntEltNumberOfDivisors(Q): RngIntEltFact → RngIntEltSumOfDivisors(n): RngIntElt → RngIntEltSumOfDivisors(Q): RngIntEltFact → RngIntEltEulerPhi(n): RngIntElt → RngIntEltEulerPhi(Q): RngIntEltFact → RngIntEltEulerPhi(Q): [Tup] → RngIntEltFactoredEulerPhi(n): RngIntElt → RngIntEltFactFactoredEulerPhi(Q): RngIntEltFact → RngIntEltFactFactoredEulerPhi(Q): [Tup] → RngIntEltFactEulerPhiInverse(m): RngIntElt → RngIntEltEulerPhiInverse(Q): RngIntEltFact → RngIntEltFactoredEulerPhiInverse(n): RngIntElt → RngIntEltFactFactoredEulerPhiInverse(Q): RngIntEltFact → RngIntEltFactLegendreSymbol(n, m): RngIntElt, RngIntElt → RngIntEltJacobiSymbol(n, m): RngIntElt, RngIntElt → RngIntEltKroneckerSymbol(n, m): RngIntElt, RngIntElt → RngIntEltMoebiusMu(n): RngIntElt → RngIntEltMoebiusMu(Q): RngIntEltFact → RngIntElt- Example: Amicable Pairs of Integers
- Combinatorial Functions
Binomial(n, r): RngIntElt, RngIntElt → RngIntEltMultinomial(n, [r₁, ... rₙ]): RngIntElt, [RngIntElt] → RngIntEltFactorial(n): RngIntElt → RngIntEltIsFactorial(n): RngIntElt → BoolElt, RngIntEltPartitions(n): RngIntElt → [ [ RngIntElt ] ]NumberOfPartitions(n): RngIntElt → RngIntEltRestrictedPartitions(n, M): RngIntElt, SetEnum → [ [ RngIntElt ] ]RestrictedPartitions(n, k, M): RngIntElt, RngIntElt, SetEnum → [ [ RngIntElt ] ]StirlingFirst(n, k): RngIntElt, RngIntElt → RngIntEltStirlingSecond(n, k): RngIntElt, RngIntElt → RngIntEltBell(n): RngIntElt → RngIntEltFibonacci(n): RngIntElt → RngIntEltLucas(n): RngIntElt → RngIntEltGeneralizedFibonacciNumber(g0, g1, n): RngIntElt, RngIntElt, RngIntElt → RngIntElt
- Primes and Primality Testing
- Factorization
- General Factorization
SetVerbose("Factorization", v): MonStgElt, RngIntEltFactorization(n): RngIntElt → RngIntEltFact, RngIntElt, SeqEnumFactorisation(n): RngIntElt → RngIntEltFact, RngIntElt, SeqEnumFactorization(n: parameters): RngIntElt → RngIntEltFact, RngIntElt, SeqEnumFactorisation(n: parameters): RngIntElt → RngIntEltFact, RngIntElt, SeqEnum
- Storing Potential Factors
- Specific Factorization Algorithms
SetVerbose("Cunningham", b): MonStgElt, BoolEltSetVerbose("ECM", b): MonStgElt, EltSetVerbose("MPQS", b): MonStgElt, EltCunningham(b, k, c): RngIntElt, RngIntElt, RngIntElt → SeqEnumAssertAttribute(RngInt, "CunninghamStorageLimit", l): Cat, MonStgElt, RngIntEltTrialDivision(n): RngIntElt → RngIntEltFact, RngIntEltTrialDivision(n, B): RngIntElt, RngIntElt → RngIntEltFact, RngIntEltPollardRho(n): RngIntElt → RngIntEltFact, [ RngIntElt ]PollardRho(n, c, s, k): RngIntElt, RngIntElt, RngIntElt, RngIntElt → RngIntEltFact, [ RngIntElt ]pMinus1(n, B1): RngIntElt, RngIntElt → RngIntEltpPlus1(n, B1): RngIntElt, RngIntElt → RngIntEltSQUFOF(n): RngIntElt → RngIntEltFact, [ RngIntElt ]SQUFOF(n, k): RngIntElt, RngIntElt → RngIntEltFact, [ RngIntElt ]ECM(n, B1): RngIntElt, RngIntElt → RngIntElt, RngIntEltECMSteps(n, L, U): RngIntElt, RngIntElt, RngIntElt → RngIntElt, RngIntEltMPQS(n): RngIntElt → RngIntEltFact, [ RngIntElt ]
- Factorization Related Functions
- Factorization Sequences
- Modular Arithmetic
- Arithmetic Operations
Modexp(n, k, m): RngIntElt, RngIntElt, RngIntElt → RngIntEltn mod m: RngIntElt, RngIntElt → RngIntEltModinv(n, m): RngIntElt, RngIntElt → RngIntEltInverseMod(n, m): RngIntElt, RngIntElt → RngIntEltModsqrt(n, m): RngIntElt, RngIntElt → BoolElt, RngIntEltModorder(n, m): RngIntElt, RngIntElt → RngIntEltIsPrimitive(n, m): RngIntElt, RngIntElt → BoolEltPrimitiveRoot(m): RngIntElt → RngIntElt
- The Solution of Modular Equations
Solution(a, b, m): RngIntElt, RngIntElt, RngIntElt → RngIntElt, RngIntEltChineseRemainderTheorem(X, N): [RngIntElt], [RngIntElt] → RngIntEltCRT(X, N): [RngIntElt], [RngIntElt] → RngIntEltSolution(A, B, N): [RngIntElt], [RngIntElt], [RngIntElt] → RngIntEltNormEquation(d, m): RngIntElt, RngIntElt → BoolElt, RngIntElt, RngIntEltNormEquation(d, m: parameters)): RngIntElt, RngIntElt → BoolElt, RngIntElt, RngIntElt- Example: Norm Equation
- Infinities
- Creation
- Arithmetic
- x: Infty → Inftyx + y: Infty, Infty → Inftyx + y: Infty, RngIntElt → Inftyx + y: RngIntElt, Infty → Inftyx - y: Infty, Infty → Inftyx - y: Infty, RngIntElt → Inftyx - y: RngIntElt, Infty → Inftyx * y: Infty, Infty → Inftyx * y: Infty, RngIntElt → Inftyx * y: RngIntElt, Infty → Inftyx / y: RngIntElt, Infty → RngIntEltx / y: Infty, RngIntElt → Inftyx ^ n: Infty, Infty → Inftyx ^ n: Infty, RngIntElt → Infty
- Comparison
x eq y: Infty, Infty → BoolEltx eq y: Infty, RngIntElt → BoolEltx eq y: RngIntElt, Infty → BoolEltx ne y: Infty, Infty → BoolEltx ne y: Infty, RngIntElt → BoolEltx ne y: RngIntElt, Infty → BoolEltx lt y: Infty, Infty → BoolEltx lt y: Infty, RngIntElt → BoolEltx lt y: RngIntElt, Infty → BoolEltx le y: Infty, Infty → BoolEltx le y: Infty, RngIntElt → BoolEltx le y: RngIntElt, Infty → BoolEltx gt y: Infty, Infty → BoolEltx gt y: Infty, RngIntElt → BoolEltx gt y: RngIntElt, Infty → BoolEltx ge y: Infty, Infty → BoolEltx ge y: Infty, RngIntElt → BoolEltx ge y: RngIntElt, Infty → BoolEltMaximum(x, y): Infty, Infty → .Maximum(x, y): Infty, RngIntElt → .Maximum(x, y): RngIntElt, Infty → .Minimum(x, y): Infty, Infty → .Minimum(x, y): Infty, RngIntElt → .Minimum(x, y): RngIntElt, Infty → .
- Miscellaneous
- Advanced Factorization Techniques: The Number Field Sieve
- The Magma Number Field Sieve Implementation
- Naive NFS
NumberFieldSieve(n, F, m1, m2): RngIntElt, RngMPolElt, RngIntElt, RngIntElt → RngIntEltNFS(n, F, m1, m2): RngIntElt, RngMPolElt, RngIntElt, RngIntElt → RngIntElt
- Factoring with NFS Processes
- Data Files
- Distributing NFS Factorizations
- Magma and CWI NFS Interoperability
- Tools for Finding a Suitable Polynomial
BaseMPolynomial(n, m, d): RngIntElt, RngIntElt, RngIntElt → RngMPolEltMurphyAlphaApproximation(F, b): RngMPolElt, RngIntElt → FldReEltOptimalSkewness(F): RngMPolElt → FldReElt, FldReElt- Example: Finding a Good NFS Polynomial
BestTranslation(F, m, a): RngMPolElt, RngIntElt, FldReElt, FldReElt → RngMPolElt, RngIntElt, FldReElt, FldReEltPolynomialSieve(F, m, J0, J1, MaxAlpha): RngMPolElt, RngIntElt, RngIntElt, RngIntElt, FldReElt → List
- Bibliography