Homomorphisms
hom< Z -> R | > : RngInt, Rng -> Map
Example RngInt_hom (H40E1)
Creation of Structures
IntegerRing() : Null -> RngInt
Creation of Elements
a_1a_2...a_r : RngIntElt, ..., RngIntElt -> RngIntElt
elt< Z | a_1a_2...a_r > : RngInt, RngIntElt -> RngIntElt
Z ! a : RngInt, RngElt -> RngIntElt
Example RngInt_Integers (H40E2)
Element Conversions
FactorizationToInteger(s) : [ <RngIntElt, RngIntElt> ] -> RngIntElt
IntegerToSequence(n, b) : RngIntElt, RngIntElt -> [RngIntElt]
SequenceToInteger(s, b) : [RngIntElt], RngIntElt -> RngIntElt
IntegerToString(n) : RngIntElt -> ModStgElt
Eltseq(n) : RngIntElt -> [RngIntElt]
Related Structures
AdditiveGroup(Z) : RngInt -> GrpAb, Map
MultiplicativeGroup(Z) : RngInt -> GrpAb, Map
ClassGroup(Z) : RngInt -> GrpAb, Map
FieldOfFractions(Z) : RngInt -> FldRat
sub< Z | n > : RngInt, RngIntElt -> RngInt
Numerical Invariants
Signature(Z) : RngInt -> RngIntElt, RngIntElt
Arithmetic Operations
n div m : RngIntElt, RngIntElt -> RngIntElt
n mod m : RngIntElt, RngIntElt -> RngIntElt
ExactQuotient(n, d) : RngIntElt, RngIntElt -> RngIntElt
Predicates on Ring Elements
IsEven(n) : RngIntElt -> BoolElt
IsOdd(n) : RngIntElt -> BoolElt
IsDivisibleBy(n, d) : RngIntElt, RngIntElt -> BoolElt, RngIntElt
IsSquare(n) : RngIntElt -> BoolElt, RngIntElt
IsSquarefree(n) : RngIntElt -> BoolElt
IsPower(n) : RngIntElt -> BoolElt
IsPower(n, k) : RngIntElt -> BoolElt
IsPrime(n) : RngIntElt -> BoolElt
Example RngInt_IsPrime (H40E3)
IsIntegral(n) : RngIntElt -> BoolElt
IsSinglePrecision(n) : RngIntElt -> BoolElt
Conjugates, Norm and Trace
ComplexConjugate(n) : RngIntElt -> RngIntElt
Conjugate(n) : RngIntElt -> RngIntElt
Norm(n) : RngIntElt -> RngIntElt
EuclideanNorm(n) : RngIntElt -> RngIntElt
Trace(n) : RngIntElt -> RngIntElt
MinimalPolynomial(n) : RngIntElt -> RngUPolElt
Other Elementary Functions
AbsoluteValue(n) : RngIntElt -> RngIntElt
Ilog2(n) : RngIntElt -> RngIntElt
Ilog(b, n) : RngIntElt, RngIntElt -> RngIntElt
Quotrem(m, n) : RngIntElt, RngIntElt -> RngIntElt, RngIntElt
Valuation(x, p) : RngIntElt, RngIntElt -> RngIntElt, RngIntElt
Iroot(a, n) : RngIntElt, RngIntElt -> RngIntElt
Sign(n) : RngIntElt -> RngIntElt
Ceiling(n) : RngIntElt -> RngIntElt
Floor(n) : RngIntElt -> RngIntElt
Round(n) : RngIntElt -> RngIntElt
Truncate(n) : RngIntElt -> RngIntElt
SquarefreeFactorization(n) : RngIntElt -> RngIntElt, RngIntElt
Isqrt(n) : RngIntElt -> RngIntElt
Random Numbers
Random(a, b) : RngIntElt, RngIntElt -> RngIntElt
Random(b) : RngIntElt -> RngIntElt
RandomBits(n) : RngIntElt -> RngIntElt
RandomPrime(n: parameter) : RngIntElt -> RngIntElt
RandomPrime(n, a, b, x: parameter) :RngIntElt, RngIntElt, RngIntElt -> BoolElt, RngIntElt
RandomConsecutiveBits(n, a, b) : RngIntElt, RngIntElt -> RngIntElt
Common Divisors and Common Multiples
Gcd(m, n) : RngIntElt, RngIntElt -> RngIntElt
GreatestCommonDivisor(s) : [RngIntElt] -> RngIntElt
ExtendedGreatestCommonDivisor(m, n) : RngIntElt, RngIntElt -> RngIntElt, RngIntElt, RngIntElt
ExtendedGreatestCommonDivisor(s) : [RngIntElt] -> RngIntElt, [RngIntElt]
LeastCommonMultiple(m, n) : RngIntElt, RngIntElt -> RngIntElt
LeastCommonMultiple(s) : [RngIntElt] -> RngIntElt
Arithmetic Functions
CarmichaelLambda(n) : RngIntElt -> RngIntElt
FactoredCarmichaelLambda(n) : RngIntElt -> RngIntEltFact
DivisorSigma(i, n) : RngIntElt, RngIntElt -> RngIntElt
NumberOfDivisors(n) : RngIntElt -> RngIntElt
SumOfDivisors(n) : RngIntElt -> RngIntElt
EulerPhi(n) : RngIntElt -> RngIntElt
FactoredEulerPhi(n) : RngIntElt -> RngIntEltFact
LegendreSymbol(n, m) : RngIntElt, RngIntElt -> RngIntElt
JacobiSymbol(n, m) : RngIntElt, RngIntElt -> RngIntElt
KroneckerSymbol(n, m) : RngIntElt, RngIntElt -> RngIntElt
MoebiusMu(n) : RngIntElt -> RngIntElt
Example RngInt_Amicable (H40E4)
Combinatorial Functions
Binomial(n, r) : RngIntElt, RngIntElt -> RngIntElt
Multinomial(n, [a_1, ... a_n]) : RngIntElt, [RngIntElt] -> RngIntElt
Factorial(n) : RngIntElt -> RngIntElt
Partitions(n) : RngIntElt -> [ [ RngIntElt ] ]
NumberOfPartitions(n) : RngIntElt -> RngIntElt
RestrictedPartitions(n, Q) : RngIntElt, SetEnum -> [ [ RngIntElt ] ]
RestrictedPartitions(n, k, M) : RngIntElt, SetEnum -> [ [ RngIntElt ] ]
StirlingFirst(m, n) : RngIntElt, RngIntElt -> RngIntElt
StirlingSecond(m, n) : RngIntElt, RngIntElt -> RngIntElt
Fibonacci(n) : RngIntElt -> RngIntElt
Lucas(n) : RngIntElt -> RngIntElt
GeneralizedFibonacciNumber(g0, g1, n) : RngIntElt, RngIntElt, RngIntElt -> RngIntElt
Q as a Number Field
Decomposition(R, p) : RngInt, RngIntElt -> SeqEnum
MinimalInteger(I) : RngInt -> RngIntElt
RamificationIndex(I, p) : RngInt, RngIntElt -> RngIntElt
Degree(I) : RngInt -> RngIntElt
TwoElementNormal(I) : RngInt -> RngIntElt, RngIntElt
ChineseRemainderTheorem(I, J, a, b) : RngInt, RngInt, RngIntElt, RngIntElt -> RngIntElt
Valuation(x, I) : RngIntElt, RngInt -> RngIntElt
ClassRepresentative(I) : RngInt -> RngInt
Coercion
Example RngInt_Coercion (H40E5)
Homomorphisms
hom< R -> S | > : RngIntRes, Rng -> Map
Creation Functions
ResidueClassRing(m) : RngIntElt -> RngIntRes
ResidueClassRing(Q) : RngIntEltFact -> RngIntRes
quo< Z | I > : RngInt, RngInt -> RngIntRes
quo< Z | m > : RngInt, RngIntElt -> RngIntRes
elt< R | k > : RngIntRes, RngIntElt -> RngIntResElt
R ! k : RngIntRes, RngIntElt -> RngIntResElt
Random(R) : RngIntRes -> RngIntResElt
Structure Operations
AdditiveGroup(R) : RngIntRes -> GrpAb, Map
MultiplicativeGroup(R) : RngIntRes -> GrpAb, Map
sub< R | n > : RngIntRes, RngIntResElt -> RngIntRes
Set(R) : RngIntRes -> SetEnum
Numerical Invariants
Modulus(R) : RngIntRes -> RngInt
FactoredModulus(R) : RngIntRes -> RngIntEltFact
Predicates on Ring Elements
IsSquare(n) : RngIntResElt -> BoolElt, RngIntResElt
IsPrimitive(n) : RngIntResElt -> BoolElt
Other Element Functions
PrimitiveElement(R) : RngIntRes -> RngIntResElt
Order(a) : RngIntResElt -> RngIntElt
Sqrt(a) : RngIntResElt -> RngIntResElt
AllSquareRoots(a) : RngIntResElt -> [ RngIntResElt ]
Solving Linear Equations in Z/mZ
Solution(a, b) : RngIntResElt, RngIntResElt -> RngIntResElt
Ideal Operations
GreatestCommonDivisor(a, b) : RngIntResElt, RngIntResElt -> RngIntResElt
GreatestCommonDivisor(Q) : [RngIntResElt] -> RngIntResElt
LeastCommonMultiple(a, b) : RngIntResElt, RngIntResElt -> RngIntResElt
LeastCommonMultiple(Q) : Seq(RngIntResElt) -> RngIntResElt
Primality
IsPrime(n) : RngIntElt -> BoolElt
IsProbablePrime(n: parameter) : RngIntElt -> BoolElt
IsPrimePower(n) : RngIntElt -> BoolElt, RngIntElt, RngIntElt
Example RngInt_RepUnits (H40E6)
Other Functions Relating to Primes
NextPrime(n) : RngIntElt -> RngIntElt
PreviousPrime(n) : RngIntElt -> RngIntElt
RandomPrime(n: parameter) : RngIntElt -> RngIntElt
RandomPrime(n, a, b, x: parameter) :RngIntElt, RngIntElt, RngIntElt -> BoolElt, RngIntElt
PrimeBasis(n) : RngIntElt -> [RngIntElt]
General Factorization
SetVerbose("Factorization", v) : MonStgElt, RngIntElt ->
Factorization(n) : RngIntElt -> RngIntEltFact, RngIntElt, SeqEnum
Specific Factorization Algorithms
SetVerbose("Cunningham", b) : MonStgElt, Boolean ->
Cunningham(b, k, c) : RngIntElt, RngIntElt, RngIntElt -> SeqEnum
AssertAttribute(RngInt, "CunninghamStorageLimit", l) : Cat, MonStgElt, RngIntElt ->
TrialDivision(n) : RngIntElt -> RngIntEltFact, [ RngIntElt ]
PollardRho(n) : RngIntElt -> RngIntEltFact, [ RngIntElt ]
pMinus1(n) : RngIntElt -> RngIntEltFact, [ RngIntElt ]
SQUOFOF(n) : RngIntElt -> RngIntEltFact, [ RngIntElt ]
ECM(n) : RngIntElt -> RngIntEltFact, [ RngIntElt ]
MPQS(n) : RngIntElt -> RngIntEltFact, [ RngIntElt ]
Factorization Related Functions
PrimeBasis(n) : RngIntElt -> [RngIntElt]
Divisors(n) : RngIntElt -> [ RngIntElt ]
CoprimeBasis(S) : [ RngIntElt ] -> [ RngIntElt ]
Example RngInt_Perfect (H40E7)
PartialFactorization(S) : [ RngIntElt ] -> [ RngIntEltFact ]
Example RngInt_PartialFact (H40E8)
Creation and Conversion
Facint(f) : RngIntEltFact -> RngIntElt
SeqFact(s) : SeqEnum -> RngIntEltFact
Eltseq(f) : RngIntEltFact -> SeqEnum
Arithmetic Operations
Modexp(n, k, m) : RngIntElt, RngIntElt, RngIntElt -> RngIntElt
n mod m : RngIntElt, RngIntElt -> RngIntElt
Modinv(n, m) : RngIntElt, RngIntElt -> RngIntElt
Modsqrt(n, m) : RngIntElt, RngIntElt -> BoolElt, RngIntElt
Modorder(n, m) : RngIntElt, RngIntElt -> RngIntElt
IsPrimitive(n, m) : RngIntElt, RngIntElt -> BoolElt
PrimitiveRoot(m) : RngIntElt -> RngIntElt
The Solution of Modular Equations
Solution(a, b, m) : RngIntElt, RngIntElt, RngIntElt -> RngIntElt, RngIntElt
ChineseRemainderTheorem(X, N) : [RngIntElt], [RngIntElt] -> RngIntElt
Solution(A, B, N) : [RngIntElt], [RngIntElt],[RngIntElt] -> RngIntElt
NormEquation(d, m) : RngIntElt, RngIntElt -> BoolElt, RngIntElt, RngIntElt
Example RngInt_norm-equation (H40E9)
Creation
Infinity() : -> Infty
MinusInfinity() : -> Infty
Miscellaneous
Sign(x) : Infty -> RngIntElt
IsFinite(x) : Infty -> BoolElt
Advanced Factorization Techniques: The Number Field Sieve
The Number Field Sieve
Example RngInt_70digitnfs (H40E10)
Example RngInt_80digitnfs (H40E11)
Example RngInt_87digitnfs (H40E12)
NFS(n, F, m1, m2) : RngIntElt, RngMPolElt, RngIntElt, RngIntElt -> RngIntElt
NFSRelations(n, F, tuple) : RngIntElt, RngMPolElt, Tup -> RngIntElt
NFSMerge(T, fn) : Tup, MonStgElt -> .
NFSCWIFormat(n, F, T, pb) : RngIntElt, RngMPolElt, Tup, RngIntElt -> .;
NFSCycleCount(n, F, tuple) : RngIntElt, RngMPolElt, Tup -> RngIntElt
NFSCycleFile(n, F, tuple) : RngIntElt, RngMPolElt, Tup -> .
NFSCharacterColumns(n, F, tuple) : RngIntElt, RngMPolElt, Tup -> .
NFSDependencies(n, F, tuple) : RngIntElt, RngMPolElt, Tup -> .
NFSFactor(n, F, tuple) : RngIntElt, RngMPolElt, Tup -> RngIntElt
NFSClear(n, F, tuple) : RngIntElt, RngMPolElt, Tup -> .
Tools for Finding a Suitable Polynomial
BaseMPolynomial(n, m, d) : RngIntElt, RngIntElt, RngIntElt -> RngMPolElt
MurphyAlphaApproximation(F, b) : RngMPolElt, RngIntElt -> FldReElt
OptimalSkewness(F) : RngMPolElt -> FldReElt, FldReElt
Example RngInt_GetPoly (H40E13)
BestTranslation( T ) : Tup -> Tup
PolynomialSieve( T ) : Tup -> SeqEnum