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);
407 b.p_poly_reduce(b,b.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);
473 B.p_poly_reduce(B,B.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);
615 B.p_poly_reduce(B,B.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);
669 B.p_poly_reduce(B,B.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);
783 B.p_poly_reduce(B,B.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);
893 B.p_poly_reduce(B,B.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);
925 B.p_poly_reduce(B,B.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]);
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)