# Ring of Integers

- [Introduction](introduction.md)

  - [Representation](introduction.md#representation)

  - [Coercion](introduction.md#coercion)

  - [Homomorphisms](introduction.md#homomorphisms)

    - [`hom< Z -> R | >: RngInt, Rng → Map`](introduction.md#constructor-constructor-hom-rngint-rng-map)

    - [`Example: hom`](introduction.md#example-ex-a58966)

- [Creation Functions](creation.md)

  - [Creation of Structures](creation.md#creation-of-structures)

    - [`IntegerRing() → RngInt`](creation.md#function-integerring)

    - [`Integers() → RngInt`](creation.md#function-integers)

    - [`RingOfIntegers() → RngInt`](creation.md#function-ringofintegers)

    - [`IntegerRing(Q): FldRat → RngInt`](creation.md#function-integerring-fldrat)

    - [`Integers(Q): FldRat → RngInt`](creation.md#function-integers-fldrat)

    - [`RingOfIntegers(Q): FldRat → RngInt`](creation.md#function-ringofintegers-fldrat)

  - [Creation of Elements](creation.md#creation-of-elements)

    - [`a₁a₂...aᵣ`](creation.md#literal-literal-integer-literal-a1a2-ar)

    - [`0xa₁a₂...aᵣ`](creation.md#literal-literal-integer-literal-hexadecimal-0xa1a2-ar)

    - [`elt< Z | a₁a₂...aᵣ >: RngInt, RngIntElt → RngIntElt`](creation.md#constructor-constructor-elt-rngint-rngintelt-rngintelt)

    - [`elt< Z | 0xa₁a₂...aᵣ >: RngInt, RngIntElt → RngIntElt`](creation.md#constructor-constructor-elt-rngint-rngintelt-rngintelt-2)

    - [`Z ! a: RngInt, RngElt → RngIntElt`](creation.md#operation-op-rngint-rngelt)

    - [`Z ! [a]: RngInt, [RngElt] → RngIntElt`](creation.md#operation-op-rngint-rngelt-2)

    - [`Example: Integers`](creation.md#example-ex-2fa3b0)

    - [`One(Z): RngInt → RngIntElt`](creation.md#function-one-rngint)

    - [`Identity(Z): RngInt → RngIntElt`](creation.md#function-identity-rngint)

    - [`Zero(Z): RngInt → RngIntElt`](creation.md#function-zero-rngint)

    - [`Representative(Z): RngInt → RngIntElt`](creation.md#function-representative-rngint)

  - [Printing of Elements](creation.md#printing-of-elements)

    - [`Example: Printing`](creation.md#example-ex-47136f)

  - [Element Conversions](creation.md#element-conversions)

    - [`FactorizationToInteger(s): [ <RngIntElt, RngIntElt> ] → RngIntElt`](creation.md#function-factorizationtointeger-rngintelt-rngintelt)

    - [`FactorisationToInteger(s): [ <RngIntElt, RngIntElt> ] → RngIntElt`](creation.md#function-factorisationtointeger-rngintelt-rngintelt)

    - [`Facint(s): [ <RngIntElt, RngIntElt> ] → RngIntElt`](creation.md#function-facint-rngintelt-rngintelt)

    - [`IntegerToSequence(n, b): RngIntElt, RngIntElt → [RngIntElt]`](creation.md#function-integertosequence-rngintelt-rngintelt)

    - [`Intseq(n, b): RngIntElt, RngIntElt → [RngIntElt]`](creation.md#function-intseq-rngintelt-rngintelt)

    - [`SequenceToInteger(s, b): [RngIntElt], RngIntElt → RngIntElt`](creation.md#function-sequencetointeger-rngintelt-rngintelt)

    - [`Seqint(s, b): [RngIntElt], RngIntElt → RngIntElt`](creation.md#function-seqint-rngintelt-rngintelt)

    - [`IntegerToString(n): RngIntElt → ModStgElt`](creation.md#function-integertostring-rngintelt)

    - [`IntegerToString(n, b): RngIntElt, RngIntElt → ModStgElt`](creation.md#function-integertostring-rngintelt-rngintelt)

    - [`Eltseq(n): RngIntElt → [RngIntElt]`](creation.md#function-eltseq-rngintelt)

    - [`Denominator(n): RngIntElt → RngIntElt`](creation.md#function-denominator-rngintelt)

- [Structure Operations](operation.md)

  - [Related Structures](operation.md#related-structures)

    - [`Category(Z): RngInt → Cat`](operation.md#function-category-rngint)

    - [`Parent(Z): RngInt → PowerStructure`](operation.md#function-parent-rngint)

    - [`PrimeRing(Z): RngInt → RngInt`](operation.md#function-primering-rngint)

    - [`Center(Z): RngInt → RngInt`](operation.md#function-center-rngint)

    - [`AdditiveGroup(Z): RngInt → GrpAb, Map`](operation.md#function-additivegroup-rngint)

    - [`MultiplicativeGroup(Z): RngInt → GrpAb, Map`](operation.md#function-multiplicativegroup-rngint)

    - [`UnitGroup(Z): RngInt → GrpAb, Map`](operation.md#function-unitgroup-rngint)

    - [`ClassGroup(Z): RngInt → GrpAb, Map`](operation.md#function-classgroup-rngint)

    - [`FieldOfFractions(Z): RngInt → FldRat`](operation.md#function-fieldoffractions-rngint)

    - [`sub< Z | n >: RngInt, RngIntElt → RngInt`](operation.md#constructor-constructor-sub-rngint-rngintelt-rngint)

  - [Numerical Invariants](operation.md#numerical-invariants)

    - [`Characteristic(Z): RngInt → RngIntElt`](operation.md#function-characteristic-rngint)

    - [`Signature(Z): RngInt → RngIntElt, RngIntElt`](operation.md#function-signature-rngint)

  - [Ring Predicates and Booleans](operation.md#ring-predicates-and-booleans)

    - [`IsCommutative(Z): RngInt → BoolElt`](operation.md#function-iscommutative-rngint)

    - [`IsUnitary(Z): RngInt → BoolElt`](operation.md#function-isunitary-rngint)

    - [`IsFinite(Z): RngInt → BoolElt`](operation.md#function-isfinite-rngint)

    - [`IsOrdered(Z): RngInt → BoolElt`](operation.md#function-isordered-rngint)

    - [`IsField(Z): RngInt → BoolElt`](operation.md#function-isfield-rngint)

    - [`IsEuclideanDomain(Z): RngInt → BoolElt`](operation.md#function-iseuclideandomain-rngint)

    - [`IsPID(Z): RngInt → BoolElt`](operation.md#function-ispid-rngint)

    - [`IsUFD(Z): RngInt → BoolElt`](operation.md#function-isufd-rngint)

    - [`IsDivisionRing(Z): RngInt → BoolElt`](operation.md#function-isdivisionring-rngint)

    - [`IsEuclideanRing(Z): RngInt → BoolElt`](operation.md#function-iseuclideanring-rngint)

    - [`IsPrincipalIdealRing(Z): RngInt → BoolElt`](operation.md#function-isprincipalidealring-rngint)

    - [`IsDomain(Z): RngInt → BoolElt`](operation.md#function-isdomain-rngint)

    - [`Z eq R: RngInt, Rng → BoolElt`](operation.md#operation-op-eq-rngint-rng)

    - [`Z ne R: RngInt, Rng → BoolElt`](operation.md#operation-op-ne-rngint-rng)

- [Element Operations](operation-element.md)

  - [Arithmetic Operations](operation-element.md#arithmetic-operations)

    - [`+ n: RngIntElt → RngIntElt`](operation-element.md#operation-operation-rngintelt-rngintelt)

    - [`- n: RngIntElt → RngIntElt`](operation-element.md#operation-operation-rngintelt-rngintelt-2)

    - [`m + n: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-op-plus-rngintelt-rngintelt)

    - [`m - n: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-op-minus-rngintelt-rngintelt)

    - [`m * n: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-op-times-rngintelt-rngintelt)

    - [`n ^ k: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-op-pow-rngintelt-rngintelt)

    - [`m / n: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-op-div-rngintelt-rngintelt)

    - [`m +:= n: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-operation-rngintelt-rngintelt-rngintelt)

    - [`m -:= n: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-operation-rngintelt-rngintelt-rngintelt-2)

    - [`m *:= n: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-operation-rngintelt-rngintelt-rngintelt-3)

    - [`m /:= n: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-operation-rngintelt-rngintelt-rngintelt-4)

    - [`m ^:= k: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-operation-rngintelt-rngintelt-rngintelt-5)

    - [`n div m: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-operation-div-rngintelt-rngintelt-rngintelt)

    - [`n mod m: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-operation-mod-rngintelt-rngintelt-rngintelt)

    - [`ExactQuotient(n, d): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-exactquotient-rngintelt-rngintelt)

    - [`n div:= m: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-operation-div-rngintelt-rngintelt-rngintelt-2)

    - [`n mod:= m: RngIntElt, RngIntElt → RngIntElt`](operation-element.md#operation-operation-mod-rngintelt-rngintelt-rngintelt-2)

  - [Bit Operations](operation-element.md#bit-operations)

    - [`ShiftLeft(n, b): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-shiftleft-rngintelt-rngintelt)

    - [`ShiftRight(n, b): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-shiftright-rngintelt-rngintelt)

    - [`ModByPowerOf2(n, b): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-modbypowerof2-rngintelt-rngintelt)

  - [Bitwise Operations](operation-element.md#bitwise-operations)

    - [`BitwiseNot(x): RngIntElt → RngIntElt`](operation-element.md#function-bitwisenot-rngintelt)

    - [`BitwiseAnd(x, y): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-bitwiseand-rngintelt-rngintelt)

    - [`BitwiseOr(x, y): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-bitwiseor-rngintelt-rngintelt)

    - [`BitwiseXor(x, y): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-bitwisexor-rngintelt-rngintelt)

  - [Equality and Membership](operation-element.md#equality-and-membership)

    - [`m eq n: RngIntElt, RngIntElt → BoolElt`](operation-element.md#operation-op-eq-rngintelt-rngintelt)

    - [`m ne n: RngIntElt, RngIntElt → BoolElt`](operation-element.md#operation-op-ne-rngintelt-rngintelt)

    - [`n in R: RngIntElt, Rng → BoolElt`](operation-element.md#operation-op-in-rngintelt-rng)

    - [`n notin R: RngIntElt, Rng → BoolElt`](operation-element.md#operation-op-notin-rngintelt-rng)

  - [Parent and Category](operation-element.md#parent-and-category)

    - [`Parent(n): RngIntElt → RngInt`](operation-element.md#function-parent-rngintelt)

    - [`Category(n): RngIntElt → Cat`](operation-element.md#function-category-rngintelt)

  - [Predicates on Ring Elements](operation-element.md#predicates-on-ring-elements)

    - [`IsEven(n): RngIntElt → BoolElt`](operation-element.md#function-iseven-rngintelt)

    - [`IsOdd(n): RngIntElt → BoolElt`](operation-element.md#function-isodd-rngintelt)

    - [`IsDivisibleBy(n, d): RngIntElt, RngIntElt → BoolElt, RngIntElt`](operation-element.md#function-isdivisibleby-rngintelt-rngintelt)

    - [`IsSquare(n): RngIntElt → BoolElt, RngIntElt`](operation-element.md#function-issquare-rngintelt)

    - [`IsSquarefree(n): RngIntElt → BoolElt`](operation-element.md#function-issquarefree-rngintelt)

    - [`IsPower(n): RngIntElt → BoolElt`](operation-element.md#function-ispower-rngintelt)

    - [`IsPower(n, k): RngIntElt, RngIntElt → BoolElt`](operation-element.md#function-ispower-rngintelt-rngintelt)

    - [`IsPrime(n): RngIntElt → BoolElt`](operation-element.md#function-isprime-rngintelt)

    - [`Example: Is Prime`](operation-element.md#example-ex-687a13)

    - [`IsIntegral(n): RngIntElt → BoolElt`](operation-element.md#function-isintegral-rngintelt)

    - [`IsSinglePrecision(n): RngIntElt → BoolElt`](operation-element.md#function-issingleprecision-rngintelt)

    - [`IsZero(n): RngIntElt → BoolElt`](operation-element.md#function-iszero-rngintelt)

    - [`IsOne(n): RngIntElt → BoolElt`](operation-element.md#function-isone-rngintelt)

    - [`IsMinusOne(n): RngIntElt → BoolElt`](operation-element.md#function-isminusone-rngintelt)

    - [`IsNilpotent(n): RngIntElt → BoolElt`](operation-element.md#function-isnilpotent-rngintelt)

    - [`IsIdempotent(n): RngIntElt → BoolElt`](operation-element.md#function-isidempotent-rngintelt)

    - [`IsUnit(n): RngIntElt → BoolElt`](operation-element.md#function-isunit-rngintelt)

    - [`IsZeroDivisor(n): RngIntElt → BoolElt`](operation-element.md#function-iszerodivisor-rngintelt)

    - [`IsRegular(n): RngInt → BoolElt`](operation-element.md#function-isregular-rngint)

    - [`IsIrreducible(n): RngIntElt → BoolElt`](operation-element.md#function-isirreducible-rngintelt)

    - [`IsPrime(n): RngIntElt → BoolElt`](operation-element.md#function-isprime-rngintelt-2)

  - [Comparison of Ring Elements](operation-element.md#comparison-of-ring-elements)

    - [`m gt n: RngIntElt, RngIntElt → BoolElt`](operation-element.md#operation-op-gt-rngintelt-rngintelt)

    - [`m ge n: RngIntElt, RngIntElt → BoolElt`](operation-element.md#operation-op-ge-rngintelt-rngintelt)

    - [`m lt n: RngIntElt, RngIntElt → BoolElt`](operation-element.md#operation-op-lt-rngintelt-rngintelt)

    - [`m le n: RngIntElt, RngIntElt → BoolElt`](operation-element.md#operation-op-le-rngintelt-rngintelt)

    - [`Maximum(m, n): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-maximum-rngintelt-rngintelt)

    - [`Maximum(Q): [RngIntElt] → RngIntElt`](operation-element.md#function-maximum-rngintelt)

    - [`Minimum(m, n): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-minimum-rngintelt-rngintelt)

    - [`Minimum(Q): [RngIntElt] → RngIntElt`](operation-element.md#function-minimum-rngintelt)

  - [Conjugates, Norm and Trace](operation-element.md#conjugates-norm-and-trace)

    - [`ComplexConjugate(n): RngIntElt → RngIntElt`](operation-element.md#function-complexconjugate-rngintelt)

    - [`Conjugate(n): RngIntElt → RngIntElt`](operation-element.md#function-conjugate-rngintelt)

    - [`Norm(n): RngIntElt → RngIntElt`](operation-element.md#function-norm-rngintelt)

    - [`EuclideanNorm(n): RngIntElt → RngIntElt`](operation-element.md#function-euclideannorm-rngintelt)

    - [`Trace(n): RngIntElt → RngIntElt`](operation-element.md#function-trace-rngintelt)

    - [`MinimalPolynomial(n): RngIntElt → RngUPolElt`](operation-element.md#function-minimalpolynomial-rngintelt)

  - [Other Elementary Functions](operation-element.md#other-elementary-functions)

    - [`AbsoluteValue(n): RngIntElt → RngIntElt`](operation-element.md#function-absolutevalue-rngintelt)

    - [`Abs(n): RngIntElt → RngIntElt`](operation-element.md#function-abs-rngintelt)

    - [`Ilog2(n): RngIntElt → RngIntElt`](operation-element.md#function-ilog2-rngintelt)

    - [`Ilog(b, n): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-ilog-rngintelt-rngintelt)

    - [`Quotrem(m, n): RngIntElt, RngIntElt → RngIntElt, RngIntElt`](operation-element.md#function-quotrem-rngintelt-rngintelt)

    - [`Valuation(x, p): RngIntElt, RngIntElt → RngIntElt, RngIntElt`](operation-element.md#function-valuation-rngintelt-rngintelt)

    - [`Iroot(a, n): RngIntElt, RngIntElt → RngIntElt`](operation-element.md#function-iroot-rngintelt-rngintelt)

    - [`Sign(n): RngIntElt → RngIntElt`](operation-element.md#function-sign-rngintelt)

    - [`Ceiling(n): RngIntElt → RngIntElt`](operation-element.md#function-ceiling-rngintelt)

    - [`Floor(n): RngIntElt → RngIntElt`](operation-element.md#function-floor-rngintelt)

    - [`Round(n): RngIntElt → RngIntElt`](operation-element.md#function-round-rngintelt)

    - [`Truncate(n): RngIntElt → RngIntElt`](operation-element.md#function-truncate-rngintelt)

    - [`SquarefreeFactorization(n): RngIntElt → RngIntElt, RngIntElt`](operation-element.md#function-squarefreefactorization-rngintelt)

    - [`Isqrt(n): RngIntElt → RngIntElt`](operation-element.md#function-isqrt-rngintelt)

- [Random Numbers](random.md)

  - [`Random(a, b): RngIntElt, RngIntElt → RngIntElt`](random.md#function-random-rngintelt-rngintelt)

  - [`Random(b): RngIntElt → RngIntElt`](random.md#function-random-rngintelt)

  - [`RandomBits(n): RngIntElt → RngIntElt`](random.md#function-randombits-rngintelt)

  - [`RandomPrime(n: parameter): RngIntElt → RngIntElt`](random.md#function-randomprime-rngintelt)

  - [`RandomPrime(n, a, b, x: parameter): RngIntElt, RngIntElt, RngIntElt → BoolElt, RngIntElt`](random.md#function-randomprime-rngintelt-rngintelt-rngintelt)

  - [`RandomConsecutiveBits(n, a, b): RngIntElt, RngIntElt → RngIntElt`](random.md#function-randomconsecutivebits-rngintelt-rngintelt)

- [GCD and LCM](gcd-lcm.md)

  - [`GreatestCommonDivisor(m, n): RngIntElt, RngIntElt → RngIntElt`](gcd-lcm.md#function-greatestcommondivisor-rngintelt-rngintelt)

  - [`Gcd(m, n): RngIntElt, RngIntElt → RngIntElt`](gcd-lcm.md#function-gcd-rngintelt-rngintelt)

  - [`GCD(m, n): RngIntElt, RngIntElt → RngIntElt`](gcd-lcm.md#function-gcd-rngintelt-rngintelt-2)

  - [`GreatestCommonDivisor(s): [RngIntElt] → RngIntElt`](gcd-lcm.md#function-greatestcommondivisor-rngintelt)

  - [`Gcd(s): [RngIntElt] → RngIntElt`](gcd-lcm.md#function-gcd-rngintelt)

  - [`GCD(s): [RngIntElt] → RngIntElt`](gcd-lcm.md#function-gcd-rngintelt-2)

  - [`ExtendedGreatestCommonDivisor(m, n): RngIntElt, RngIntElt → RngIntElt, RngIntElt, RngIntElt`](gcd-lcm.md#function-extendedgreatestcommondivisor-rngintelt-rngintelt)

  - [`Xgcd(m, n): RngIntElt, RngIntElt → RngIntElt, RngIntElt, RngIntElt`](gcd-lcm.md#function-xgcd-rngintelt-rngintelt)

  - [`XGCD(m, n): RngIntElt, RngIntElt → RngIntElt, RngIntElt, RngIntElt`](gcd-lcm.md#function-xgcd-rngintelt-rngintelt-2)

  - [`ExtendedGreatestCommonDivisor(s): [RngIntElt] → RngIntElt, [RngIntElt]`](gcd-lcm.md#function-extendedgreatestcommondivisor-rngintelt)

  - [`Xgcd(s): [RngIntElt] → RngIntElt, [RngIntElt]`](gcd-lcm.md#function-xgcd-rngintelt)

  - [`XGCD(s): [RngIntElt] → RngIntElt, [RngIntElt]`](gcd-lcm.md#function-xgcd-rngintelt-2)

  - [`LeastCommonMultiple(m, n): RngIntElt, RngIntElt → RngIntElt`](gcd-lcm.md#function-leastcommonmultiple-rngintelt-rngintelt)

  - [`Lcm(m, n): RngIntElt, RngIntElt → RngIntElt`](gcd-lcm.md#function-lcm-rngintelt-rngintelt)

  - [`LCM(m, n): RngIntElt, RngIntElt → RngIntElt`](gcd-lcm.md#function-lcm-rngintelt-rngintelt-2)

  - [`LeastCommonMultiple(s): [RngIntElt] → RngIntElt`](gcd-lcm.md#function-leastcommonmultiple-rngintelt)

  - [`Lcm(s): [RngIntElt] → RngIntElt`](gcd-lcm.md#function-lcm-rngintelt)

  - [`LCM(s): [RngIntElt] → RngIntElt`](gcd-lcm.md#function-lcm-rngintelt-2)

- [Arithmetic Functions](arithmetic-function.md)

  - [`CarmichaelLambda(n): RngIntElt → RngIntElt`](arithmetic-function.md#function-carmichaellambda-rngintelt)

  - [`CarmichaelLambda(Q): RngIntEltFact → RngIntElt`](arithmetic-function.md#function-carmichaellambda-rnginteltfact)

  - [`CarmichaelLambda(Q): [Tup] → RngIntElt`](arithmetic-function.md#function-carmichaellambda-tup)

  - [`DickmanRho(u): FldReElt → FldReElt`](arithmetic-function.md#function-dickmanrho-fldreelt)

  - [`FactoredCarmichaelLambda(n): RngIntElt → RngIntEltFact`](arithmetic-function.md#function-factoredcarmichaellambda-rngintelt)

  - [`FactoredCarmichaelLambda(Q): RngIntEltFact → RngIntEltFact`](arithmetic-function.md#function-factoredcarmichaellambda-rnginteltfact)

  - [`FactoredCarmichaelLambda(Q): [Tup] → RngIntEltFact`](arithmetic-function.md#function-factoredcarmichaellambda-tup)

  - [`DivisorSigma(i, n): RngIntElt, RngIntElt → RngIntElt`](arithmetic-function.md#function-divisorsigma-rngintelt-rngintelt)

  - [`DivisorSigma(i, Q): RngIntElt, RngIntEltFact → RngIntElt`](arithmetic-function.md#function-divisorsigma-rngintelt-rnginteltfact)

  - [`NumberOfDivisors(n): RngIntElt → RngIntElt`](arithmetic-function.md#function-numberofdivisors-rngintelt)

  - [`NumberOfDivisors(Q): RngIntEltFact → RngIntElt`](arithmetic-function.md#function-numberofdivisors-rnginteltfact)

  - [`SumOfDivisors(n): RngIntElt → RngIntElt`](arithmetic-function.md#function-sumofdivisors-rngintelt)

  - [`SumOfDivisors(Q): RngIntEltFact → RngIntElt`](arithmetic-function.md#function-sumofdivisors-rnginteltfact)

  - [`EulerPhi(n): RngIntElt → RngIntElt`](arithmetic-function.md#function-eulerphi-rngintelt)

  - [`EulerPhi(Q): RngIntEltFact → RngIntElt`](arithmetic-function.md#function-eulerphi-rnginteltfact)

  - [`EulerPhi(Q): [Tup] → RngIntElt`](arithmetic-function.md#function-eulerphi-tup)

  - [`FactoredEulerPhi(n): RngIntElt → RngIntEltFact`](arithmetic-function.md#function-factoredeulerphi-rngintelt)

  - [`FactoredEulerPhi(Q): RngIntEltFact → RngIntEltFact`](arithmetic-function.md#function-factoredeulerphi-rnginteltfact)

  - [`FactoredEulerPhi(Q): [Tup] → RngIntEltFact`](arithmetic-function.md#function-factoredeulerphi-tup)

  - [`EulerPhiInverse(m): RngIntElt → RngIntElt`](arithmetic-function.md#function-eulerphiinverse-rngintelt)

  - [`EulerPhiInverse(Q): RngIntEltFact → RngIntElt`](arithmetic-function.md#function-eulerphiinverse-rnginteltfact)

  - [`FactoredEulerPhiInverse(n): RngIntElt → RngIntEltFact`](arithmetic-function.md#function-factoredeulerphiinverse-rngintelt)

  - [`FactoredEulerPhiInverse(Q): RngIntEltFact → RngIntEltFact`](arithmetic-function.md#function-factoredeulerphiinverse-rnginteltfact)

  - [`LegendreSymbol(n, m): RngIntElt, RngIntElt → RngIntElt`](arithmetic-function.md#function-legendresymbol-rngintelt-rngintelt)

  - [`JacobiSymbol(n, m): RngIntElt, RngIntElt → RngIntElt`](arithmetic-function.md#function-jacobisymbol-rngintelt-rngintelt)

  - [`KroneckerSymbol(n, m): RngIntElt, RngIntElt → RngIntElt`](arithmetic-function.md#function-kroneckersymbol-rngintelt-rngintelt)

  - [`MoebiusMu(n): RngIntElt → RngIntElt`](arithmetic-function.md#function-moebiusmu-rngintelt)

  - [`MoebiusMu(Q): RngIntEltFact → RngIntElt`](arithmetic-function.md#function-moebiusmu-rnginteltfact)

  - [`Example: Amicable`](arithmetic-function.md#example-ex-233f46)

- [Combinatorial Functions](combinatorics.md)

  - [`Binomial(n, r): RngIntElt, RngIntElt → RngIntElt`](combinatorics.md#function-binomial-rngintelt-rngintelt)

  - [`Multinomial(n, [r₁, ... rₙ]): RngIntElt, [RngIntElt] → RngIntElt`](combinatorics.md#function-multinomial-rngintelt-rngintelt)

  - [`Factorial(n): RngIntElt → RngIntElt`](combinatorics.md#function-factorial-rngintelt)

  - [`IsFactorial(n): RngIntElt → BoolElt, RngIntElt`](combinatorics.md#function-isfactorial-rngintelt)

  - [`Partitions(n): RngIntElt → [ [ RngIntElt ] ]`](combinatorics.md#function-partitions-rngintelt)

  - [`NumberOfPartitions(n): RngIntElt → RngIntElt`](combinatorics.md#function-numberofpartitions-rngintelt)

  - [`RestrictedPartitions(n, M): RngIntElt, SetEnum → [ [ RngIntElt ] ]`](combinatorics.md#function-restrictedpartitions-rngintelt-setenum)

  - [`RestrictedPartitions(n, k, M): RngIntElt, RngIntElt, SetEnum → [ [ RngIntElt ] ]`](combinatorics.md#function-restrictedpartitions-rngintelt-rngintelt-setenum)

  - [`StirlingFirst(n, k): RngIntElt, RngIntElt → RngIntElt`](combinatorics.md#function-stirlingfirst-rngintelt-rngintelt)

  - [`StirlingSecond(n, k): RngIntElt, RngIntElt → RngIntElt`](combinatorics.md#function-stirlingsecond-rngintelt-rngintelt)

  - [`Bell(n): RngIntElt → RngIntElt`](combinatorics.md#function-bell-rngintelt)

  - [`Fibonacci(n): RngIntElt → RngIntElt`](combinatorics.md#function-fibonacci-rngintelt)

  - [`Lucas(n): RngIntElt → RngIntElt`](combinatorics.md#function-lucas-rngintelt)

  - [`GeneralizedFibonacciNumber(g0, g1, n): RngIntElt, RngIntElt, RngIntElt → RngIntElt`](combinatorics.md#function-generalizedfibonaccinumber-rngintelt-rngintelt-rngintelt)

- [Primes and Primality Testing](prime.md)

  - [Primality](prime.md#primality)

    - [`IsPrime(n): RngIntElt → BoolElt`](prime.md#function-isprime-rngintelt-3)

    - [`IsPrime(n: parameter): RngIntElt → BoolElt`](prime.md#function-isprime-rngintelt-4)

    - [`SetVerbose("ECPP", v): MonStgElt, Elt`](prime.md#function-setverbose-monstgelt-elt)

    - [`PrimalityCertificate(n): RngIntElt → SeqEnum`](prime.md#function-primalitycertificate-rngintelt)

    - [`CheckCertificate(cert): SeqEnum → BoolElt`](prime.md#function-checkcertificate-seqenum)

    - [`OldCertificate(cert): SeqEnum → List`](prime.md#function-oldcertificate-seqenum)

    - [`IsProbablePrime(n: parameter): RngIntElt → BoolElt`](prime.md#function-isprobableprime-rngintelt)

    - [`IsProbablyPrime(n: parameter): RngIntElt → BoolElt`](prime.md#function-isprobablyprime-rngintelt)

    - [`IsPrimePower(n): RngIntElt → BoolElt, RngIntElt, RngIntElt`](prime.md#function-isprimepower-rngintelt)

    - [`Example: Rep Units`](prime.md#example-ex-ca5938)

  - [Other Functions Relating to Primes](prime.md#other-functions-relating-to-primes)

    - [`NextPrime(n): RngIntElt → RngIntElt`](prime.md#function-nextprime-rngintelt)

    - [`NextPrime(n: parameter): RngIntElt → RngIntElt`](prime.md#function-nextprime-rngintelt-2)

    - [`PreviousPrime(n): RngIntElt → RngIntElt`](prime.md#function-previousprime-rngintelt)

    - [`PreviousPrime(n: parameter): RngIntElt → RngIntElt`](prime.md#function-previousprime-rngintelt-2)

    - [`PrimesUpTo(B): RngIntElt → [RngIntElt]`](prime.md#function-primesupto-rngintelt)

    - [`PrimesInInterval(b, e): RngIntElt, RngIntElt → [RngIntElt]`](prime.md#function-primesininterval-rngintelt-rngintelt)

    - [`NthPrime(n): RngIntElt → RngIntElt`](prime.md#function-nthprime-rngintelt)

    - [`RandomPrime(n: parameter): RngIntElt → RngIntElt`](prime.md#function-randomprime-rngintelt-2)

    - [`RandomPrime(n, a, b, x: parameter): RngIntElt, RngIntElt, RngIntElt → BoolElt, RngIntElt`](prime.md#function-randomprime-rngintelt-rngintelt-rngintelt-2)

    - [`PrimeBasis(n): RngIntElt → [RngIntElt]`](prime.md#function-primebasis-rngintelt)

    - [`PrimeDivisors(n): RngIntElt → [RngIntElt]`](prime.md#function-primedivisors-rngintelt)

- [Factorization](factor.md)

  - [General Factorization](factor.md#general-factorization)

    - [`SetVerbose("Factorization", v): MonStgElt, RngIntElt`](factor.md#function-setverbose-monstgelt-rngintelt)

    - [`Factorization(n): RngIntElt → RngIntEltFact, RngIntElt, SeqEnum`](factor.md#function-factorization-rngintelt)

    - [`Factorisation(n): RngIntElt → RngIntEltFact, RngIntElt, SeqEnum`](factor.md#function-factorisation-rngintelt)

    - [`Factorization(n: parameters): RngIntElt → RngIntEltFact, RngIntElt, SeqEnum`](factor.md#function-factorization-rngintelt-2)

    - [`Factorisation(n: parameters): RngIntElt → RngIntEltFact, RngIntElt, SeqEnum`](factor.md#function-factorisation-rngintelt-2)

  - [Storing Potential Factors](factor.md#storing-potential-factors)

    - [`StoreFactor(n): RngIntElt`](factor.md#function-storefactor-rngintelt)

    - [`StoreFactor(S): [ RngIntElt ]`](factor.md#function-storefactor-rngintelt-2)

    - [`GetStoredFactors() → [ RngIntElt ]`](factor.md#function-getstoredfactors)

    - [`ClearStoredFactors()`](factor.md#function-clearstoredfactors)

  - [Specific Factorization Algorithms](factor.md#specific-factorization-algorithms)

    - [`SetVerbose("Cunningham", b): MonStgElt, BoolElt`](factor.md#function-setverbose-monstgelt-boolelt)

    - [`SetVerbose("ECM", b): MonStgElt, Elt`](factor.md#function-setverbose-monstgelt-elt-2)

    - [`SetVerbose("MPQS", b): MonStgElt, Elt`](factor.md#function-setverbose-monstgelt-elt-3)

    - [`Cunningham(b, k, c): RngIntElt, RngIntElt, RngIntElt → SeqEnum`](factor.md#function-cunningham-rngintelt-rngintelt-rngintelt)

    - [`AssertAttribute({RngInt, }{"CunninghamStorageLimit", l}): Cat, MonStgElt, RngIntElt`](factor.md#function-assertattribute-cat-monstgelt-rngintelt)

    - [`TrialDivision(n): RngIntElt → RngIntEltFact, RngIntElt`](factor.md#function-trialdivision-rngintelt)

    - [`TrialDivision(n, B): RngIntElt, RngIntElt → RngIntEltFact, RngIntElt`](factor.md#function-trialdivision-rngintelt-rngintelt)

    - [`PollardRho(n): RngIntElt → RngIntEltFact, [ RngIntElt ]`](factor.md#function-pollardrho-rngintelt)

    - [`PollardRho(n, c, s, k): RngIntElt, RngIntElt, RngIntElt, RngIntElt → RngIntEltFact, [ RngIntElt ]`](factor.md#function-pollardrho-rngintelt-rngintelt-rngintelt-rngintelt)

    - [`pMinus1(n, B1): RngIntElt, RngIntElt → RngIntElt`](factor.md#function-pminus1-rngintelt-rngintelt)

    - [`pPlus1(n, B1): RngIntElt, RngIntElt → RngIntElt`](factor.md#function-pplus1-rngintelt-rngintelt)

    - [`SQUFOF(n): RngIntElt → RngIntEltFact, [ RngIntElt ]`](factor.md#function-squfof-rngintelt)

    - [`SQUFOF(n, k): RngIntElt, RngIntElt → RngIntEltFact, [ RngIntElt ]`](factor.md#function-squfof-rngintelt-rngintelt)

    - [`ECM(n, B1): RngIntElt, RngIntElt → RngIntElt, RngIntElt`](factor.md#function-ecm-rngintelt-rngintelt)

    - [`ECMSteps(n, L, U): RngIntElt, RngIntElt, RngIntElt → RngIntElt, RngIntElt`](factor.md#function-ecmsteps-rngintelt-rngintelt-rngintelt)

    - [`MPQS(n): RngIntElt → RngIntEltFact, [ RngIntElt ]`](factor.md#function-rngint-mpqs)

  - [Factorization Related Functions](factor.md#factorization-related-functions)

    - [`ECMOrder(p, s): RngIntElt, RngIntElt → RngIntElt`](factor.md#function-ecmorder-rngintelt-rngintelt)

    - [`ECMFactoredOrder(p, s): RngIntElt, RngIntElt → RngIntElt`](factor.md#function-ecmfactoredorder-rngintelt-rngintelt)

    - [`PrimeBasis(n): RngIntElt → [RngIntElt]`](factor.md#function-primebasis-rngintelt-2)

    - [`PrimeDivisors(n): RngIntElt → [RngIntElt]`](factor.md#function-primedivisors-rngintelt-2)

    - [`Divisors(n): RngIntElt → [ RngIntElt ]`](factor.md#function-divisors-rngintelt)

    - [`Divisors(f): RngIntEltFact → [ RngIntElt ]`](factor.md#function-divisors-rnginteltfact)

    - [`CoprimeBasis(S): [ RngIntElt ] → [ RngIntElt ]`](factor.md#function-coprimebasis-rngintelt)

    - [`CoprimeBasis(S): { RngIntElt } → [ RngIntElt ]`](factor.md#function-coprimebasis-rngintelt-2)

    - [`Example: Perfect`](factor.md#example-ex-07a3e8)

    - [`PartialFactorization(S): [ RngIntElt ] → [ RngIntEltFact ]`](factor.md#function-partialfactorization-rngintelt)

    - [`Example: Partial Fact`](factor.md#example-ex-15e5a0)

- [Factorization Sequences](factorization-sequence.md)

  - [Creation and Conversion](factorization-sequence.md#creation-and-conversion)

    - [`Facint(f): RngIntEltFact → RngIntElt`](factorization-sequence.md#function-facint-rnginteltfact)

    - [`FactorizationToInteger(f): RngIntEltFact → RngIntElt`](factorization-sequence.md#function-factorizationtointeger-rnginteltfact)

    - [`SeqFact(s): SeqEnum → RngIntEltFact`](factorization-sequence.md#function-seqfact-seqenum)

    - [`SequenceToFactorization(s): SeqEnum → RngIntEltFact`](factorization-sequence.md#function-sequencetofactorization-seqenum)

    - [`Eltseq(f): RngIntEltFact → SeqEnum`](factorization-sequence.md#function-eltseq-rnginteltfact)

    - [`ElementToSequence(f): RngIntEltFact → SeqEnum`](factorization-sequence.md#function-elementtosequence-rnginteltfact)

  - [Arithmetic](factorization-sequence.md#arithmetic)

    - [`s + t: RngIntEltFact, RngIntEltFact → RngIntEltFact`](factorization-sequence.md#operation-op-plus-rnginteltfact-rnginteltfact)

    - [`s - t: RngIntEltFact, RngIntEltFact → RngIntEltFact`](factorization-sequence.md#operation-op-minus-rnginteltfact-rnginteltfact)

    - [`s * t: RngIntEltFact, RngIntEltFact → RngIntEltFact`](factorization-sequence.md#operation-op-times-rnginteltfact-rnginteltfact)

    - [`s / t: RngIntEltFact, RngIntEltFact → RngIntEltFact`](factorization-sequence.md#operation-op-div-rnginteltfact-rnginteltfact)

    - [`s ^ k: RngIntEltFact, RngIntElt → RngIntEltFact`](factorization-sequence.md#operation-op-pow-rnginteltfact-rngintelt)

  - [Divisors](factorization-sequence.md#divisors)

    - [`Lcm(s, t): RngIntEltFact, RngIntEltFact → RngIntEltFact`](factorization-sequence.md#function-lcm-rnginteltfact-rnginteltfact)

    - [`Gcd(s, t): RngIntEltFact, RngIntEltFact → RngIntEltFact`](factorization-sequence.md#function-gcd-rnginteltfact-rnginteltfact)

    - [`SquarefreeFactorization(f): RngIntEltFact → RngIntEltFact, RngIntEltFact`](factorization-sequence.md#function-squarefreefactorization-rnginteltfact)

    - [`MoebiusMu(f): RngIntEltFact → RngIntElt`](factorization-sequence.md#function-moebiusmu-rnginteltfact-2)

    - [`Divisors(f): RngIntEltFact → SeqEnum`](factorization-sequence.md#function-divisors-rnginteltfact-2)

    - [`PrimeDivisors(f): RngIntEltFact → SeqEnum`](factorization-sequence.md#function-primedivisors-rnginteltfact)

    - [`NumberOfDivisors(f): RngIntEltFact → RngIntElt`](factorization-sequence.md#function-numberofdivisors-rnginteltfact-2)

    - [`SumOfDivisors(f): RngIntEltFact → RngIntElt`](factorization-sequence.md#function-sumofdivisors-rnginteltfact-2)

  - [Predicates](factorization-sequence.md#predicates)

    - [`IsOne(s): RngIntEltFact → BoolElt`](factorization-sequence.md#function-isone-rnginteltfact)

    - [`IsOdd(s): RngIntEltFact → BoolElt`](factorization-sequence.md#function-isodd-rnginteltfact)

    - [`IsEven(s): RngIntEltFact → BoolElt`](factorization-sequence.md#function-iseven-rnginteltfact)

    - [`IsUnit(s): RngIntEltFact → BoolElt`](factorization-sequence.md#function-isunit-rnginteltfact)

    - [`IsPrime(s): RngIntEltFact → BoolElt`](factorization-sequence.md#function-isprime-rnginteltfact)

    - [`IsPrimePower(s): RngIntEltFact → BoolElt`](factorization-sequence.md#function-isprimepower-rnginteltfact)

    - [`IsSquare(s): RngIntEltFact → BoolElt`](factorization-sequence.md#function-issquare-rnginteltfact)

    - [`IsSquarefree(s): RngIntEltFact → BoolElt`](factorization-sequence.md#function-issquarefree-rnginteltfact)

- [Modular Arithmetic](modular.md)

  - [Arithmetic Operations](modular.md#arithmetic-operations)

    - [`Modexp(n, k, m): RngIntElt, RngIntElt, RngIntElt → RngIntElt`](modular.md#function-modexp-rngintelt-rngintelt-rngintelt)

    - [`n mod m: RngIntElt, RngIntElt → RngIntElt`](modular.md#operation-operation-mod-rngintelt-rngintelt-rngintelt)

    - [`Modinv(n, m): RngIntElt, RngIntElt → RngIntElt`](modular.md#function-modinv-rngintelt-rngintelt)

    - [`InverseMod(n, m): RngIntElt, RngIntElt → RngIntElt`](modular.md#function-inversemod-rngintelt-rngintelt)

    - [`Modsqrt(n, m): RngIntElt, RngIntElt → BoolElt, RngIntElt`](modular.md#function-modsqrt-rngintelt-rngintelt)

    - [`Modorder(n, m): RngIntElt, RngIntElt → RngIntElt`](modular.md#function-modorder-rngintelt-rngintelt)

    - [`IsPrimitive(n, m): RngIntElt, RngIntElt → BoolElt`](modular.md#function-isprimitive-rngintelt-rngintelt)

    - [`PrimitiveRoot(m): RngIntElt → RngIntElt`](modular.md#function-primitiveroot-rngintelt)

  - [The Solution of Modular Equations](modular.md#the-solution-of-modular-equations)

    - [`Solution(a, b, m): RngIntElt, RngIntElt, RngIntElt → RngIntElt, RngIntElt`](modular.md#function-solution-rngintelt-rngintelt-rngintelt)

    - [`ChineseRemainderTheorem(X, N): [RngIntElt], [RngIntElt] → RngIntElt`](modular.md#function-chineseremaindertheorem-rngintelt-rngintelt)

    - [`CRT(X, N): [RngIntElt], [RngIntElt] → RngIntElt`](modular.md#function-crt-rngintelt-rngintelt)

    - [`Solution(A, B, N): [RngIntElt], [RngIntElt], [RngIntElt] → RngIntElt`](modular.md#function-solution-rngintelt-rngintelt-rngintelt-2)

    - [`NormEquation(d, m): RngIntElt, RngIntElt → BoolElt, RngIntElt, RngIntElt`](modular.md#function-normequation-rngintelt-rngintelt)

    - [`NormEquation(d, m: parameters)): RngIntElt, RngIntElt → BoolElt, RngIntElt, RngIntElt`](modular.md#function-normequation-rngintelt-rngintelt-2)

    - [`Example: Norm Equation`](modular.md#example-ex-a39523)

- [Infinities](infinity.md)

  - [Creation](infinity.md#creation)

    - [`Infinity() → Infty`](infinity.md#function-infinity)

    - [`MinusInfinity() → Infty`](infinity.md#function-minusinfinity)

  - [Arithmetic](infinity.md#arithmetic)

    - [`- x: Infty → Infty`](infinity.md#operation-operation-infty-infty)

    - [`x + y: Infty, Infty → Infty`](infinity.md#operation-op-plus-infty-infty)

    - [`x + y: Infty, RngIntElt → Infty`](infinity.md#operation-op-plus-infty-rngintelt)

    - [`x + y: RngIntElt, Infty → Infty`](infinity.md#operation-op-plus-rngintelt-infty)

    - [`x - y: Infty, Infty → Infty`](infinity.md#operation-op-minus-infty-infty)

    - [`x - y: Infty, RngIntElt → Infty`](infinity.md#operation-op-minus-infty-rngintelt)

    - [`x - y: RngIntElt, Infty → Infty`](infinity.md#operation-op-minus-rngintelt-infty)

    - [`x * y: Infty, Infty → Infty`](infinity.md#operation-op-times-infty-infty)

    - [`x * y: Infty, RngIntElt → Infty`](infinity.md#operation-op-times-infty-rngintelt)

    - [`x * y: RngIntElt, Infty → Infty`](infinity.md#operation-op-times-rngintelt-infty)

    - [`x / y: RngIntElt, Infty → RngIntElt`](infinity.md#operation-op-div-rngintelt-infty)

    - [`x / y: Infty, RngIntElt → Infty`](infinity.md#operation-op-div-infty-rngintelt)

    - [`x ^ n: Infty, Infty → Infty`](infinity.md#operation-op-pow-infty-infty)

    - [`x ^ n: Infty, RngIntElt → Infty`](infinity.md#operation-op-pow-infty-rngintelt)

  - [Comparison](infinity.md#comparison)

    - [`x eq y: Infty, Infty → BoolElt`](infinity.md#operation-op-eq-infty-infty)

    - [`x eq y: Infty, RngIntElt → BoolElt`](infinity.md#operation-op-eq-infty-rngintelt)

    - [`x eq y: RngIntElt, Infty → BoolElt`](infinity.md#operation-op-eq-rngintelt-infty)

    - [`x ne y: Infty, Infty → BoolElt`](infinity.md#operation-op-ne-infty-infty)

    - [`x ne y: Infty, RngIntElt → BoolElt`](infinity.md#operation-op-ne-infty-rngintelt)

    - [`x ne y: RngIntElt, Infty → BoolElt`](infinity.md#operation-op-ne-rngintelt-infty)

    - [`x lt y: Infty, Infty → BoolElt`](infinity.md#operation-op-lt-infty-infty)

    - [`x lt y: Infty, RngIntElt → BoolElt`](infinity.md#operation-op-lt-infty-rngintelt)

    - [`x lt y: RngIntElt, Infty → BoolElt`](infinity.md#operation-op-lt-rngintelt-infty)

    - [`x le y: Infty, Infty → BoolElt`](infinity.md#operation-op-le-infty-infty)

    - [`x le y: Infty, RngIntElt → BoolElt`](infinity.md#operation-op-le-infty-rngintelt)

    - [`x le y: RngIntElt, Infty → BoolElt`](infinity.md#operation-op-le-rngintelt-infty)

    - [`x gt y: Infty, Infty → BoolElt`](infinity.md#operation-op-gt-infty-infty)

    - [`x gt y: Infty, RngIntElt → BoolElt`](infinity.md#operation-op-gt-infty-rngintelt)

    - [`x gt y: RngIntElt, Infty → BoolElt`](infinity.md#operation-op-gt-rngintelt-infty)

    - [`x ge y: Infty, Infty → BoolElt`](infinity.md#operation-op-ge-infty-infty)

    - [`x ge y: Infty, RngIntElt → BoolElt`](infinity.md#operation-op-ge-infty-rngintelt)

    - [`x ge y: RngIntElt, Infty → BoolElt`](infinity.md#operation-op-ge-rngintelt-infty)

    - [`Maximum(x, y): Infty, Infty → .`](infinity.md#function-maximum-infty-infty)

    - [`Maximum(x, y): Infty, RngIntElt → .`](infinity.md#function-maximum-infty-rngintelt)

    - [`Maximum(x, y): RngIntElt, Infty → .`](infinity.md#function-maximum-rngintelt-infty)

    - [`Minimum(x, y): Infty, Infty → .`](infinity.md#function-minimum-infty-infty)

    - [`Minimum(x, y): Infty, RngIntElt → .`](infinity.md#function-minimum-infty-rngintelt)

    - [`Minimum(x, y): RngIntElt, Infty → .`](infinity.md#function-minimum-rngintelt-infty)

  - [Miscellaneous](infinity.md#miscellaneous)

    - [`Sign(x): Infty → RngIntElt`](infinity.md#function-sign-infty)

    - [`Abs(x): Infty → Infty`](infinity.md#function-abs-infty)

    - [`AbsoluteValue(x): Infty → Infty`](infinity.md#function-absolutevalue-infty)

    - [`Round(x): Infty → Infty`](infinity.md#function-round-infty)

    - [`Floor(x): Infty → Infty`](infinity.md#function-floor-infty)

    - [`Ceiling(x): Infty → Infty`](infinity.md#function-ceiling-infty)

    - [`IsFinite(x): Infty → BoolElt`](infinity.md#function-isfinite-infty)

    - [`IsFinite(x): RngIntElt → BoolElt`](infinity.md#function-isfinite-rngintelt)

- [Advanced Factorization Techniques: The Number Field Sieve](nfs.md)

  - [The Magma Number Field Sieve Implementation](nfs.md#the-magma-number-field-sieve-implementation)

    - [`SetVerbose("NFS", v): MonStgElt, RngIntElt`](nfs.md#function-setverbose-monstgelt-rngintelt-2)

  - [Naive NFS](nfs.md#naive-nfs)

    - [`NumberFieldSieve(n, F, m1, m2): RngIntElt, RngMPolElt, RngIntElt, RngIntElt → RngIntElt`](nfs.md#function-numberfieldsieve-rngintelt-rngmpolelt-rngintelt-rngintelt)

    - [`NFS(n, F, m1, m2): RngIntElt, RngMPolElt, RngIntElt, RngIntElt → RngIntElt`](nfs.md#function-nfs-rngintelt-rngmpolelt-rngintelt-rngintelt)

  - [Factoring with NFS Processes](nfs.md#factoring-with-nfs-processes)

    - [`NFSProcess(n, F, m1, m2): RngIntElt, RngMPolElt, RngIntElt, RngIntElt → NFSProc`](nfs.md#function-nfsprocess-rngintelt-rngmpolelt-rngintelt-rngintelt)

    - [`Example: nfsprocessparameters`](nfs.md#example-ex-53bcfa)

    - [Attribute Selection](nfs.md#attribute-selection)

      - [`Example: 70digitnfs`](nfs.md#example-ex-25ef84)

      - [`Example: 80digitnfs`](nfs.md#example-ex-9e7234)

      - [`Example: 87digitnfs`](nfs.md#example-ex-7d7073)

    - [The Sieving Stage](nfs.md#the-sieving-stage)

      - [`NumberOfRelationsRequired(P): NFSProc → RngIntElt`](nfs.md#function-numberofrelationsrequired-nfsproc)

      - [`FindRelations(P): NFSProc → RngIntElt`](nfs.md#function-findrelations-nfsproc)

    - [The Auxiliary Data Stage](nfs.md#the-auxiliary-data-stage)

      - [`CreateCycleFile(P): NFSProc → .`](nfs.md#function-createcyclefile-nfsproc)

      - [`CycleCount(P): NFSProc → RngIntElt`](nfs.md#function-cyclecount-nfsproc)

      - [`CycleCount(fn): MonStgElt → RngIntElt`](nfs.md#function-cyclecount-monstgelt)

      - [`CreateCharacterFile(P): NFSProc → .`](nfs.md#function-createcharacterfile-nfsproc)

      - [`CreateCharacterFile(P, cc): NFSProc, RngIntElt → .`](nfs.md#function-createcharacterfile-nfsproc-rngintelt)

    - [Finding Dependencies: the Linear Algebra Stage](nfs.md#finding-dependencies-the-linear-algebra-stage)

      - [`FindDependencies(P): NFSProc → .`](nfs.md#function-finddependencies-nfsproc)

    - [The Factorization Stage](nfs.md#the-factorization-stage)

      - [`Factor(P): NFSProc → RngIntElt`](nfs.md#function-factor-nfsproc)

      - [`Factor(P,k): NFSProc, RngIntElt → RngIntElt`](nfs.md#function-factor-nfsproc-rngintelt)

  - [Data Files](nfs.md#data-files)

    - [`RemoveFiles(P): NFSProc → .`](nfs.md#function-removefiles-nfsproc)

    - [`MergeFiles(S, fn): [MonStgElt], MonStgElt → RngIntElt, RngIntElt`](nfs.md#function-mergefiles-monstgelt-monstgelt)

    - [Magma Native NFS Data Files](nfs.md#magma-native-nfs-data-files)

  - [Distributing NFS Factorizations](nfs.md#distributing-nfs-factorizations)

    - [`Example: distributed`](nfs.md#example-ex-dc02d5)

  - [Magma and CWI NFS Interoperability](nfs.md#magma-and-cwi-nfs-interoperability)

    - [`FindRelationsInCWIFormat(P): NFSProc → RngIntElt`](nfs.md#function-findrelationsincwiformat-nfsproc)

    - [`ConvertToCWIFormat(P, pb): NFSProc, RngIntElt → .;`](nfs.md#function-converttocwiformat-nfsproc-rngintelt)

  - [Tools for Finding a Suitable Polynomial](nfs.md#tools-for-finding-a-suitable-polynomial)

    - [`BaseMPolynomial(n, m, d): RngIntElt, RngIntElt, RngIntElt → RngMPolElt`](nfs.md#function-basempolynomial-rngintelt-rngintelt-rngintelt)

    - [`MurphyAlphaApproximation(F, b): RngMPolElt, RngIntElt → FldReElt`](nfs.md#function-murphyalphaapproximation-rngmpolelt-rngintelt)

    - [`OptimalSkewness(F): RngMPolElt → FldReElt, FldReElt`](nfs.md#function-optimalskewness-rngmpolelt)

    - [`Example: Get Poly`](nfs.md#example-ex-112b3b)

    - [`BestTranslation(F, m, a): RngMPolElt, RngIntElt, FldReElt, FldReElt → RngMPolElt, RngIntElt, FldReElt, FldReElt`](nfs.md#function-besttranslation-rngmpolelt-rngintelt-fldreelt-fldreelt)

    - [`PolynomialSieve({F, m, J0, J1,}{MaxAlpha}): RngMPolElt, RngIntElt, RngIntElt, RngIntElt, FldReElt → List`](nfs.md#function-polynomialsieve-rngmpolelt-rngintelt-rngintelt-rngintelt-fldreelt)