1 #include "cado.h" // IWYU pragma: keep
2 #include <climits> // for UINT_MAX
3 #ifndef SELECT_MPFQ_LAYER_u64k1
4 #include <gmp.h>
5 #include "cxx_mpz.hpp"
6 #endif
7 #include "lingen_abfield.hpp" // IWYU pragma: keep
8 #include "lingen_bw_dimensions.hpp" // for bw_dimensions
9 #include "lingen_expected_pi_length.hpp"
10 #include "macros.h" // for iceildiv, MAYBE_UNUSED
11
12
get_minmax_delta(std::vector<unsigned int> const & delta)13 std::tuple<unsigned int, unsigned int> get_minmax_delta(std::vector<unsigned int> const & delta)/*{{{*/
14 {
15 unsigned int maxdelta = 0;
16 unsigned int mindelta = UINT_MAX;
17 for(auto x : delta) {
18 if (x > maxdelta) maxdelta = x;
19 if (x < mindelta) mindelta = x;
20 }
21 return std::make_tuple(mindelta, maxdelta);
22 }/*}}}*/
get_min_delta(std::vector<unsigned int> const & delta)23 unsigned int get_min_delta(std::vector<unsigned int> const & delta)/*{{{*/
24 {
25 unsigned int mindelta, maxdelta;
26 std::tie(mindelta, maxdelta) = get_minmax_delta(delta);
27 return mindelta;
28 }/*}}}*/
get_max_delta(std::vector<unsigned int> const & delta)29 unsigned int get_max_delta(std::vector<unsigned int> const & delta)/*{{{*/
30 {
31 unsigned int mindelta, maxdelta;
32 std::tie(mindelta, maxdelta) = get_minmax_delta(delta);
33 return maxdelta;
34 }/*}}}*/
35
36
expected_pi_length(bw_dimensions & d,unsigned int len)37 unsigned int expected_pi_length(bw_dimensions & d, unsigned int len)/*{{{*/
38 {
39 /* The idea is that we want something which may account for something
40 * exceptional, bounded by probability 2^-64. This corresponds to a
41 * column in e (matrix of size m*b) to be spontaneously equal to
42 * zero. This happens with probability (#K)^-m.
43 * The solution to
44 * (#K)^(-m*x) > 2^-64
45 * is m*x*log_2(#K) < 64
46 *
47 * We thus need to get an idea of the value of log_2(#K).
48 *
49 * (Note that we know that #K^abgroupsize(ab) < 2^64, but that bound
50 * might be very gross).
51 *
52 * The same esitmate can be used to appreciate what we mean by
53 * ``luck'' in the end. If a column happens to be zero more than
54 * expected_pi_length(d,0) times in a row, then the cause must be
55 * more than sheer luck, and we use it to detect generating rows.
56 */
57
58 unsigned int m = d.m;
59 unsigned int n = d.n;
60 unsigned int b = m + n;
61 abdst_field ab MAYBE_UNUSED = d.ab;
62 unsigned int res = 1 + iceildiv(len * m, b);
63 #ifndef SELECT_MPFQ_LAYER_u64k1
64 cxx_mpz p;
65 abfield_characteristic(ab, (mpz_ptr) p);
66 unsigned int l;
67 if (mpz_cmp_ui(p, 1024) >= 0) {
68 l = mpz_sizeinbase(p, 2);
69 l *= abfield_degree(ab); /* roughly log_2(#K) */
70 } else {
71 mpz_pow_ui(p, p, abfield_degree(ab));
72 l = mpz_sizeinbase(p, 2);
73 }
74 #else
75 // K is GF(2), period.
76 unsigned int l = 1;
77 #endif
78 // unsigned int safety = iceildiv(abgroupsize(ab), m * sizeof(abelt));
79 unsigned int safety = iceildiv(64, m * l);
80 // this +1 is here because I've sometimes seen the c30 fail in the
81 // lingen step because of the pi size check. I wonder whether I
82 // should have a +1 here, or maybe a +t0. Anyway. Quite sure that
83 // it's in the whereabouts of adding a small offset.
84 safety++;
85 return res + safety;
86 }/*}}}*/
87
expected_pi_length(bw_dimensions & d,std::vector<unsigned int> const & delta,unsigned int len)88 unsigned int expected_pi_length(bw_dimensions & d, std::vector<unsigned int> const & delta, unsigned int len)/*{{{*/
89 {
90 // see comment above.
91
92 unsigned int mi, ma;
93 std::tie(mi, ma) = get_minmax_delta(delta);
94
95 return expected_pi_length(d, len) + ma - mi;
96 }/*}}}*/
97
expected_pi_length_lowerbound(bw_dimensions & d,unsigned int len)98 unsigned int expected_pi_length_lowerbound(bw_dimensions & d, unsigned int len)/*{{{*/
99 {
100 /* generically we expect that len*m % (m+n) columns have length
101 * 1+\lfloor(len*m/(m+n))\rfloor, and the others have length one more.
102 * For one column to have a length less than \lfloor(len*m/(m+n))\rfloor,
103 * it takes probability 2^-(m*l) using the notations above. Therefore
104 * we can simply count 2^(64-m*l) accidental zero cancellations at
105 * most below the bound.
106 * In particular, it is sufficient to derive from the code above!
107 */
108 unsigned int m = d.m;
109 unsigned int n = d.n;
110 unsigned int b = m + n;
111 abdst_field ab MAYBE_UNUSED = d.ab;
112 unsigned int res = 1 + (len * m) / b;
113 #ifndef SELECT_MPFQ_LAYER_u64k1
114 cxx_mpz p;
115 abfield_characteristic(ab, p);
116 unsigned int l;
117 if (mpz_cmp_ui(p, 1024) >= 0) {
118 l = mpz_sizeinbase(p, 2);
119 l *= abfield_degree(ab); /* roughly log_2(#K) */
120 } else {
121 mpz_pow_ui(p, p, abfield_degree(ab));
122 l = mpz_sizeinbase(p, 2);
123 }
124 #else
125 unsigned int l = 1;
126 #endif
127 unsigned int safety = iceildiv(64, m * l);
128 return safety < res ? res - safety : 0;
129 }/*}}}*/
130
131