6#include <symengine/symengine_exception.h>
13 SYMENGINE_ASSIGN_TYPEID()
20 if (dict.modulo_ <= integer_class(0))
23 if (dict.dict_[dict.dict_.
size() - 1] == integer_class(0))
32 seed += get_var()->hash();
33 for (
const auto &
it : get_poly().dict_) {
45 if (get_poly().size() != s.get_poly().size())
46 return (get_poly().size() < s.get_poly().size()) ? -1 : 1;
66GaloisField::from_vec(
const RCP<const Basic> &var,
68 const integer_class &
modulo)
71 GaloisFieldDict::from_vec(v,
modulo));
75 const integer_class &
modulo)
84 if (get_poly().dict_.empty())
87 for (
unsigned i = 0; i < get_poly().dict_.size(); i++) {
88 if (get_poly().dict_[i] == integer_class(0))
93 if (get_poly().dict_[i] == 1) {
94 args.push_back(get_var());
100 if (get_poly().dict_[i] == 1) {
112GaloisFieldDict::GaloisFieldDict(
const int &i,
const integer_class &
mod)
116 mp_fdiv_r(
temp, integer_class(i), modulo_);
117 if (
temp != integer_class(0))
118 dict_.insert(dict_.begin(),
temp);
121GaloisFieldDict::GaloisFieldDict(
const map_uint_mpz &p,
122 const integer_class &
mod)
126 dict_.resize(p.rbegin()->first + 1, integer_class(0));
127 for (
auto &
iter : p) {
129 mp_fdiv_r(
temp,
iter.second, modulo_);
136GaloisFieldDict::GaloisFieldDict(
const integer_class &i,
137 const integer_class &
mod)
141 mp_fdiv_r(
temp, i, modulo_);
142 if (
temp != integer_class(0))
143 dict_.insert(dict_.begin(),
temp);
147 const integer_class &
modulo)
151 x.dict_.resize(v.
size());
152 for (
unsigned int i = 0; i < v.
size(); ++i) {
154 mp_fdiv_r(a, v[i],
modulo);
161GaloisFieldDict &GaloisFieldDict::negate()
163 for (
auto &a : dict_) {
171void GaloisFieldDict::gf_istrip()
173 for (
auto i = dict_.
size(); i-- != 0;) {
174 if (dict_[i] == integer_class(0))
181GaloisFieldDict GaloisFieldDict::mul(
const GaloisFieldDict &a,
182 const GaloisFieldDict &b)
184 if (a.modulo_ != b.modulo_)
186 if (a.get_dict().empty())
188 if (b.get_dict().empty())
192 p.dict_.resize(a.degree() + b.degree() + 1, integer_class(0));
193 p.modulo_ = a.modulo_;
194 for (
unsigned int i = 0; i <= a.degree(); i++)
195 for (
unsigned int j = 0;
j <= b.degree();
j++) {
196 auto temp = a.dict_[i];
198 if (
temp != integer_class(0)) {
199 auto t = p.dict_[i +
j];
201 mp_fdiv_r(t, t, a.modulo_);
209void GaloisFieldDict::gf_div(
const GaloisFieldDict &
o,
213 if (modulo_ !=
o.modulo_)
214 throw SymEngineException(
"Error: field must be same.");
219 *
quo = GaloisFieldDict::from_vec(
dict_out, modulo_);
220 *
rem = GaloisFieldDict::from_vec(dict_, modulo_);
227 *
quo = GaloisFieldDict::from_vec(
dict_out, modulo_);
228 *
rem = GaloisFieldDict::from_vec(dict_, modulo_);
240 for (
size_t j =
lb;
j <
ub; ++
j) {
246 mp_fdiv_r(coeff, coeff, modulo_);
258 *
quo = GaloisFieldDict::from_vec(
dict_quo, modulo_);
259 *
rem = GaloisFieldDict::from_vec(
dict_rem, modulo_);
263GaloisFieldDict GaloisFieldDict::gf_lshift(
const integer_class n)
const
267 if (!dict_.
empty()) {
268 auto n_val = mp_get_ui(n);
275void GaloisFieldDict::gf_rshift(
const integer_class n,
280 *
quo = GaloisFieldDict::from_vec(
dict_quo, modulo_);
281 auto n_val = mp_get_ui(n);
286 *
rem = GaloisFieldDict::from_vec(
dict_rem, modulo_);
292GaloisFieldDict GaloisFieldDict::gf_sqr()
const
294 return (*
this * *
this);
297GaloisFieldDict GaloisFieldDict::gf_pow(
const unsigned long n)
const
300 return GaloisFieldDict({integer_class(1)}, modulo_);
308 GaloisFieldDict
to_ret = GaloisFieldDict({integer_class(1)}, modulo_);
320void GaloisFieldDict::gf_monic(integer_class &
res,
325 res = integer_class(0);
328 if (
res != integer_class(1)) {
329 integer_class inv,
temp;
330 mp_invert(inv,
res, modulo_);
340GaloisFieldDict GaloisFieldDict::gf_gcd(
const GaloisFieldDict &
o)
const
342 if (modulo_ !=
o.modulo_)
343 throw SymEngineException(
"Error: field must be same.");
345 GaloisFieldDict
g =
o;
347 while (
not g.dict_.empty()) {
349 f.dict_.swap(
g.dict_);
356GaloisFieldDict GaloisFieldDict::gf_lcm(
const GaloisFieldDict &
o)
const
358 if (modulo_ !=
o.modulo_)
359 throw SymEngineException(
"Error: field must be same.");
368 out.gf_monic(
temp_LC, outArg(out));
372GaloisFieldDict GaloisFieldDict::gf_diff()
const
375 GaloisFieldDict out = GaloisFieldDict({}, modulo_);
376 out.dict_.resize(
df, integer_class(0));
377 for (
unsigned i = 1; i <=
df; i++) {
378 if (dict_[i] != integer_class(0)) {
379 out.dict_[i - 1] = i * dict_[i];
380 mp_fdiv_r(out.dict_[i - 1], out.dict_[i - 1], modulo_);
387integer_class GaloisFieldDict::gf_eval(
const integer_class &a)
const
389 integer_class
res = 0
_z;
399GaloisFieldDict::gf_multi_eval(
const vec_integer_class &v)
const
401 vec_integer_class
res(v.size());
402 for (
unsigned int i = 0; i < v.size(); ++i)
403 res[i] = gf_eval(v[i]);
407bool GaloisFieldDict::gf_is_sqf()
const
412 GaloisFieldDict
monic;
415 return monic.is_one();
419GaloisFieldDict::gf_sqf_list()
const
430 gf_monic(
LC, outArg(
f));
432 GaloisFieldDict
F =
f.gf_diff();
433 if (
not F.dict_.empty()) {
434 GaloisFieldDict
g =
f.gf_gcd(
F);
435 GaloisFieldDict
h =
f /
g;
439 while (
not h.is_one()) {
440 GaloisFieldDict
G =
h.gf_gcd(
g);
441 GaloisFieldDict
H =
h /
G;
456 auto deg =
f.degree();
458 GaloisFieldDict
temp =
f;
459 for (
unsigned int i = 0; i <=
d; ++i) {
463 f.dict_.resize(
d + 1);
471GaloisFieldDict GaloisFieldDict::gf_sqf_part()
const
473 auto sqf = gf_sqf_list();
474 GaloisFieldDict
g = GaloisFieldDict::from_vec({1
_z}, modulo_);
482GaloisFieldDict GaloisFieldDict::gf_compose_mod(
const GaloisFieldDict &
g,
483 const GaloisFieldDict &
h)
const
485 if (
g.modulo_ !=
h.modulo_)
486 throw SymEngineException(
"Error: field must be same.");
487 if (
g.modulo_ != modulo_)
488 throw SymEngineException(
"Error: field must be same.");
489 if (
g.dict_.size() == 0)
492 = GaloisFieldDict::from_vec({*(
g.dict_.rbegin())}, modulo_);
493 if (
g.dict_.size() >= 2) {
494 for (
auto i =
g.dict_.size() - 2;; --i) {
505GaloisFieldDict GaloisFieldDict::gf_pow_mod(
const GaloisFieldDict &
f,
506 const unsigned long &n)
const
508 if (modulo_ !=
f.modulo_)
509 throw SymEngineException(
"Error: field must be same.");
511 return GaloisFieldDict::from_vec({1
_z}, modulo_);
512 GaloisFieldDict in =
f;
517 return f.gf_sqr() % (*this);
519 GaloisFieldDict
h = GaloisFieldDict::from_vec({1
_z}, modulo_);
531 in = in.gf_sqr() % *
this;
543 b[0] = GaloisFieldDict::from_vec({1
_z}, modulo_);
545 if (mp_get_ui(modulo_) < n) {
546 for (
unsigned i = 1; i < n; ++i) {
547 b[i] = b[i - 1].gf_lshift(modulo_);
551 b[1] = gf_pow_mod(GaloisFieldDict::from_vec({0
_z, 1
_z}, modulo_),
553 for (
unsigned i = 2; i < n; ++i) {
554 b[i] = b[i - 1] * b[1];
562GaloisFieldDict::gf_frobenius_map(
const GaloisFieldDict &
g,
565 if (modulo_ !=
g.modulo_)
566 throw SymEngineException(
"Error: field must be same.");
568 GaloisFieldDict
temp_out(*
this), out;
569 if (this->degree() >= m) {
576 out = GaloisFieldDict::from_vec({
temp_out.dict_[0]}, modulo_);
577 for (
unsigned i = 1; i <= m; ++i) {
587 const GaloisFieldDict &a,
const GaloisFieldDict &b,
588 const GaloisFieldDict &
c,
const unsigned long &n)
const
590 unsigned long n_val(n);
591 auto u = this->gf_compose_mod(a, b);
592 GaloisFieldDict v(b),
U,
V;
602 u += this->gf_compose_mod(
u, v);
603 v = gf_compose_mod(v, v);
606 auto temp = gf_compose_mod(
u,
V);
608 V = gf_compose_mod(v,
V);
616GaloisFieldDict::_gf_trace_map(
const GaloisFieldDict &
f,
const unsigned long &n,
619 GaloisFieldDict x =
f % (*this);
622 for (
unsigned i = 1; i < n; ++i) {
623 h = gf_frobenius_map(
h, b);
631GaloisFieldDict::gf_ddf_zassenhaus()
const
634 GaloisFieldDict
f(*
this);
635 GaloisFieldDict
g = GaloisFieldDict::from_vec({0
_z, 1
_z}, modulo_);
639 auto b =
f.gf_frobenius_monomial_base();
640 while (2 * i <=
f.degree()) {
641 g =
g.gf_frobenius_map(
f, b);
643 GaloisFieldDict
h =
f.gf_gcd(
g -
to_sub);
645 if (
not h.is_one()) {
649 b =
f.gf_frobenius_monomial_base();
653 if (
not(
f.is_one() ||
f.empty())) {
660GaloisFieldDict::_gf_pow_pnm1d2(
const GaloisFieldDict &
f,
const unsigned &n,
663 GaloisFieldDict
f_in(
f);
665 GaloisFieldDict
h,
r;
667 for (
unsigned i = 1; i < n; ++i) {
668 h =
h.gf_frobenius_map(*
this, b);
672 auto res = gf_pow_mod(
r, (mp_get_ui(modulo_) - 1) / 2);
676GaloisFieldDict GaloisFieldDict::gf_random(
const unsigned int &
n_val,
677 mp_randstate &state)
const
680 for (
unsigned i = 0; i <
n_val; ++i) {
681 state.urandomint(v[i], modulo_);
684 return GaloisFieldDict::from_vec(v, modulo_);
688GaloisFieldDict::gf_edf_zassenhaus(
const unsigned &n)
const
692 if (this->degree() <= n)
695 auto N = this->degree() / n;
699 b = this->gf_frobenius_monomial_base();
701 while (factors.
size() <
N) {
702 auto r = gf_random(2 * n - 1, state);
704 if (modulo_ == 2
_z) {
705 GaloisFieldDict
h =
r;
706 unsigned ub = 1 << (n *
N - 1);
707 for (
unsigned i = 0; i <
ub; ++i) {
708 r = gf_pow_mod(
r, 2);
713 GaloisFieldDict
h = _gf_pow_pnm1d2(
r, n, b);
718 if (!
g.is_one()
and g != (*
this)) {
719 factors =
g.gf_edf_zassenhaus(n);
720 auto to_add = ((*this) /
g).gf_edf_zassenhaus(n);
729GaloisFieldDict::gf_ddf_shoup()
const
734 GaloisFieldDict
f(*
this);
735 auto n = this->degree();
737 auto b = gf_frobenius_monomial_base();
738 auto x = GaloisFieldDict::from_vec({0
_z, 1
_z}, modulo_);
739 auto h = x.gf_frobenius_map(
f, b);
745 for (
unsigned i = 2; i <= k; ++i)
746 U[i] =
U[i - 1].gf_frobenius_map(*
this, b);
752 for (
unsigned i = 1; i + 1 <= k; ++i)
753 V[i] = this->gf_compose_mod(
V[i - 1],
h);
754 for (
unsigned i = 0; i <
V.size(); i++) {
755 h = GaloisFieldDict::from_vec({1
_z}, modulo_);
765 for (
auto rit =
U.rbegin();
rit !=
U.rend(); ++
rit) {
767 auto F =
g.gf_gcd(
h);
768 if (
not F.is_one()) {
769 unsigned temp = k * (i + 1) -
j;
782GaloisFieldDict::gf_edf_shoup(
const unsigned &n)
const
784 auto N = this->degree();
791 auto x = GaloisFieldDict::from_vec({0_z, 1_z}, modulo_);
793 auto r = gf_random(N - 1, state);
794 if (modulo_ == 2_z) {
795 auto h = gf_pow_mod(x, mp_get_ui(modulo_));
796 auto H = gf_trace_map(r, h, x, n - 1).second;
798 auto h2 = (*this) / h1;
799 factors = h1.gf_edf_shoup(n);
800 auto temp = h2.gf_edf_shoup(n);
801 factors.
insert(temp.begin(), temp.end());
803 auto b = gf_frobenius_monomial_base();
804 auto H = _gf_trace_map(r, n, b);
805 auto h = gf_pow_mod(H, (mp_get_ui(modulo_) - 1) / 2);
807 auto h2 = gf_gcd(h - 1_z);
808 auto h3 = (*this) / (h1 * h2);
809 factors = h1.gf_edf_shoup(n);
810 auto temp = h2.gf_edf_shoup(n);
811 factors.
insert(temp.begin(), temp.end());
812 temp = h3.gf_edf_shoup(n);
813 factors.
insert(temp.begin(), temp.end());
819GaloisFieldDict::gf_zassenhaus()
const
822 auto temp1 = gf_ddf_zassenhaus();
823 for (
auto &f : temp1) {
824 auto temp2 = f.first.gf_edf_zassenhaus(f.second);
825 factors.
insert(temp2.begin(), temp2.end());
831GaloisFieldDict::gf_shoup()
const
834 auto temp1 = gf_ddf_shoup();
835 for (
auto &f : temp1) {
836 auto temp2 = f.first.gf_edf_shoup(f.second);
837 factors.
insert(temp2.begin(), temp2.end());
843 GaloisFieldDict::DictLess>>
844GaloisFieldDict::gf_factor()
const
848 GaloisFieldDict monic;
849 gf_monic(lc, outArg(monic));
850 if (monic.degree() < 1)
853 = monic.gf_sqf_list();
854 for (
auto a : sqf_list) {
855 auto temp = (a.first).gf_zassenhaus();
857 factors.
insert({f, a.second});
Classes and functions relating to the binary operation of addition.
The lowest unit of symbolic representation.
GaloisField(const RCP< const Basic > &var, GaloisFieldDict &&dict)
Constructor of GaloisField class.
bool is_canonical(const GaloisFieldDict &dict) const
hash_t __hash__() const override
vec_basic get_args() const override
Returns the list of arguments.
int compare(const Basic &o) const override
static RCP< const Basic > from_dict(const RCP< const Number > &coef, map_basic_basic &&d)
Create a Mul from a dict.
Main namespace for SymEngine package.
RCP< const Integer > mod(const Integer &n, const Integer &d)
modulo round toward zero
void hash_combine(hash_t &seed, const T &v)
void insert(T1 &m, const T2 &first, const T3 &second)
int unified_compare(const T &a, const T &b)
std::enable_if< std::is_integral< T >::value, RCP< constInteger > >::type integer(T i)