RING OF INTEGERS
Acknowledgements
Introduction
Representation
Coercion
Homomorphisms
Creation Functions
Creation of Structures
Creation of Elements
Printing of Elements
Element Conversions
Structure Operations
Related Structures
Numerical Invariants
Ring Predicates and Booleans
Element Operations
Arithmetic Operations
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
Random Numbers
GCD and LCM
Arithmetic Functions
Combinatorial Functions
Primes and Primality Testing
Primality
Other Functions Relating to Primes
Factorization
General Factorization
Storing Potential Factors
Specific Factorization Algorithms
Factorization Related Functions
Factorization Sequences
Creation and Conversion
Arithmetic
Divisors
Predicates
Modular Arithmetic
Arithmetic Operations
The Solution of Modular Equations
Infinities
Creation
Arithmetic
Comparison
Miscellaneous
Advanced Factorization Techniques: The Number Field Sieve
The Magma Number Field Sieve Implementation
Naive NFS
Factoring with NFS Processes
Attribute Selection
The Sieving Stage
The Auxiliary Data Stage
Finding Dependencies: the Linear Algebra Stage
The Factorization Stage
Data Files
Magma Native NFS Data Files
Distributing NFS Factorizations
Magma and CWI NFS Interoperability
Tools for Finding a Suitable Polynomial
Bibliography
Introduction
Representation
Coercion
Homomorphisms
hom< Z -> R | > : RngInt, Rng -> Map
Example RngInt_hom (H19E1)
Creation Functions
Creation of Structures
IntegerRing() : -> RngInt
Creation of Elements
a1a2...ar
0xa1a2...ar
elt< Z | a1a2...ar > : RngInt, RngIntElt -> RngIntElt
elt< Z | 0xa1a2...ar > : RngInt, RngIntElt -> RngIntElt
Z ! a : RngInt, RngElt -> RngIntElt
Example RngInt_Integers (H19E2)
Printing of Elements
Example RngInt_Printing (H19E3)
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
Structure Operations
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
Ring Predicates and Booleans
Element Operations
Arithmetic Operations
n div m : RngIntElt, RngIntElt -> RngIntElt
n mod m : RngIntElt, RngIntElt -> RngIntElt
ExactQuotient(n, d) : RngIntElt, RngIntElt -> RngIntElt
Bit Operations
ShiftLeft(n, b) : RngIntElt, RngIntElt -> RngIntElt
ShiftRight(n, b) : RngIntElt, RngIntElt -> RngIntElt
ModByPowerOf2(n, b) : RngIntElt, RngIntElt -> RngIntElt
Bitwise Operations
BitwiseNot(x) : RngIntElt -> RngIntElt
BitwiseAnd(x, y) : RngIntElt, RngIntElt -> RngIntElt
BitwiseOr(x, y) : RngIntElt, RngIntElt -> RngIntElt
BitwiseXor(x, y) : RngIntElt, RngIntElt -> RngIntElt
Equality and Membership
Parent and Category
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, RngIntElt -> BoolElt
IsPrime(n) : RngIntElt -> BoolElt
Example RngInt_IsPrime (H19E4)
IsIntegral(n) : RngIntElt -> BoolElt
IsSinglePrecision(n) : RngIntElt -> BoolElt
Comparison of Ring Elements
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
GCD and LCM
GreatestCommonDivisor(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
DickmanRho(u) : FldReElt -> FldReElt
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 (H19E5)
Combinatorial Functions
Binomial(n, r) : RngIntElt, RngIntElt -> RngIntElt
Multinomial(n, [r1, ... rn]) : RngIntElt, [RngIntElt] -> RngIntElt
Factorial(n) : RngIntElt -> RngIntElt
IsFactorial(n) : RngIntElt -> BoolElt, RngIntElt
Partitions(n) : RngIntElt -> [ [ RngIntElt ] ]
NumberOfPartitions(n) : RngIntElt -> RngIntElt
RestrictedPartitions(n, M) : RngIntElt, SetEnum -> [ [ RngIntElt ] ]
RestrictedPartitions(n, k, M) : RngIntElt, RngIntElt, SetEnum -> [ [ RngIntElt ] ]
StirlingFirst(n, k) : RngIntElt, RngIntElt -> RngIntElt
StirlingSecond(n, k) : RngIntElt, RngIntElt -> RngIntElt
Bell(n) : RngIntElt -> RngIntElt
Fibonacci(n) : RngIntElt -> RngIntElt
Lucas(n) : RngIntElt -> RngIntElt
GeneralizedFibonacciNumber(g0, g1, n) : RngIntElt, RngIntElt, RngIntElt -> RngIntElt
Primes and Primality Testing
Primality
IsPrime(n) : RngIntElt -> BoolElt
SetVerbose("ECPP", v) : MonStgElt, Elt ->
PrimalityCertificate(n) : RngIntElt -> SeqEnum
OldCertificate(cert) : SeqEnum -> List
IsProbablePrime(n: parameter) : RngIntElt -> BoolElt
IsPrimePower(n) : RngIntElt -> BoolElt, RngIntElt, RngIntElt
Example RngInt_RepUnits (H19E6)
Other Functions Relating to Primes
NextPrime(n) : RngIntElt -> RngIntElt
PreviousPrime(n) : RngIntElt -> RngIntElt
PrimesUpTo(B) : RngIntElt -> [RngIntElt]
PrimesInInterval(b, e) : RngIntElt, RngIntElt -> [RngIntElt]
NthPrime(n) : RngIntElt -> RngIntElt
RandomPrime(n: parameter) : RngIntElt -> RngIntElt
RandomPrime(n, a, b, x: parameter) :RngIntElt, RngIntElt, RngIntElt -> BoolElt, RngIntElt
PrimeBasis(n) : RngIntElt -> [RngIntElt]
Factorization
General Factorization
SetVerbose("Factorization", v) : MonStgElt, RngIntElt ->
Factorization(n) : RngIntElt -> RngIntEltFact, RngIntElt, SeqEnum
Storing Potential Factors
StoreFactor(n) : RngIntElt ->
GetStoredFactors() : -> [ RngIntElt ]
ClearStoredFactors() : ->
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 (H19E7)
PartialFactorization(S) : [ RngIntElt ] -> [ RngIntEltFact ]
Example RngInt_PartialFact (H19E8)
Factorization Sequences
Creation and Conversion
Facint(f) : RngIntEltFact -> RngIntElt
SeqFact(s) : SeqEnum -> RngIntEltFact
Eltseq(f) : RngIntEltFact -> SeqEnum
Arithmetic
Divisors
Predicates
Modular Arithmetic
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 (H19E9)
Infinities
Creation
Infinity() : -> Infty
MinusInfinity() : -> Infty
Arithmetic
Comparison
Miscellaneous
Sign(x) : Infty -> RngIntElt
Abs(x) : Infty -> Infty
Round(x) : Infty -> Infty
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) : RngIntElt, RngMPolElt, RngIntElt, RngIntElt -> NFSProc
Example RngInt_nfsprocessparameters (H19E10)
Attribute Selection
Example RngInt_70digitnfs (H19E11)
Example RngInt_80digitnfs (H19E12)
Example RngInt_87digitnfs (H19E13)
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
Magma Native NFS Data Files
Distributing NFS Factorizations
Example RngInt_distributed (H19E14)
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 (H19E15)
BestTranslation(F, m, a) : RngMPolElt, RngIntElt, FldReElt, FldReElt -> RngMPolElt, RngIntElt, FldReElt, FldReElt
PolynomialSieve(F, m, J0, J1,MaxAlpha) : RngMPolElt, RngIntElt, RngIntElt, RngIntElt, FldReElt -> List
Bibliography
[Next][Prev] [Right] [____] [Up] [Index] [Root]
|