19 mpz_init_set_ui(coef[0],0);
24 p_poly::p_poly(
int n,
int p, mpz_t *a)
30 for (
int i=0;
i<=n;
i++)
32 mpz_mod_ui(a[
i],a[
i],
mod);
33 mpz_init_set(coef[
i], a[
i]);
50 void p_poly::p_poly_reduce(p_poly
f,
int p)
55 for (
int i=
f.deg;
i>=0;
i--)
57 mpz_mod_ui(coef[
i],
f.coef[
i],
p);
62 while(mpz_sgn(coef[
k])==0 &&
k>=0)
73 void p_poly::p_poly_add(
const p_poly a,
const p_poly
b)
81 for (
int i=0;
i<=
b.deg;
i++)
83 mpz_add(coef[
i],a.coef[
i],
b.coef[
i]);
86 for (
int i=
b.deg+1;
i<=a.deg;
i++)
88 mpz_init_set(coef[
i],a.coef[
i]);
93 while(mpz_divisible_ui_p(coef[
k],
mod)!=0 &&
k>=0)
99 else {p_poly_add(
b,a); }
105 void p_poly::p_poly_add_to(
const p_poly
g)
107 this->p_poly_add(*
this,
g);
111 void p_poly::p_poly_add_const(p_poly
f,
const mpz_t a)
113 if (
f.is_zero()==1 && mpz_divisible_ui_p(a,
f.mod)==0)
116 else if (mpz_divisible_ui_p(a,
f.mod)==0)
119 mpz_add(coef[0],coef[0],a);
132 void p_poly::p_poly_add_const_to(
const mpz_t a)
134 this->p_poly_add_const(*
this,a);
138 void p_poly::p_poly_add_mon(
const p_poly
f, mpz_t a,
int i)
141 if (
i<=deg && is_zero()==0)
143 mpz_add(coef[
i],coef[
i],a);
145 else if (is_zero()==1 && mpz_divisible_ui_p(a,
f.mod)==0)
148 for(
int j=0;
j<=
i;
j++)
150 mpz_init_set_ui(coef[
j],0);
153 mpz_init_set_ui(temp,0);
154 mpz_mod_ui(temp,a,
mod);
155 mpz_add(coef[
i],coef[
i],temp);
158 else if(
i>deg && mpz_divisible_ui_p(a,
f.mod)==0)
161 for(
int j=
i;
j>deg;
j--)
163 mpz_init_set_ui(coef[
j],0);
166 mpz_init_set_ui(temp,0);
167 mpz_mod_ui(temp,a,
mod);
168 mpz_add(coef[
i],coef[
i],temp);
180 void p_poly::p_poly_add_mon_to(mpz_t a,
int i)
183 if (
i<=deg && is_zero()==0)
185 mpz_add(coef[
i],coef[
i],a);
187 else if (is_zero()==1 && mpz_divisible_ui_p(a,
mod)==0)
190 for(
int j=0;
j<=
i;
j++)
192 mpz_init_set_ui(coef[
j],0);
195 mpz_init_set_ui(temp,0);
196 mpz_mod_ui(temp,a,
mod);
197 mpz_add(coef[
i],coef[
i],temp);
200 else if(
i>deg && mpz_divisible_ui_p(a,
mod)==0)
203 for(
int j=
i;
j>deg;
j--)
205 mpz_init_set_ui(coef[
j],0);
208 mpz_init_set_ui(temp,0);
209 mpz_mod_ui(temp,a,
mod);
210 mpz_add(coef[
i],coef[
i],temp);
221 void p_poly::p_poly_sub(
const p_poly a,
const p_poly
b)
229 for (
int i=0;
i<=
b.deg;
i++)
231 mpz_sub(coef[
i],a.coef[
i],
b.coef[
i]);
234 for (
int i=
b.deg+1;
i<=a.deg;
i++)
236 mpz_init_set(coef[
i],a.coef[
i]);
241 while(mpz_divisible_ui_p(coef[
k],
mod)!=0 &&
k>=0)
246 else {p_poly_sub(
b,a);p_poly_neg(); }
253 void p_poly::p_poly_sub_to(
const p_poly
b)
255 this->p_poly_sub(*
this,
b);
259 void p_poly::p_poly_sub_const(p_poly
f,
const mpz_t a)
269 mpz_sub(coef[0],coef[0],a);
281 void p_poly::p_poly_sub_const_to(
const mpz_t a)
283 this->p_poly_sub_const(*
this,a);
288 void p_poly::p_poly_sub_mon(
const p_poly
f , mpz_t a,
int i)
292 p_poly_add_mon(
f,temp,
i);
296 void p_poly::p_poly_sub_mon_to(mpz_t a,
int i)
300 p_poly_add_mon_to(temp,
i);
307 void p_poly::p_poly_mon_mult( p_poly
f,
int n)
315 for (
int i=deg;
i>=n;
i--)
317 mpz_init_set(coef[
i],
f.coef[
i-n]);
319 for (
int i=n-1;
i>=0;
i--)
321 mpz_init_set_ui(coef[
i],0);
331 void p_poly::p_poly_mon_mult_to(
const int n)
333 this->p_poly_mon_mult(*
this,n);
339 void p_poly::p_poly_scalar_mult(
const p_poly
g,
const mpz_t n)
341 if (mpz_divisible_ui_p(n,
g.mod)!=0)
349 mpz_init_set_ui(temp,0);
350 for(
int i=0;
i<=deg;
i++)
352 mpz_mul(temp,n,
g.coef[
i]);
353 mpz_init_set(coef[
i],temp);
360 void p_poly::p_poly_scalar_mult(
const mpz_t n,
const p_poly
g)
362 if (mpz_divisible_ui_p(n,
g.mod)!=0)
371 mpz_init_set_ui(temp,0);
372 for(
int i=0;
i<=deg;
i++)
374 mpz_mul(temp,n,
g.coef[
i]);
375 mpz_init_set(coef[
i],temp);
385 void p_poly::p_poly_scalar_mult_to(
const mpz_t n)
387 this->p_poly_scalar_mult(*
this,n);
394 void p_poly::p_poly_neg()
396 for (
int i=0;
i<=deg;
i++)
398 mpz_neg(coef[
i],coef[
i]);
403 void p_poly::p_poly_mult_n(p_poly a,p_poly
b)
406 a.p_poly_reduce(a,a.mod);
409 if (a.is_zero()==1 ||
b.is_zero()==1)
414 mpz_init_set_ui(temp,0);
421 for(
int i=a.deg+1;
i<=deg;
i++)
423 mpz_init_set_ui(atemp.coef[
i],0);
425 for(
int i=
b.deg+1;
i<=deg;
i++)
427 mpz_init_set_ui(btemp.coef[
i],0);
433 for (
int k=0;
k<=deg;
k++)
435 mpz_init_set_ui(coef[
k],0);
436 for (
int i=0;
i<=
k;
i++)
438 mpz_mul(temp,atemp.coef[
i],btemp.coef[
k-
i]);
439 mpz_add(coef[
k],coef[
k],temp);
455 void p_poly::p_poly_mult_n_to(
const p_poly
g)
457 this->p_poly_mult_n(*
this,
g);
462 void p_poly::p_poly_mult_ka( p_poly
A, p_poly
B)
465 if (
A.is_zero()==1 ||
B.is_zero()==1)
472 A.p_poly_reduce(
A,
A.mod);
477 if(
A.deg>=
B.deg){n=
A.deg+1;}
481 n = static_cast<int>(
pow(2,n));
486 mpz_mul(AB,
A.coef[0],
B.coef[0]);
487 p_poly_set(AB,
A.mod);
488 this->p_poly_reduce(*
this,
A.mod);
493 p_poly Au, Al, Bu, Bl;
494 Au.p_poly_mon_div(
A,n/2);
495 Al.p_poly_mon_div_rem(
A,n/2);
496 Bu.p_poly_mon_div(
B,n/2);
497 Bl.p_poly_mon_div_rem(
B,n/2);
499 Alu.p_poly_add(Al,Au);
500 Blu.p_poly_add(Bl,Bu);
504 D0.p_poly_mult_ka(Al,Bl);
505 D1.p_poly_mult_ka(Au,Bu);
506 D01.p_poly_mult_ka(Alu,Blu);
510 D01.p_poly_sub_to(D0);
511 D01.p_poly_sub_to(D1);
512 D01.p_poly_mon_mult_to(n/2);
513 D1.p_poly_mon_mult_to(n);
514 D1.p_poly_add_to(D01);
515 D1.p_poly_add_to(D0);
522 while(mpz_divisible_ui_p(coef[
k],
mod)!=0 &&
k>=0)
531 void p_poly::p_poly_scalar_div(
const p_poly
g,
const mpz_t n)
534 if (mpz_divisible_ui_p(n,
g.mod)==0)
542 mpz_init_set_ui(temp,0);
543 mpz_init_set_ui(
p,
mod);
544 for(
int i=0;
i<=deg;
i++)
546 mpz_invert(temp,n,
p);
547 mpz_mul(temp,
g.coef[
i],temp);
548 mpz_init_set(coef[
i],temp);
559 void p_poly::p_poly_scalar_div_to(
const mpz_t n)
561 this->p_poly_scalar_div(*
this,n);
565 void p_poly::p_poly_mon_div(
const p_poly
f,
const int n)
576 for (
int i=0;
i<=
f.deg-n;
i++)
578 mpz_init_set(coef[
i],
f.coef[n+
i]);
584 void p_poly::p_poly_mon_div_rem(
const p_poly
f,
const int n)
596 for (
int i=0;
i<=n-1;
i++)
598 mpz_init_set(coef[
i],
f.coef[
i]);
608 void p_poly::p_poly_div_rem( p_poly
A, p_poly
B)
614 A.p_poly_reduce(
A,
A.mod);
623 mpz_init_set_ui(
p,
A.mod);
624 mpz_init_set_ui(a,0);
625 mpz_init_set_ui(u,0);
628 mpz_invert(u,
B.coef[
B.deg],
p);
634 mpz_mul(a,
R.coef[
R.deg],u);
637 temp.p_poly_mon_mult(
B,
i);
638 temp.p_poly_scalar_mult_to(a);
640 R.p_poly_sub_to(temp);
653 void p_poly::p_poly_div_rem_to(
const p_poly
B)
655 this->p_poly_div_rem(*
this,
B);
663 void p_poly::p_poly_div(p_poly &
Q, p_poly &
R, p_poly
A, p_poly
B)
668 A.p_poly_reduce(
A,
A.mod);
680 mpz_init_set_ui(
p,
A.mod);
681 mpz_init_set_ui(a,0);
682 mpz_init_set_ui(
b,0);
684 mpz_invert(
b,
B.coef[
B.deg],
p);
690 mpz_mul(a,
R.coef[
R.deg],
b);
693 temp.p_poly_mon_mult(
B,
i);
694 temp.p_poly_scalar_mult_to(a);
696 R.p_poly_sub_to(temp);
698 Q.p_poly_add_mon_to(a,
i);
700 R.p_poly_reduce(
R,
R.mod);
701 Q.p_poly_reduce(
Q,
Q.mod);
719 void p_poly::p_poly_div_to(p_poly &
Q,p_poly &
R, p_poly
B)
721 this->p_poly_div(
Q ,
R,*
this,
B);
728 void p_poly::p_poly_multadd_to(
const p_poly
b,
const p_poly c)
735 void p_poly::p_poly_multsub_to(
const p_poly
b,
const p_poly c)
757 void p_poly::p_poly_horner(mpz_t erg,
const mpz_t u)
761 mpz_init_set(erg,coef[deg]);
762 for (
int i=deg;
i>=1;
i--)
765 mpz_add(erg,erg,coef[
i-1]);
769 mpz_mod_ui(erg,erg,
mod);
779 void p_poly::p_poly_horner_p_poly( p_poly
A, p_poly
B)
782 A.p_poly_reduce(
A,
A.mod);
785 p_poly_set(
A.coef[
A.deg],
A.mod);
786 for (
int i=
A.deg;
i>=1;
i--)
789 p_poly_add_const_to(
A.coef[
i-1]);
803 void p_poly::p_poly_set(
const p_poly
b)
809 for(
int i=0;
i<=deg;
i++)
811 mpz_init_set(coef[
i],
b.coef[
i]);
817 void p_poly::p_poly_set(
const mpz_t
b,
int p)
822 if (mpz_divisible_ui_p(
b,
mod)!=0)
827 mpz_init_set(temp,
b);
828 mpz_mod_ui(temp,temp,
p);
829 mpz_init_set(coef[0],
b);
835 void p_poly::p_poly_set_zero()
843 int p_poly::is_equal(
const p_poly
g)
const
849 for (
int i=deg;
i>=0;
i--)
851 if (mpz_cmp(coef[
i],
g.coef[
i])!=0)
859 int p_poly::is_zero()
const
868 int p_poly::is_one()
const
872 if (mpz_cmp_ui(coef[0],1)==0) {
return 1; }
878 int p_poly::is_monic()
const
880 if (mpz_cmpabs_ui(coef[deg],1)==0)
888 void p_poly::p_poly_gcd( p_poly
A, p_poly
B)
892 A.p_poly_reduce(
A,
A.mod);
897 else if (
B.is_zero()==1)
907 while (Bpp.is_zero()==0)
909 R.p_poly_div_rem(App,Bpp);
920 void p_poly::p_poly_extgcd(p_poly &
s,p_poly &t,p_poly &
g, p_poly
A, p_poly
B)
924 A.p_poly_reduce(
A,
A.mod);
929 p_poly_extgcd(t,
s,
g,
B,
A);
930 else if (
B.is_zero()==1)
936 mpz_init_set_ui(temp,1);
937 s.p_poly_set(temp,
A.mod);
943 mpz_init_set_ui(temp,1);
954 S1.p_poly_set(temp,
A.mod);
956 S2.p_poly_set_zero();
962 T1.p_poly_set_zero();
965 T2.p_poly_set(temp,
A.mod);
971 while (R2.is_zero()!=1)
973 p_poly_div(
Q,R3,R1,R2);
975 S3.p_poly_mult_n(
Q,S2);
977 S3.p_poly_add_to(S1);
979 T3.p_poly_mult_n(
Q,
T2);
981 T3.p_poly_add_to(
T1);
1003 void p_poly::p_poly_insert()
1006 cout <<
"Bitte geben Sie ein p_polynom ein! Zunächst den Grad: " << endl;
1008 cout <<
"Jetzt den modul: " << endl;
1011 for (
int i=0;
i<=deg;
i++)
1013 mpz_init_set_ui(coef[
i],0);
1014 printf(
"Geben Sie nun f[%i] ein:",
i);
1015 mpz_inp_str(coef[
i],stdin, 10);
1018 this->p_poly_reduce(*
this,
mod);
1024 void p_poly::p_poly_print()
1029 this->p_poly_reduce(*
this,
mod);
1033 cout <<
"0" <<
"\n" <<endl;
1036 for (
int i=deg;
i>=1;
i--)
1038 mpz_out_str(stdout,10, coef[
i]);
1041 mpz_out_str(stdout,10, coef[0]);