|
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
Let K be a field of cardinality q=pk, with p prime.
There are two types of algorithms used in Magma to compute discrete
logarithms for finite fields:
- (a)
- Pohlig-Hellman [PH78]:
- The running time is usually proportional to the square root of the
largest prime l dividing q - 1. This is combined with the Shanks
baby-step/giant-step algorithm (when l is very small) or the
Pollard-ρalgorithm. This algorithm is always used for any
K if l is small and is also used if K is any non-prime field of
characteristic greater than 2.
- (b)
- Index-Calculus Methods:
- (1)
- Suppose K is a prime field (so q=p).
Then the Gaussian integer sieve [COS86], [LO91a] is
used if p has at least 4 bits but no more than 400 bits,
p - 1 is not a square, and one of the following is a quadratic
residue modulo p: -1, -2, -3, -7, or -11.
If the Gaussian integer sieve cannot
be used and if p is no more than 300-bits,
then the linear sieve [COS86], [LO91a] is used.
- (2)
- If K is a finite field of characteristic 2 (so p=2), then
Emmanuel Thom'e's implementation [Tho01]
of Coppersmith's index-calculus algorithm
[Cop84], [GM93] is used.
When an index-calculus method is first used for some finite field, a
precomputation stage takes place which may require a lot of memory for
large fields. This precomputation stage also requires a lot more time
than for computing individual logarithms. Thus, the first call to the
function Log below may take much more time than for subsequent calls.
Also, for large prime fields, in comparison to the Gaussian method the
linear sieve requires much more time and memory than the Gaussian method
for the precomputation stage, and therefore it is only used
when the Gaussian integer algorithm cannot be used.
See the example H26E3 in the chapter on sparse matrices
for an explanation of the basic linear sieve algorithm and for more
information on the sparse linear algebra techniques employed in
index-calculus methods.
The discrete logarithm of the non-zero element x from the
field F, i.e., the unique integer k such that x = wk and
0 ≤k < (#F - 1), where w is the primitive element
of F (as returned by PrimitiveElement).
Default parameters are automatically chosen if an index-calculus
method is used (use Sieve and Coppersmith below
to set parameters).
See also the procedure SetPrimitiveElement.
The discrete logarithm to the base b of the non-zero element x from
the field F, i.e., the unique integer k such that x = bk and
0 ≤k < (#F - 1). If b is not a primitive element, then in
some unusual cases the algorithm may take much longer than normal.
The Zech logarithm Z(n) of the integer n for the field field F, which
equals the logarithm to base w of wn + 1, where w
is the primitive element of F. If wn is the minus one element
of K, then -1 is returned.
Sieve(K) : FldFin ->
Lanczos: BoolElt Default: false
(Procedure.)
Call the Gaussian integer sieve on the prime finite field K if
possible; otherwise call the linear sieve on K (assuming K is not
too small).
If the parameter Lanczos is set to true, then the Lanczos algorithm [LO91b, Sec. 3] will be used for the
linear algebra phase.
This is generally very much slower than the default method
(often 10 to 50 times slower), but it will take considerably less
memory, so may be preferable for extremely large fields.
See also the function ModularSolution in the
chapter on sparse matrices for more information.
SmoothnessBound: RngIntElt Default:
LargePrimeBound: RngIntElt Default:
SieveA: RngIntElt Default:
SieveB: RngIntElt Default:
RelationsRatio: RngElt Default: 1.2
Lanczos: BoolElt Default: false
(Procedure.)
Call Emmanuel Thom'e's implementation of
Coppersmith's algorithm on the characteristic-2 field K
with the given parameters. Each of these parameters will have
a default chosen by Magma based on the degree of K; assigning them
to other values may yield better results in several cases (and
may enable the sieving to succeed where the default parameters may fail
for high degrees).
See [Tho01] for more details concerning each parameter.
The parameter SmoothnessBound controls the size of the factor
base which is used during the calculations. The factor base consists
of all irreducible polynomials over GF(2) whose degree is less than
or equal to this bound. The bound must not exceed 29.
The parameter LargePrimeBound specifies the maximum acceptable
degree of the "large primes" used for matching partial relations.
These large primes are the cofactors that remain in a factorization
after all the factors belonging to the factor base have been set aside.
In order to make sure large primes are indeed irreducibles,
LargePrimeBound must lie in the interval [s ... 2s + 1] where
s is the value of the parameter SmoothnessBound.
The parameters SieveA and SieveB control the size of the
overall sieving space, which is the set of coprime polynomials (A, B)
with Degree(A)≤ SieveA and Degree(B)≤ SieveB.
The parameter RelationsRatio determines the number of excess relations
that will be needed before commencing the linear algebra.
The sieving will finish and the linear algebra will then be applied
to the resulting matrix as soon as the number of relations is greater
or equal to than RelationsRatio times the number of unknowns.
RelationsRatio must be greater than 1.
If the parameter Lanczos is set to true, then the Lanczos algorithm [LO91b, Sec. 3] will be used for the
linear algebra phase.
This is generally very much slower than the default method (it is
often 10 to 50 times slower), but it will take considerably less
memory, so may be preferable for extremely large fields.
See also the function ModularSolution in the
chapter on sparse matrices for more information.
(Procedure.)
Set the verbose printing level for the finite field logarithm
algorithm to be v. Currently the legal values for v are 0, 1, and
2.
If the level is 1, information is printed whenever the logarithm of an element
is computed (unless the field is very small, in which case a lookup table
is used).
The value of 2 will print a very large amount of information.
We demonstrate the Log function.
> F<z> := FiniteField(7^4);
> PrimitiveElement(F);
z;
> Log(z);
1
> Log(z^2);
2
> Log(z + 1);
419
> z^419 eq z + 1;
true
> b := z + 1;
> b;
z^419
> Log(b, b);
1
> Log(b, z);
779
> b^779 eq z;
true
We now do similar things for a larger field of characteristic 2, which
will use Coppersmith's algorithm to compute the logarithms.
> F<z> := GF(2, 73);
> Factorization(#F-1);
[ <439, 1>, <2298041, 1>, <9361973132609, 1> ]
> PrimitiveElement(F);
z
> time Log(z + 1);
4295700317032218908392
Time: 5.400
> z^4295700317032218908392;
z + 1
> time Log(z + 1);
4295700317032218908392
Time: 0.000
> time Log(z^2);
2
Time: 0.000
> time Log(z^2134914112412412);
2134914112412412
Time: 0.000
> b := z + 1;
> b;
z + 1
> time Log(b, b);
1
Time: 0.010
> time Log(b, z);
2260630912967574270198
Time: 0.000
> b^2260630912967574270198;
z
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
