20 mpz_init_set_ui(coef[0],0);
25 p_poly::p_poly(
int n,
int p, mpz_t *a)
31 for (
int i=0;
i<=n;
i++)
33 mpz_mod_ui(a[
i],a[
i],
mod);
34 mpz_init_set(coef[
i], a[
i]);
51 void p_poly::p_poly_reduce(p_poly
f,
int p)
56 for (
int i=
f.deg;
i>=0;
i--)
58 mpz_mod_ui(coef[
i],
f.coef[
i],
p);
63 while(mpz_sgn(coef[
k])==0 &&
k>=0)
74 void p_poly::p_poly_add(
const p_poly a,
const p_poly
b)
82 for (
int i=0;
i<=
b.deg;
i++)
84 mpz_add(coef[
i],a.coef[
i],
b.coef[
i]);
87 for (
int i=
b.deg+1;
i<=a.deg;
i++)
89 mpz_init_set(coef[
i],a.coef[
i]);
94 while(mpz_divisible_ui_p(coef[
k],
mod)!=0 &&
k>=0)
100 else {p_poly_add(
b,a); }
106 void p_poly::p_poly_add_to(
const p_poly
g)
108 this->p_poly_add(*
this,
g);
112 void p_poly::p_poly_add_const(p_poly
f,
const mpz_t a)
114 if (
f.is_zero()==1 && mpz_divisible_ui_p(a,
f.mod)==0)
117 else if (mpz_divisible_ui_p(a,
f.mod)==0)
120 mpz_add(coef[0],coef[0],a);
133 void p_poly::p_poly_add_const_to(
const mpz_t a)
135 this->p_poly_add_const(*
this,a);
139 void p_poly::p_poly_add_mon(
const p_poly
f, mpz_t a,
int i)
142 if (
i<=deg && is_zero()==0)
144 mpz_add(coef[
i],coef[
i],a);
146 else if (is_zero()==1 && mpz_divisible_ui_p(a,
f.mod)==0)
149 for(
int j=0;
j<=
i;
j++)
151 mpz_init_set_ui(coef[
j],0);
154 mpz_init_set_ui(temp,0);
155 mpz_mod_ui(temp,a,
mod);
156 mpz_add(coef[
i],coef[
i],temp);
159 else if(
i>deg && mpz_divisible_ui_p(a,
f.mod)==0)
162 for(
int j=
i;
j>deg;
j--)
164 mpz_init_set_ui(coef[
j],0);
167 mpz_init_set_ui(temp,0);
168 mpz_mod_ui(temp,a,
mod);
169 mpz_add(coef[
i],coef[
i],temp);
181 void p_poly::p_poly_add_mon_to(mpz_t a,
int i)
184 if (
i<=deg && is_zero()==0)
186 mpz_add(coef[
i],coef[
i],a);
188 else if (is_zero()==1 && mpz_divisible_ui_p(a,
mod)==0)
191 for(
int j=0;
j<=
i;
j++)
193 mpz_init_set_ui(coef[
j],0);
196 mpz_init_set_ui(temp,0);
197 mpz_mod_ui(temp,a,
mod);
198 mpz_add(coef[
i],coef[
i],temp);
201 else if(
i>deg && mpz_divisible_ui_p(a,
mod)==0)
204 for(
int j=
i;
j>deg;
j--)
206 mpz_init_set_ui(coef[
j],0);
209 mpz_init_set_ui(temp,0);
210 mpz_mod_ui(temp,a,
mod);
211 mpz_add(coef[
i],coef[
i],temp);
222 void p_poly::p_poly_sub(
const p_poly a,
const p_poly
b)
230 for (
int i=0;
i<=
b.deg;
i++)
232 mpz_sub(coef[
i],a.coef[
i],
b.coef[
i]);
235 for (
int i=
b.deg+1;
i<=a.deg;
i++)
237 mpz_init_set(coef[
i],a.coef[
i]);
242 while(mpz_divisible_ui_p(coef[
k],
mod)!=0 &&
k>=0)
247 else {p_poly_sub(
b,a);p_poly_neg(); }
254 void p_poly::p_poly_sub_to(
const p_poly
b)
256 this->p_poly_sub(*
this,
b);
260 void p_poly::p_poly_sub_const(p_poly
f,
const mpz_t a)
270 mpz_sub(coef[0],coef[0],a);
282 void p_poly::p_poly_sub_const_to(
const mpz_t a)
284 this->p_poly_sub_const(*
this,a);
289 void p_poly::p_poly_sub_mon(
const p_poly
f , mpz_t a,
int i)
293 p_poly_add_mon(
f,temp,
i);
297 void p_poly::p_poly_sub_mon_to(mpz_t a,
int i)
301 p_poly_add_mon_to(temp,
i);
308 void p_poly::p_poly_mon_mult( p_poly
f,
int n)
316 for (
int i=deg;
i>=n;
i--)
318 mpz_init_set(coef[
i],
f.coef[
i-n]);
320 for (
int i=n-1;
i>=0;
i--)
322 mpz_init_set_ui(coef[
i],0);
332 void p_poly::p_poly_mon_mult_to(
const int n)
334 this->p_poly_mon_mult(*
this,n);
340 void p_poly::p_poly_scalar_mult(
const p_poly
g,
const mpz_t n)
342 if (mpz_divisible_ui_p(n,
g.mod)!=0)
350 mpz_init_set_ui(temp,0);
351 for(
int i=0;
i<=deg;
i++)
353 mpz_mul(temp,n,
g.coef[
i]);
354 mpz_init_set(coef[
i],temp);
361 void p_poly::p_poly_scalar_mult(
const mpz_t n,
const p_poly
g)
363 if (mpz_divisible_ui_p(n,
g.mod)!=0)
372 mpz_init_set_ui(temp,0);
373 for(
int i=0;
i<=deg;
i++)
375 mpz_mul(temp,n,
g.coef[
i]);
376 mpz_init_set(coef[
i],temp);
386 void p_poly::p_poly_scalar_mult_to(
const mpz_t n)
388 this->p_poly_scalar_mult(*
this,n);
395 void p_poly::p_poly_neg()
397 for (
int i=0;
i<=deg;
i++)
399 mpz_neg(coef[
i],coef[
i]);
404 void p_poly::p_poly_mult_n(p_poly a,p_poly
b)
407 a.p_poly_reduce(a,a.mod);
410 if (a.is_zero()==1 ||
b.is_zero()==1)
415 mpz_init_set_ui(temp,0);
422 for(
int i=a.deg+1;
i<=deg;
i++)
424 mpz_init_set_ui(atemp.coef[
i],0);
426 for(
int i=
b.deg+1;
i<=deg;
i++)
428 mpz_init_set_ui(btemp.coef[
i],0);
434 for (
int k=0;
k<=deg;
k++)
436 mpz_init_set_ui(coef[
k],0);
437 for (
int i=0;
i<=
k;
i++)
439 mpz_mul(temp,atemp.coef[
i],btemp.coef[
k-
i]);
440 mpz_add(coef[
k],coef[
k],temp);
456 void p_poly::p_poly_mult_n_to(
const p_poly
g)
458 this->p_poly_mult_n(*
this,
g);
463 void p_poly::p_poly_mult_ka( p_poly
A, p_poly
B)
466 if (
A.is_zero()==1 ||
B.is_zero()==1)
473 A.p_poly_reduce(
A,
A.mod);
478 if(
A.deg>=
B.deg){n=
A.deg+1;}
482 n = static_cast<int>(
pow(2,n));
487 mpz_mul(AB,
A.coef[0],
B.coef[0]);
488 p_poly_set(AB,
A.mod);
489 this->p_poly_reduce(*
this,
A.mod);
494 p_poly Au, Al, Bu, Bl;
495 Au.p_poly_mon_div(
A,n/2);
496 Al.p_poly_mon_div_rem(
A,n/2);
497 Bu.p_poly_mon_div(
B,n/2);
498 Bl.p_poly_mon_div_rem(
B,n/2);
500 Alu.p_poly_add(Al,Au);
501 Blu.p_poly_add(Bl,Bu);
505 D0.p_poly_mult_ka(Al,Bl);
506 D1.p_poly_mult_ka(Au,Bu);
507 D01.p_poly_mult_ka(Alu,Blu);
511 D01.p_poly_sub_to(D0);
512 D01.p_poly_sub_to(D1);
513 D01.p_poly_mon_mult_to(n/2);
514 D1.p_poly_mon_mult_to(n);
515 D1.p_poly_add_to(D01);
516 D1.p_poly_add_to(D0);
523 while(mpz_divisible_ui_p(coef[
k],
mod)!=0 &&
k>=0)
532 void p_poly::p_poly_scalar_div(
const p_poly
g,
const mpz_t n)
535 if (mpz_divisible_ui_p(n,
g.mod)==0)
543 mpz_init_set_ui(temp,0);
544 mpz_init_set_ui(
p,
mod);
545 for(
int i=0;
i<=deg;
i++)
547 mpz_invert(temp,n,
p);
548 mpz_mul(temp,
g.coef[
i],temp);
549 mpz_init_set(coef[
i],temp);
560 void p_poly::p_poly_scalar_div_to(
const mpz_t n)
562 this->p_poly_scalar_div(*
this,n);
566 void p_poly::p_poly_mon_div(
const p_poly
f,
const int n)
577 for (
int i=0;
i<=
f.deg-n;
i++)
579 mpz_init_set(coef[
i],
f.coef[n+
i]);
585 void p_poly::p_poly_mon_div_rem(
const p_poly
f,
const int n)
597 for (
int i=0;
i<=n-1;
i++)
599 mpz_init_set(coef[
i],
f.coef[
i]);
609 void p_poly::p_poly_div_rem( p_poly
A, p_poly
B)
615 A.p_poly_reduce(
A,
A.mod);
624 mpz_init_set_ui(
p,
A.mod);
625 mpz_init_set_ui(a,0);
626 mpz_init_set_ui(u,0);
629 mpz_invert(u,
B.coef[
B.deg],
p);
635 mpz_mul(a,
R.coef[
R.deg],u);
638 temp.p_poly_mon_mult(
B,
i);
639 temp.p_poly_scalar_mult_to(a);
641 R.p_poly_sub_to(temp);
654 void p_poly::p_poly_div_rem_to(
const p_poly
B)
656 this->p_poly_div_rem(*
this,
B);
664 void p_poly::p_poly_div(p_poly &
Q, p_poly &
R, p_poly
A, p_poly
B)
669 A.p_poly_reduce(
A,
A.mod);
681 mpz_init_set_ui(
p,
A.mod);
682 mpz_init_set_ui(a,0);
683 mpz_init_set_ui(
b,0);
685 mpz_invert(
b,
B.coef[
B.deg],
p);
691 mpz_mul(a,
R.coef[
R.deg],
b);
694 temp.p_poly_mon_mult(
B,
i);
695 temp.p_poly_scalar_mult_to(a);
697 R.p_poly_sub_to(temp);
699 Q.p_poly_add_mon_to(a,
i);
701 R.p_poly_reduce(
R,
R.mod);
702 Q.p_poly_reduce(
Q,
Q.mod);
720 void p_poly::p_poly_div_to(p_poly &
Q,p_poly &
R, p_poly
B)
722 this->p_poly_div(
Q ,
R,*
this,
B);
729 void p_poly::p_poly_multadd_to(
const p_poly
b,
const p_poly c)
736 void p_poly::p_poly_multsub_to(
const p_poly
b,
const p_poly c)
758 void p_poly::p_poly_horner(mpz_t erg,
const mpz_t u)
762 mpz_init_set(erg,coef[deg]);
763 for (
int i=deg;
i>=1;
i--)
766 mpz_add(erg,erg,coef[
i-1]);
770 mpz_mod_ui(erg,erg,
mod);
780 void p_poly::p_poly_horner_p_poly( p_poly
A, p_poly
B)
783 A.p_poly_reduce(
A,
A.mod);
786 p_poly_set(
A.coef[
A.deg],
A.mod);
787 for (
int i=
A.deg;
i>=1;
i--)
790 p_poly_add_const_to(
A.coef[
i-1]);
804 void p_poly::p_poly_set(
const p_poly
b)
810 for(
int i=0;
i<=deg;
i++)
812 mpz_init_set(coef[
i],
b.coef[
i]);
818 void p_poly::p_poly_set(
const mpz_t
b,
int p)
823 if (mpz_divisible_ui_p(
b,
mod)!=0)
828 mpz_init_set(temp,
b);
829 mpz_mod_ui(temp,temp,
p);
830 mpz_init_set(coef[0],
b);
836 void p_poly::p_poly_set_zero()
844 int p_poly::is_equal(
const p_poly
g)
const 850 for (
int i=deg;
i>=0;
i--)
852 if (mpz_cmp(coef[
i],
g.coef[
i])!=0)
860 int p_poly::is_zero()
const 869 int p_poly::is_one()
const 873 if (mpz_cmp_ui(coef[0],1)==0) {
return 1; }
879 int p_poly::is_monic()
const 881 if (mpz_cmpabs_ui(coef[deg],1)==0)
889 void p_poly::p_poly_gcd( p_poly
A, p_poly
B)
893 A.p_poly_reduce(
A,
A.mod);
898 else if (
B.is_zero()==1)
908 while (Bpp.is_zero()==0)
910 R.p_poly_div_rem(App,Bpp);
921 void p_poly::p_poly_extgcd(p_poly &
s,p_poly &t,p_poly &
g, p_poly
A, p_poly
B)
925 A.p_poly_reduce(
A,
A.mod);
930 p_poly_extgcd(t,
s,
g,
B,
A);
931 else if (
B.is_zero()==1)
937 mpz_init_set_ui(temp,1);
938 s.p_poly_set(temp,
A.mod);
944 mpz_init_set_ui(temp,1);
955 S1.p_poly_set(temp,
A.mod);
957 S2.p_poly_set_zero();
963 T1.p_poly_set_zero();
966 T2.p_poly_set(temp,
A.mod);
972 while (R2.is_zero()!=1)
974 p_poly_div(
Q,R3,R1,R2);
976 S3.p_poly_mult_n(
Q,S2);
978 S3.p_poly_add_to(S1);
980 T3.p_poly_mult_n(
Q,
T2);
982 T3.p_poly_add_to(
T1);
1004 void p_poly::p_poly_insert()
1007 cout <<
"Bitte geben Sie ein p_polynom ein! Zunächst den Grad: " << endl;
1009 cout <<
"Jetzt den modul: " << endl;
1012 for (
int i=0;
i<=deg;
i++)
1014 mpz_init_set_ui(coef[
i],0);
1015 printf(
"Geben Sie nun f[%i] ein:",
i);
1016 mpz_inp_str(coef[
i],stdin, 10);
1019 this->p_poly_reduce(*
this,
mod);
1025 void p_poly::p_poly_print()
1030 this->p_poly_reduce(*
this,
mod);
1034 cout <<
"0" <<
"\n" <<endl;
1037 for (
int i=deg;
i>=1;
i--)
1039 mpz_out_str(stdout,10, coef[
i]);
1042 mpz_out_str(stdout,10, coef[0]);
const CanonicalForm int s
gmp_float log(const gmp_float &a)
const signed long ceil(const ampf< Precision > &x)
Rational pow(const Rational &a, int e)