Let's first import Python/Sage bindings to compute embeddings using different libraries and algorithms.
from ffisom import *
Lets define an extension finite field with different underlying libraries:
p = 7
n = 237
q = p**n
k = GF(q, name='z')
k_flint = GF_flint(p, k.modulus(), name='z')
Here comes data of importance to the algorithms:
o, _ = find_root_order(p, [n, n], n, verbose=False)
c = Mod(p,n).multiplicative_order()
print o, c
1 78
We cannot test Magma implementation of cyclotomic Rains here, but we can test ours.
%time a, b = find_gens_cyclorains(k, k)
print a.minpoly() == b.minpoly()
CPU times: user 43 ms, sys: 2 ms, total: 45 ms Wall time: 43.3 ms True
%time a, b = find_gens_cyclorains(k_flint, k_flint)
print a.minpoly() == b.minpoly()
CPU times: user 34 ms, sys: 4 ms, total: 38 ms Wall time: 35.9 ms True
As o == 2, the conic Rains algorithm does not apply here, but we can try the elliptic variation.
%time a, b = find_gens_ellrains(k, k)
print a.minpoly() == b.minpoly()
CPU times: user 1.44 s, sys: 1 ms, total: 1.44 s Wall time: 1.44 s True
%time a, b = find_gens_ellrains(k_flint, k_flint)
print a.minpoly() == b.minpoly()
CPU times: user 391 ms, sys: 2 ms, total: 393 ms Wall time: 388 ms True
Let's try PARI/GP implementation of Lenstra/Allombert:
%time a, b = find_gens_pari(k, k)
print a.minpoly() == b.minpoly()
CPU times: user 2.95 s, sys: 0 ns, total: 2.95 s Wall time: 2.95 s True
And finally our C++ implementations of variations on Lenstra/Allombert:
for i, algo in enumerate(kummer_algolist[2*(c==1):-2*(c==1)-1]):
print kummer_namelist[2*(c==1)+i]
%time a, b = find_gens_kummer(k_flint, k_flint, n, algo)
print a.minpoly() == b.minpoly()
LINALG_CYCLO CPU times: user 584 ms, sys: 0 ns, total: 584 ms Wall time: 583 ms True LINALG_ONLY CPU times: user 211 ms, sys: 0 ns, total: 211 ms Wall time: 211 ms True LINALG CPU times: user 217 ms, sys: 0 ns, total: 217 ms Wall time: 217 ms True MODCOMP CPU times: user 217 ms, sys: 0 ns, total: 217 ms Wall time: 217 ms True COFACTOR CPU times: user 190 ms, sys: 0 ns, total: 190 ms Wall time: 189 ms True ITERFROB CPU times: user 193 ms, sys: 0 ns, total: 193 ms Wall time: 193 ms True MPE CPU times: user 233 ms, sys: 0 ns, total: 233 ms Wall time: 233 ms True
All of the above can be automated to get performance data using functions from the benchmark module. The p, n, o, c stuff is as above and are repeated on the timing line where it is followed by timings for :
from benchmark import *
benchmark(pbound=[3, 10], nbound=[3,10], prime=True, skip_magma=True)
p = 3, n = 5, (o = 1, c = 4) 3 5 (1, 4) 0 0.00104029178619 0 0 0.000214171409607 0.000252461433411 0.000206804275513 0.000239109992981 0.00023558139801 0.000199675559998 0.000184798240662 0.000219798088074 p = 3, n = 7, (o = 4, c = 6) 3 7 (4, 6) 0 0.0182385921478 0 0 0.000329279899597 0.000423884391785 0.000290179252625 0.00036346912384 0.000365328788757 0.000275325775146 0.000277233123779 0.000323891639709 p = 5, n = 3, (o = 2, c = 2) 5 3 (2, 2) 0 0.00926465988159 0.00410797595978 0.00565741062164 0.000153589248657 8.82625579834e-05 7.37428665161e-05 8.65697860718e-05 8.50915908813e-05 7.74383544922e-05 6.81638717651e-05 7.14063644409e-05 p = 5, n = 7, (o = 2, c = 6) 5 7 (2, 6) 0 0.0130973339081 0.00559575557709 0.00507645606995 0.00050151348114 0.000452399253845 0.000354504585266 0.000415539741516 0.000410485267639 0.000329875946045 0.000319623947144 0.000390458106995 p = 7, n = 3, (o = 1, c = 1) 7 3 (1, 1) 0 0.00118911266327 0 0.00498025417328 0.000131869316101 0 0 2.70128250122e-05 2.80618667603e-05 2.91109085083e-05 0 0 p = 7, n = 5, (o = 2, c = 4) 7 5 (2, 4) 0 0.0141561985016 0.00537779331207 0.005087018013 0.000209999084473 0.000223612785339 0.000172328948975 0.000203800201416 0.000200629234314 0.000172138214111 0.000155472755432 0.000178909301758