Homomorphisms
hom< Z -> R | > : RngInt, Rng -> Map
Example RngInt_hom (H39E1)
Creation of Structures
IntegerRing() : -> RngInt
Creation of Elements
a_1a_2...a_r : RngIntElt, ..., RngIntElt -> RngIntElt
0xa_1a_2...a_r : RngIntElt, ..., RngIntElt -> RngIntElt
elt< Z | a_1a_2...a_r > : RngInt, RngIntElt -> RngIntElt
elt< Z | 0xa_1a_2...a_r > : RngInt, RngIntElt -> RngIntElt
Z ! a : RngInt, RngElt -> RngIntElt
Example RngInt_Integers (H39E2)
Printing of Elements
Example RngInt_Printing (H39E3)
Element Conversions
FactorizationToInteger(s) : [ <RngIntElt, RngIntElt> ] -> RngIntElt
IntegerToSequence(n, b) : RngIntElt, RngIntElt -> [RngIntElt]
SequenceToInteger(s, b) : [RngIntElt], RngIntElt -> RngIntElt
IntegerToString(n) : RngIntElt -> ModStgElt
IntegerToString(n, b) : RngIntElt, RngIntElt -> ModStgElt
Eltseq(n) : RngIntElt -> [RngIntElt]
Denominator(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 (H39E4)
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
EulerPhiInverse(m) : RngIntElt -> RngIntElt
FactoredEulerPhiInverse(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 (H39E5)
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
Generator(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 (H39E6)
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
Normalize(x) : RngIntRes -> RngIntResElt, RngIntResElt
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) : [RngIntResElt] -> RngIntResElt
Primality
IsPrime(n) : RngIntElt -> BoolElt
IsProbablePrime(n: parameter) : RngIntElt -> BoolElt
IsPrimePower(n) : RngIntElt -> BoolElt, RngIntElt, RngIntElt
Example RngInt_RepUnits (H39E7)
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, BoolElt ->
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, B1) : RngIntElt, RngIntElt -> RngIntElt
pPlus1(n, B1) : RngIntElt, RngIntElt -> RngIntElt
SQUFOF(n) : RngIntElt -> RngIntEltFact, [ RngIntElt ]
ECM(n, B1) : RngIntElt, RngIntElt -> RngIntElt, RngIntElt
ECMSteps(n, L, U) : RngIntElt, RngIntElt, RngIntElt -> RngIntElt, RngIntElt
MPQS(n) : RngIntElt -> RngIntEltFact, [ RngIntElt ]
Factorization Related Functions
ECMOrder(p, s) : RngIntElt, RngIntElt -> RngIntElt
PrimeBasis(n) : RngIntElt -> [RngIntElt]
Divisors(n) : RngIntElt -> [ RngIntElt ]
CoprimeBasis(S) : [ RngIntElt ] -> [ RngIntElt ]
Example RngInt_Perfect (H39E8)
PartialFactorization(S) : [ RngIntElt ] -> [ RngIntEltFact ]
Example RngInt_PartialFact (H39E9)
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 (H39E10)
Creation
Infinity() : -> Infty
MinusInfinity() : -> Infty
Miscellaneous
Sign(x) : Infty -> RngIntElt
IsFinite(x) : Infty -> BoolElt
Advanced Factorization Techniques: The Number Field Sieve
The Magma Number Field Sieve implementation
SetVerbose("NFS", v) : MonStgElt, RngIntElt ->
Naive NFS
NumberFieldSieve(n, F, m1, m2) : RngIntElt, RngMPolElt, RngIntElt, RngIntElt -> RngIntElt
Factoring with NFS Processes
NFSProcess(n, F, m1, m2) : -> NFSProc
Example RngInt_nfsprocessparameters (H39E11)
Parameter selection
Example RngInt_70digitnfs (H39E12)
Example RngInt_80digitnfs (H39E13)
Example RngInt_87digitnfs (H39E14)
The Sieving stage
NumberOfRelationsRequired(P) : NFSProc -> RngIntElt
FindRelations(P) : NFSProc -> RngIntElt
The Auxiliary data stage
CreateCycleFile(P) : NFSProc -> .
CycleCount(P) : NFSProc -> RngIntElt
CycleCount(fn) : MonStgElt -> RngIntElt
CreateCharacterFile(P) : NFSProc -> .
CreateCharacterFile(P, cc) : NFSProc, RngIntElt -> .
Finding dependencies: the Linear algebra stage
FindDependencies(P) : NFSProc -> .
The Factorization stage
Factor(P) : NFSProc -> RngIntElt
Factor(P,k) : NFSProc, RngIntElt -> RngIntElt
Data files
RemoveFiles(P) : NFSProc -> .
MergeFiles(S, fn) : [MonStgElt], MonStgElt -> RngIntElt, RngIntElt
Distributing NFS factorizations
Example RngInt_distributed (H39E15)
Magma and CWI NFS interoperability
FindRelationsInCWIFormat(P) : NFSProc -> RngIntElt
ConvertToCWIFormat(P, pb) : NFSProc, RngIntElt -> .;
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 (H39E16)
BestTranslation(F, m, a) : RngMPolElt, RngIntElt, FldReElt, FldReElt -> RngMPolElt, RngIntElt, FldReElt, FldReElt
PolynomialSieve(F, m, J0, J1,MaxAlpha) : RngMPolElt, RngIntElt, RngIntElt, RngIntElt, FldPrElt -> List
DickmanRho(u) : FldPrElt -> FldReElt
PrimesUpTo(B) : RngIntElt -> [RngIntElt]
PrimesInInterval(t, b) : RngIntElt, RngIntElt -> [RngIntElt]