Public Member Functions | Private Member Functions | Private Attributes
lattice Class Reference

#include <lattice.h>

Public Member Functions

 lattice (bigintmat *basis)
 
 ~lattice ()
 
bool LLL ()
 
bool LLL (number &c)
 
bigintmatget_basis ()
 
bigintmatget_reduced_basis ()
 
bigintmatget_transformation_matrix ()
 
bigintmatenumerate_all (number a)
 
bigintmatenumerate_next (number a, bigintmat *x)
 
bigintmatenumerate_next (number a)
 
bigintmatenumerate_next (bigintmat *x)
 
bigintmatenumerate_next ()
 

Private Member Functions

void RED (int k, int l)
 
void SWAP (int k, int k_max)
 
void SWAPG (int k, int k_max)
 
bool gram_schmidt (int k)
 
void gram_schmidt_MLLL (int k)
 
void compute_gram_matrix ()
 
number enumerate_get_next ()
 
bool quadratic_supplement ()
 
void increase_x (int index)
 
number check_bound (int index)
 

Private Attributes

bigintmat ** basis
 
bigintmatgram_matrix
 
int n
 
int m
 
coeffs coef
 
number c
 
bigintmat ** b
 
bigintmat ** b_star
 
number * B
 
bigintmatH
 
bigintmatmy
 
number * d
 
int rank
 
bool trans_matrix
 
bool independentVectors
 
bool integral
 
bigintmatQ
 
bigintmatx
 
number * bound
 
coeffs out_coef
 

Detailed Description

Definition at line 6 of file lattice.h.

Constructor & Destructor Documentation

◆ lattice()

lattice::lattice ( bigintmat basis)

Definition at line 52 of file lattice.cc.

52  {
53  DEBUG_BLOCK(true);
54  DEBUG_PRINT(("Creating new lattice..."));
55  n = basismatrix->cols();
56  m = basismatrix->rows();
57  out_coef = basismatrix->basecoeffs();
58  DEBUG_PRINT(("always set coef =out_coef"));
59  coef =out_coef;
60 
61  //NOTE: Add transformation from rings to fields here
62  // exact <-> rounded
63 
64  basis = new bigintmat*[n+1]; //basis[0] is not used
65  basis[0] = NULL;
66  for(int i=1; i<=n; i++) {
67  basis[i] = new bigintmat(m,1,coef);
68  basismatrix->getcol(i,basis[i]);
69  }
70  gram_matrix = bimCopy(basismatrix);
71  c = NULL;
72  B = NULL;
73  b = NULL;
74  b_star = NULL;
75  H = NULL;
76  my = NULL;
77  Q = NULL;
78  rank = 0;
79  independentVectors = true;
80  integral = true;
81  trans_matrix = true;
82 
83  //for enumeration
84  x = NULL;
85  bound = NULL;
86 
87  DEBUG_PRINT(("Done\n"));
88 }
int rank
Definition: lattice.h:46
bigintmat * Q
Definition: lattice.h:58
bigintmat * gram_matrix
Definition: lattice.h:14
bool trans_matrix
Definition: lattice.h:49
int n
Definition: lattice.h:17
bigintmat ** b
Definition: lattice.h:28
Matrices of numbers.
Definition: bigintmat.h:51
bigintmat * my
Definition: lattice.h:40
number * bound
Definition: lattice.h:64
coeffs out_coef
Definition: lattice.h:67
bigintmat ** b_star
Definition: lattice.h:31
bigintmat * x
Definition: lattice.h:61
bool independentVectors
Definition: lattice.h:52
bigintmat * bimCopy(const bigintmat *b)
same as copy constructor - apart from it being able to accept NULL as input
Definition: bigintmat.cc:405
int i
Definition: cfEzgcd.cc:125
bigintmat * H
Definition: lattice.h:37
#define NULL
Definition: omList.c:10
number c
Definition: lattice.h:25
int m
Definition: lattice.h:20
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
bool integral
Definition: lattice.h:55
#define DEBUG_BLOCK(x)
Definition: lattice.cc:29
number * B
Definition: lattice.h:34

◆ ~lattice()

lattice::~lattice ( )

Definition at line 90 of file lattice.cc.

90  {
91  DEBUG_BLOCK(true);
92  DEBUG_PRINT(("Deleting lattice..."));
93 
94  if(basis != NULL) {
95  for(int i=0; i<=n; i++) {
96  delete basis[i];
97  }
98  delete[] basis;
99  }
100 
101  if(b != NULL) {
102  for(int i=0; i<=n; i++) {
103  delete b[i];
104  }
105  delete[] b;
106  }
107 
108  if(b_star != NULL) {
109  for(int i=0; i<=n; i++) {
110  delete b_star[i];
111  }
112  delete[] b_star;
113  }
114 
115  delete H;
116 
117  delete my;
118 
119  delete[] B;
120 
121  n_Delete(&c,coef);
122 
123  delete Q;
124 
125  DEBUG_PRINT(("Done\n"));
126 }
bigintmat * Q
Definition: lattice.h:58
int n
Definition: lattice.h:17
bigintmat ** b
Definition: lattice.h:28
bigintmat * my
Definition: lattice.h:40
bigintmat ** b_star
Definition: lattice.h:31
bigintmat ** basis
Definition: lattice.h:11
int i
Definition: cfEzgcd.cc:125
bigintmat * H
Definition: lattice.h:37
#define NULL
Definition: omList.c:10
number c
Definition: lattice.h:25
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
#define DEBUG_BLOCK(x)
Definition: lattice.cc:29
number * B
Definition: lattice.h:34

Member Function Documentation

◆ check_bound()

number lattice::check_bound ( int  index)
inlineprivate

Definition at line 855 of file lattice.cc.

855  {
856  DEBUG_BLOCK(true);DEBUG_PRINT(("check bound\n"));DEBUG_VAR(index);
857  number check = n_Init(0,coef);DEBUG_PRINT(("x:\n"));x->Print();
858  for(int i=index + 1;i<=Q->cols();i++){DEBUG_VAR(i);
859  number mult = n_Mult(x->view(i,1),Q->view(index,i),coef);
860  n_InpAdd(check,mult,coef);
861  n_Delete(&mult,coef);
862  }
863  n_InpAdd(check, x->view(index,1), coef);
864  n_InpMult(check, check, coef);
865  n_InpMult(check, Q->get(index,index), coef);
866  return check;
867 }
bigintmat * Q
Definition: lattice.h:58
int check
Definition: libparse.cc:1104
static FORCE_INLINE void n_InpMult(number &a, number b, const coeffs r)
multiplication of &#39;a&#39; and &#39;b&#39;; replacement of &#39;a&#39; by the product a*b
Definition: coeffs.h:642
#define DEBUG_VAR(x)
Definition: lattice.cc:35
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
bigintmat * x
Definition: lattice.h:61
static FORCE_INLINE void n_InpAdd(number &a, number b, const coeffs r)
addition of &#39;a&#39; and &#39;b&#39;; replacement of &#39;a&#39; by the sum a+b
Definition: coeffs.h:647
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:637
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:125
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:443
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:647
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
number get(int i, int j) const
get a copy of an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:119
#define DEBUG_BLOCK(x)
Definition: lattice.cc:29

◆ compute_gram_matrix()

void lattice::compute_gram_matrix ( )
inlineprivate

Definition at line 828 of file lattice.cc.

828  {
829  if(gram_matrix != NULL) {
830  delete gram_matrix;
831  gram_matrix = NULL;
832  }
833  gram_matrix = new bigintmat(n,n,coef);
834  for(int i=1; i<=n; i++) {
835  for(int j=1; j<=n; j++) {
837  }
838  }
839 }
int j
Definition: facHensel.cc:105
bigintmat * gram_matrix
Definition: lattice.h:14
int n
Definition: lattice.h:17
Matrices of numbers.
Definition: bigintmat.h:51
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition: bigintmat.cc:95
bigintmat ** basis
Definition: lattice.h:11
int i
Definition: cfEzgcd.cc:125
number scalarproduct(bigintmat *a, bigintmat *b)
Definition: lattice.cc:915
#define NULL
Definition: omList.c:10
coeffs coef
Definition: lattice.h:22

◆ enumerate_all()

bigintmat * lattice::enumerate_all ( number  a)

Definition at line 507 of file lattice.cc.

507  {
508  //Quadratic Supplement
509  DEBUG_BLOCK(true);
510  DEBUG_PRINT(("Start enumerate_all\n"));
511  DEBUG_PRINT(("check input\n"));
512  if(!n_GreaterZero(a,out_coef)){
513  if(n_IsZero(a,out_coef) && n==m){
514  return new bigintmat(m,1,out_coef);
515  } else {
516  DEBUG_PRINT(("negative input\n"));
517  return NULL;
518  }
519  }
520  if( Q == NULL){
521  if(quadratic_supplement()){
522  return NULL;
523  }
524  }
525  DEBUG_PRINT(("Q defined\n"));
526  //Q->Print();PrintS("\n");
527 
528  //usefull numbers
529  number zero = n_Init(0,coef);
530  number minusOne = n_Init(-1,coef);
531 
532  //backtracking for elements
533  //DEBUG_BLOCK(true);
534  DEBUG_PRINT(("Start backtracking\n"));
535  DEBUG_PRINT(("Initialize vector and other variables\n"));
536  std::vector<std::pair<number,bigintmat*> > elementsvector;
537  elementsvector.push_back( std::make_pair(zero, new bigintmat(m,1,out_coef)));
538  if( x != NULL){
539  delete x;
540  x=NULL;
541  }
542  x = new bigintmat(m,1,coef);
543  //x->Print();PrintS("\n");
544  DEBUG_PRINT(("map a\n"));
545  if(bound != NULL){
546  delete bound;
547  bound = NULL;
548  }
549  bound = new number[n+1];
551  bound[1] = f(a, out_coef, coef);//map a to coef
552  //n_Print(bound[1],coef);PrintS("\n");
553  DEBUG_PRINT(("set bound\n"));
554  for(int i = 2; i<n+1; i++){
555  bound[i] = n_Copy(bound[1],coef);
556  //n_Print(bound[i],coef);PrintS("\n");
557  }
558  DEBUG_PRINT(("find element\n"));
559  //bigintmat* elements = enumerate_next(a);
560  increase_x(1);
561  number check = enumerate_get_next();
562  while(!n_Equal(minusOne,check,coef)){
563  //append x to elements
564  DEBUG_PRINT(("new element to list\n"));
565  //elements->appendCol(bimChangeout_coeff(x,out_coef));
566  check = n_Sub(bound[1],check,coef);
567  check = n_Sub(bound[n],check,coef);
568  elementsvector.push_back(std::make_pair(n_Copy(check,coef),bimCopy(x)));
569  //n_Print(elementsvector[elementsvector.size()-1].first,coef);PrintS("\n");
570  for(unsigned i=1; i<elementsvector.size();i++){
571  if(n_Greater(elementsvector[i].first,check,coef)){
572  elementsvector.pop_back();
573  elementsvector.insert(elementsvector.begin()+i,std::make_pair(n_Copy(check,coef),bimCopy(x)));
574  DEBUG_VAR(elementsvector.size());
575  break;
576  }
577  }
578  if(elementsvector.size() >= 1000000){
579  elementsvector.pop_back();
580  }
581  increase_x(1);
582  DEBUG_PRINT(("increased x:\n"));x->Print();
583  n_Delete(&check,coef);
584  check = enumerate_get_next();
585  DEBUG_PRINT(("got it\n"));
586  }
587  DEBUG_PRINT(("generate bigintmat for return\n"));
588  bigintmat* elements = new bigintmat(m,1,out_coef);
589  if(b!=NULL){
590  for(unsigned i=1; i<elementsvector.size();i++){
591  elements->appendCol(bimChangeCoeff(elementsvector[i].second,out_coef));
592  }
593  } else {
594  for(unsigned i=1; i<elementsvector.size();i++){
595  elements->appendCol(bimChangeCoeff(elementsvector[i].second,out_coef));
596  }
597  }
598  delete bound;
599  bound = NULL;
600  delete x;
601  x = NULL;
602  return elements;
603 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:670
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff &#39;a&#39; is larger than &#39;b&#39;; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:512
bool quadratic_supplement()
Definition: lattice.cc:775
bigintmat * Q
Definition: lattice.h:58
int n
Definition: lattice.h:17
int check
Definition: libparse.cc:1104
number enumerate_get_next()
Definition: lattice.cc:718
bigintmat ** b
Definition: lattice.h:28
Matrices of numbers.
Definition: bigintmat.h:51
void appendCol(bigintmat *a)
horizontally join the matrices, m <- m|a
Definition: bigintmat.cc:1084
#define DEBUG_VAR(x)
Definition: lattice.cc:35
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
number * bound
Definition: lattice.h:64
coeffs out_coef
Definition: lattice.h:67
bigintmat * x
Definition: lattice.h:61
bigintmat * bimCopy(const bigintmat *b)
same as copy constructor - apart from it being able to accept NULL as input
Definition: bigintmat.cc:405
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:74
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:125
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:465
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition: coeffs.h:722
bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew)
Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
Definition: bigintmat.cc:1805
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:443
#define NULL
Definition: omList.c:10
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:452
int m
Definition: lattice.h:20
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff &#39;a&#39; and &#39;b&#39; represent the same number; they may have different representations.
Definition: coeffs.h:461
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
void increase_x(int index)
Definition: lattice.cc:841
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff &#39;n&#39; is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2), where m is the long representing n in C: TRUE iff (Im(n) != 0 and Im(n) >= 0) or (Im(n) == 0 and Re(n) >= 0) in K(a)/<p(a)>: TRUE iff (n != 0 and (LC(n) > 0 or deg(n) > 0)) in K(t_1, ..., t_n): TRUE iff (LC(numerator(n) is a constant and > 0) or (LC(numerator(n) is not a constant) in Z/2^kZ: TRUE iff 0 < n <= 2^(k-1) in Z/mZ: TRUE iff the internal mpz is greater than zero in Z: TRUE iff n > 0
Definition: coeffs.h:495
#define DEBUG_BLOCK(x)
Definition: lattice.cc:29

◆ enumerate_get_next()

number lattice::enumerate_get_next ( )
inlineprivate

Definition at line 718 of file lattice.cc.

718  {
719  DEBUG_BLOCK(true);
720  DEBUG_PRINT(("enumerate_get_next\t\t\t\t\taaaaaaaaaaaaa\n"));
721  number one = n_Init(1,coef);
722  number zero = n_Init(0,coef);
723  number minusOne = n_Init(-1,coef);
724  int index =1;
725  //x->Print();PrintS("\n");
726  //DEBUG_PRINT(("first time changing x\n"));
727  //increase_x(1);
728  DEBUG_PRINT(("actual backtracking\n"));
729  while (index <= m) {
730  DEBUG_PRINT(("update check\n"));
731  number check = check_bound(index);
732  DEBUG_PRINT(("check check\n"));
733  if (n_Greater(check,bound[index],coef)){
734  DEBUG_PRINT(("element to great\n"));
735  if(!(n_GreaterZero(x->view(index,1),coef) || n_IsZero(x->view(index,1),coef))){
736  bound[index] = zero;
737  x->set(index,1,zero,coef);
738  index++;
739  if(index<= m){
740  increase_x(index);
741  }
742  } else {
743  if(index == n){
744  return minusOne;
745  }
746  x->set(index,1,minusOne,coef);
747  }
748  } else if(index == 1){
749  DEBUG_PRINT(("possible new element\n"));
750  if(n_IsZero(x->view(n,1),coef)){
751  int j=n-1;
752  while(n_IsZero(x->view(j,1),coef)){
753  j--;
754  }DEBUG_VAR(j);
755  if(n_GreaterZero(x->view(j,1),coef)){
756  return check;
757  } else {
758  index = j+1;
759  x->zero();
760  x->set(index,1,one,coef);
761  }
762  } else {
763  DEBUG_PRINT(("return\n"));
764  return check;
765  }
766  } else {
767  DEBUG_PRINT(("reduce index\n"));
768  index--;
769  bound[index] = n_Sub(bound[index+1],check,coef);
770  }
771  }
772  return minusOne;
773 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:670
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff &#39;a&#39; is larger than &#39;b&#39;; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:512
int j
Definition: facHensel.cc:105
int n
Definition: lattice.h:17
int check
Definition: libparse.cc:1104
#define DEBUG_VAR(x)
Definition: lattice.cc:35
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
number * bound
Definition: lattice.h:64
void zero()
Setzt alle Einträge auf 0.
Definition: bigintmat.cc:1351
bigintmat * x
Definition: lattice.h:61
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition: bigintmat.cc:95
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:465
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int m
Definition: lattice.h:20
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
void increase_x(int index)
Definition: lattice.cc:841
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff &#39;n&#39; is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2), where m is the long representing n in C: TRUE iff (Im(n) != 0 and Im(n) >= 0) or (Im(n) == 0 and Re(n) >= 0) in K(a)/<p(a)>: TRUE iff (n != 0 and (LC(n) > 0 or deg(n) > 0)) in K(t_1, ..., t_n): TRUE iff (LC(numerator(n) is a constant and > 0) or (LC(numerator(n) is not a constant) in Z/2^kZ: TRUE iff 0 < n <= 2^(k-1) in Z/mZ: TRUE iff the internal mpz is greater than zero in Z: TRUE iff n > 0
Definition: coeffs.h:495
number check_bound(int index)
Definition: lattice.cc:855
#define DEBUG_BLOCK(x)
Definition: lattice.cc:29

◆ enumerate_next() [1/4]

bigintmat * lattice::enumerate_next ( number  a,
bigintmat x 
)

Definition at line 605 of file lattice.cc.

605  {//next element x with norm(x)<a and x=in possible
606  DEBUG_BLOCK(true);
607  DEBUG_PRINT(("Start enumerate_next number and bigintmat\n"));
608  if (in == NULL || in->rows()!=n || in->cols()!=1){
609  DEBUG_PRINT(("Dimension error of input\n"));
610  return NULL;
611  }
612 
613  if(!n_GreaterZero(a,out_coef) || n_IsZero(a,out_coef) ){
614  DEBUG_PRINT(("negative input\n"));
615  return NULL;
616  }
617 
618  DEBUG_PRINT(("check quadratic\n"));
619 
620  if( Q == NULL){
621  if(!quadratic_supplement()){
622  return NULL;
623  }
624  }
625  DEBUG_PRINT(("Q defined\n"));
626  //Q->Print();PrintS("\n");
627 
628  //usefull numbers
629  number check;
630 
631  //backtracking for elements
632  //DEBUG_BLOCK(true);
633  DEBUG_PRINT(("Start backtracking\n"));
634  DEBUG_PRINT(("Initialize variables\n"));
635  if( x != NULL){
636  delete x;
637  x=NULL;
638  }
639  x = bimChangeCoeff(in,coef);
640  if( bound != NULL){
641  delete bound;
642  bound=NULL;
643  }
644  bound = new number[n+1];
645  DEBUG_PRINT(("set bound\n"));
647  bound[n] = f(a, out_coef, coef);//map a to coef
648  for(int j = n; j>1; j--){
649  check = check_bound(j);
650  bound[j-1] = n_Sub(bound[j],check,coef);
651  //n_Delete(&check, coef);
652  }
653  number minusOne = n_Init(-1,coef);
654  DEBUG_PRINT(("find element\n"));
655  number norm = enumerate_get_next();
656  DEBUG_PRINT(("generate bigintmat for return\n"));
657  if(n_Equal(minusOne,norm,coef)){
658  return NULL;
659  }
660  bigintmat * out = bimChangeCoeff(x,out_coef);
661  return out;
662 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:670
bool quadratic_supplement()
Definition: lattice.cc:775
int j
Definition: facHensel.cc:105
bigintmat * Q
Definition: lattice.h:58
int n
Definition: lattice.h:17
int check
Definition: libparse.cc:1104
number enumerate_get_next()
Definition: lattice.cc:718
Matrices of numbers.
Definition: bigintmat.h:51
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
number * bound
Definition: lattice.h:64
coeffs out_coef
Definition: lattice.h:67
bigintmat * x
Definition: lattice.h:61
CanonicalForm norm
Definition: facAlgExt.cc:63
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:74
FILE * f
Definition: checklibs.c:9
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:465
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition: coeffs.h:722
bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew)
Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
Definition: bigintmat.cc:1805
#define NULL
Definition: omList.c:10
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff &#39;a&#39; and &#39;b&#39; represent the same number; they may have different representations.
Definition: coeffs.h:461
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff &#39;n&#39; is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2), where m is the long representing n in C: TRUE iff (Im(n) != 0 and Im(n) >= 0) or (Im(n) == 0 and Re(n) >= 0) in K(a)/<p(a)>: TRUE iff (n != 0 and (LC(n) > 0 or deg(n) > 0)) in K(t_1, ..., t_n): TRUE iff (LC(numerator(n) is a constant and > 0) or (LC(numerator(n) is not a constant) in Z/2^kZ: TRUE iff 0 < n <= 2^(k-1) in Z/mZ: TRUE iff the internal mpz is greater than zero in Z: TRUE iff n > 0
Definition: coeffs.h:495
number check_bound(int index)
Definition: lattice.cc:855
#define DEBUG_BLOCK(x)
Definition: lattice.cc:29

◆ enumerate_next() [2/4]

bigintmat * lattice::enumerate_next ( number  a)

Definition at line 664 of file lattice.cc.

664  {
665  DEBUG_BLOCK(true);
666  DEBUG_PRINT(("Start enumerate_next number\n"));
667  bigintmat * in =new bigintmat(m,1,out_coef);
668  if(x == NULL){
669  in->set(1,1,n_Init(1,out_coef),out_coef);
670  } else {
671  in = bimChangeCoeff(x,out_coef);
672  }
673  return enumerate_next(a,in);
674 }
bigintmat * enumerate_next()
Definition: lattice.cc:691
Matrices of numbers.
Definition: bigintmat.h:51
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
coeffs out_coef
Definition: lattice.h:67
bigintmat * x
Definition: lattice.h:61
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition: bigintmat.cc:95
bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew)
Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
Definition: bigintmat.cc:1805
#define NULL
Definition: omList.c:10
int m
Definition: lattice.h:20
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
#define DEBUG_BLOCK(x)
Definition: lattice.cc:29

◆ enumerate_next() [3/4]

bigintmat * lattice::enumerate_next ( bigintmat x)

Definition at line 676 of file lattice.cc.

676  {
677  DEBUG_BLOCK(true);
678  DEBUG_PRINT(("Start enumerate_next bigintmat\n"));
679  if(bound == NULL){
680  Werror("no bound for elements given\n");
681  return NULL;
682  }
683  if (in == NULL || in->rows()!=n || in->cols()!=1){
684  DEBUG_PRINT(("Dimension error of input\n"));
685  return NULL;
686  }
687  number a = bound[n];
688  return enumerate_next(a,in);
689 }
int n
Definition: lattice.h:17
bigintmat * enumerate_next()
Definition: lattice.cc:691
number * bound
Definition: lattice.h:64
#define NULL
Definition: omList.c:10
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
void Werror(const char *fmt,...)
Definition: reporter.cc:189
#define DEBUG_BLOCK(x)
Definition: lattice.cc:29

◆ enumerate_next() [4/4]

bigintmat * lattice::enumerate_next ( )

Definition at line 691 of file lattice.cc.

691  {
692  DEBUG_BLOCK(true);
693  DEBUG_PRINT(("enumerate_next\n"));
694  if(Q == NULL){
695  Werror("not initialized\n");
696  return NULL;
697  }
698  if(bound == NULL || x == NULL){
699  return NULL;
700  }
701  increase_x(1);
702  number minusOne = n_Init(-1,coef);
703  number one = n_Init(1,coef);
704  DEBUG_PRINT(("find element\n"));
705  number norm = enumerate_get_next();
706  DEBUG_PRINT(("generate bigintmat for return\n"));
707  if(n_Equal(minusOne,norm,coef)){
708  if(!n_Equal(minusOne, x->view(1,1),coef)){
709  x->rawset(1,1, n_Add(one,x->view(1,1),coef),coef);
710  }
711  return NULL;
712  }
714  return out;
715 }
bigintmat * Q
Definition: lattice.h:58
number enumerate_get_next()
Definition: lattice.cc:718
Matrices of numbers.
Definition: bigintmat.h:51
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
number * bound
Definition: lattice.h:64
coeffs out_coef
Definition: lattice.h:67
bigintmat * x
Definition: lattice.h:61
CanonicalForm norm
Definition: facAlgExt.cc:63
void rawset(int i, number n, const coeffs C=NULL)
replace an entry with the given number n (only delete old). NOTE: starts at [0]. Should be named set_...
Definition: bigintmat.h:197
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:657
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew)
Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
Definition: bigintmat.cc:1805
#define NULL
Definition: omList.c:10
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff &#39;a&#39; and &#39;b&#39; represent the same number; they may have different representations.
Definition: coeffs.h:461
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
void increase_x(int index)
Definition: lattice.cc:841
void Werror(const char *fmt,...)
Definition: reporter.cc:189
#define DEBUG_BLOCK(x)
Definition: lattice.cc:29

◆ get_basis()

bigintmat * lattice::get_basis ( )

Definition at line 874 of file lattice.cc.

874  {
875  bigintmat * r = new bigintmat(m,n,coef);
876  for(int j=1; j<=n; j++) {
877  r->setcol(j,basis[j]);
878  }
879  return r;
880 }
int j
Definition: facHensel.cc:105
int n
Definition: lattice.h:17
Matrices of numbers.
Definition: bigintmat.h:51
void setcol(int j, bigintmat *m)
Setzt j-te Spalte gleich übergebenem Vektor (Matrix) m.
Definition: bigintmat.cc:827
bigintmat ** basis
Definition: lattice.h:11
int m
Definition: lattice.h:20
coeffs coef
Definition: lattice.h:22

◆ get_reduced_basis()

bigintmat * lattice::get_reduced_basis ( )

Definition at line 882 of file lattice.cc.

882  {
883  bigintmat * r = new bigintmat(m,n,coef);
884  for(int j=1; j<=n; j++) {
885  r->setcol(j,b[j]);
886  }
887  return r;
888 }
int j
Definition: facHensel.cc:105
int n
Definition: lattice.h:17
bigintmat ** b
Definition: lattice.h:28
Matrices of numbers.
Definition: bigintmat.h:51
void setcol(int j, bigintmat *m)
Setzt j-te Spalte gleich übergebenem Vektor (Matrix) m.
Definition: bigintmat.cc:827
int m
Definition: lattice.h:20
coeffs coef
Definition: lattice.h:22

◆ get_transformation_matrix()

bigintmat * lattice::get_transformation_matrix ( )

Definition at line 890 of file lattice.cc.

890  {
891  return bimCopy(H);
892 }
bigintmat * bimCopy(const bigintmat *b)
same as copy constructor - apart from it being able to accept NULL as input
Definition: bigintmat.cc:405
bigintmat * H
Definition: lattice.h:37

◆ gram_schmidt()

bool lattice::gram_schmidt ( int  k)
inlineprivate

Definition at line 430 of file lattice.cc.

430  {
431  DEBUG_PRINT(("Start gram_schmidt(%d)\n",k));
432 
433  delete b_star[k];
434  b_star[k] = bimCopy(b[k]);
435 
436  for(int j=1; j<k; j++) {
437  my->set(k,j,n_Div(scalarproduct(b[k],b_star[j]),B[j],coef),coef);
438 
439  b_star[k]->sub(bimMult(b_star[j],my->view(k,j),coef));
440  }
441 
442  B[k] = scalarproduct(b_star[k],b_star[k]);
443 
444  if(n_IsZero(B[k],coef)){
445  Werror("did not form a basis\n");
446  DEBUG_PRINT(("End of gram_schmidt(%d)\n",k));
447  return true;
448  } else {
449  DEBUG_PRINT(("End of gram_schmidt(%d)\n",k));
450  return false;
451  }
452 }
int j
Definition: facHensel.cc:105
bigintmat ** b
Definition: lattice.h:28
bigintmat * my
Definition: lattice.h:40
bool sub(bigintmat *b)
Subtrahiert ...
Definition: bigintmat.cc:917
bigintmat ** b_star
Definition: lattice.h:31
int k
Definition: cfEzgcd.cc:92
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition: bigintmat.cc:95
bigintmat * bimCopy(const bigintmat *b)
same as copy constructor - apart from it being able to accept NULL as input
Definition: bigintmat.cc:405
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:255
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:465
number scalarproduct(bigintmat *a, bigintmat *b)
Definition: lattice.cc:915
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:616
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
void Werror(const char *fmt,...)
Definition: reporter.cc:189
number * B
Definition: lattice.h:34

◆ gram_schmidt_MLLL()

void lattice::gram_schmidt_MLLL ( int  k)
inlineprivate

Definition at line 454 of file lattice.cc.

454  {
455  DEBUG_PRINT(("Start gram_schmidt_MLLL(%d)\n",k));
456 
457  for(int j=1; j<k; j++) {
458  if(n_IsZero(B[j],coef)) {
459  my->set(k,j,n_Init(0,coef));
460  } else {
461  my->set(k,j,n_Div(scalarproduct(b[k],b_star[j]),B[j],coef),coef);
462  }
463  }
464 
465  delete b_star[k];
466  b_star[k] = bimCopy(b[k]);
467  for(int j=1; j<k; j++) {
468  b_star[k]->sub(bimMult(b_star[j],my->view(k,j),coef));
469  }
470 
471  B[k] = scalarproduct(b_star[k],b_star[k]);
472 
473  DEBUG_PRINT(("End of gram_schmidt_MLLL(%d)\n",k));
474 }
int j
Definition: facHensel.cc:105
bigintmat ** b
Definition: lattice.h:28
bigintmat * my
Definition: lattice.h:40
bool sub(bigintmat *b)
Subtrahiert ...
Definition: bigintmat.cc:917
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
bigintmat ** b_star
Definition: lattice.h:31
int k
Definition: cfEzgcd.cc:92
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition: bigintmat.cc:95
bigintmat * bimCopy(const bigintmat *b)
same as copy constructor - apart from it being able to accept NULL as input
Definition: bigintmat.cc:405
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:255
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:465
number scalarproduct(bigintmat *a, bigintmat *b)
Definition: lattice.cc:915
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:616
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
number * B
Definition: lattice.h:34

◆ increase_x()

void lattice::increase_x ( int  index)
inlineprivate

Definition at line 841 of file lattice.cc.

841  {
842  number one = n_Init(1,coef);x->Print();
843  number newNumber;
844  if (n_GreaterZero(x->view(index,1),coef) || n_IsZero(x->view(index,1),coef)){
845  newNumber = n_Add(one,x->view(index,1),coef); //x_i=x_i+1
846  } else {
847  newNumber = n_Sub(x->view(index,1),one,coef);//x_i=x_i-1
848  }
849  x->set(index,1,newNumber,coef);
850  x->Print();
851  n_Delete(&one,coef);
852  n_Delete(&newNumber,coef);
853 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:670
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
bigintmat * x
Definition: lattice.h:61
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition: bigintmat.cc:95
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:657
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:465
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:443
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
coeffs coef
Definition: lattice.h:22
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff &#39;n&#39; is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2), where m is the long representing n in C: TRUE iff (Im(n) != 0 and Im(n) >= 0) or (Im(n) == 0 and Re(n) >= 0) in K(a)/<p(a)>: TRUE iff (n != 0 and (LC(n) > 0 or deg(n) > 0)) in K(t_1, ..., t_n): TRUE iff (LC(numerator(n) is a constant and > 0) or (LC(numerator(n) is not a constant) in Z/2^kZ: TRUE iff 0 < n <= 2^(k-1) in Z/mZ: TRUE iff the internal mpz is greater than zero in Z: TRUE iff n > 0
Definition: coeffs.h:495

◆ LLL() [1/2]

bool lattice::LLL ( )

Definition at line 133 of file lattice.cc.

133  {
134  // c = 3/4
135  number three = n_Init(3, coef);
136  number four = n_Init(4, coef);
137  number default_c = n_Div(three,four,coef);
138  n_Delete(&three,coef);
139  n_Delete(&four,coef);
140  return lattice::LLL(default_c);
141 }
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
bool LLL()
Definition: lattice.cc:133
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:616
coeffs coef
Definition: lattice.h:22
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456

◆ LLL() [2/2]

bool lattice::LLL ( number &  c)

Definition at line 143 of file lattice.cc.

143  {
144  DEBUG_PRINT(("Start LLL\n"));
145 
146  if(b == NULL) {
147  b = new bigintmat*[n+1]; //b[0] is not used
148  b[0] = NULL;
149  for(int j=1; j<=n; j++) {
150  b[j] = bimCopy(basis[j]);
151  }
152  } else {
153  b[0] = NULL;
154  for(int j=1; j<=n; j++) {
155  delete b[j];
156  b[j] = bimCopy(basis[j]);
157  }
158  }
159 
160  if(b_star == NULL) {
161  b_star = new bigintmat*[n+1]; //b_star[0] is not used
162  for(int j=0; j<=n; j++) {
163  b_star[j] = NULL;
164  }
165  } else {
166  for(int j=0; j<=n; j++) {
167  delete b_star[j];
168  b_star[j] = NULL;
169  }
170  }
171 
172  if(B == NULL) {
173  B = new number[n+1]; //B[0] is not used
174  }
175  for(int j=0; j<=n; j++) {
176  B[j] = n_Init(0,coef);
177  }
178 
179  delete H;
180  if(trans_matrix) {
181  H = new bigintmat(n,n,coef);
182  } else {
183  H = NULL;
184  }
185 
186  delete my;
187  my = new bigintmat(m,n,coef);
188 
189  delete[] d;
190  if(integral) {
191  d = new number[n+1];
192  } else {
193  d = NULL;
194  }
195 
196  this->c = c;
197 
198  if (n == 0) {
199  return true;
200  }
201  if (n == 1) {
202  return false;
203  }
204 
205  DEBUG_BIM(b[1]);
206  DEBUG_BIM(b[2]);
207  DEBUG_BIM(b[3]);
208 
209  DEBUG_PRINT(("Initialize\n"));
210  int k = 2;
211  int k_max = 1;
212 
213 
214  b_star[1] = bimCopy(b[1]);
215 
216  B[1] = scalarproduct(b[1],b[1]);
217 
218  if(trans_matrix) {
219  H->one();
220  }
221 
222  do{
223  DEBUG_PRINT(("Incremental Gram-Schmidt\n"));
224  DEBUG_VAR(k);
225  DEBUG_VAR(k_max);
226  if(k > k_max){
227  k_max = k;
228  if(independentVectors) {
229  if(gram_schmidt(k)){
230  return true;
231  }
232  } else {
234  }
235  }
236  DEBUG_PRINT(("Test LLL condition\n"));
237  while(true){
238  RED(k,k-1);
239 
240  // if((B[k] < (c- my*my)*B[k-1]))
241  if(n_Greater(n_Mult(n_Sub(c, n_Mult(my->view(k,k-1), my->view(k,k-1), coef), coef), B[k-1], coef), B[k], coef)){
242  if(independentVectors) {
243  SWAP(k,k_max);
244  } else {
245  SWAPG(k,k_max);
246  }
247  if(k>2){
248  k--;
249  }
250  } else {
251  for(int l=k-2; l>0; l--){
252  RED(k,l);
253  }
254  k++;
255  break;
256  }
257  }
258  } while(k <= n);
259 
260  rank = n;
261  for(int i=1; b[i]->isZero() && i<=n; i++) {
262  rank--;
263  }
264 
265 
266 
267 
268  DEBUG_BIM(b[1]);
269  DEBUG_BIM(b[2]);
270  DEBUG_BIM(b[3]);
271 
272  DEBUG_PRINT(("End of LLL\n"));
273  return false;
274 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:670
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff &#39;a&#39; is larger than &#39;b&#39;; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:512
int j
Definition: facHensel.cc:105
int rank
Definition: lattice.h:46
bool trans_matrix
Definition: lattice.h:49
int n
Definition: lattice.h:17
void SWAPG(int k, int k_max)
Definition: lattice.cc:357
number * d
Definition: lattice.h:43
bigintmat ** b
Definition: lattice.h:28
Matrices of numbers.
Definition: bigintmat.h:51
bigintmat * my
Definition: lattice.h:40
#define DEBUG_VAR(x)
Definition: lattice.cc:35
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
void gram_schmidt_MLLL(int k)
Definition: lattice.cc:454
bool gram_schmidt(int k)
Definition: lattice.cc:430
bigintmat ** b_star
Definition: lattice.h:31
void RED(int k, int l)
Definition: lattice.cc:276
int k
Definition: cfEzgcd.cc:92
bool independentVectors
Definition: lattice.h:52
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:637
bigintmat * bimCopy(const bigintmat *b)
same as copy constructor - apart from it being able to accept NULL as input
Definition: bigintmat.cc:405
bigintmat ** basis
Definition: lattice.h:11
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
#define DEBUG_BIM(x)
Definition: lattice.cc:37
int i
Definition: cfEzgcd.cc:125
number scalarproduct(bigintmat *a, bigintmat *b)
Definition: lattice.cc:915
void SWAP(int k, int k_max)
Definition: lattice.cc:315
bigintmat * H
Definition: lattice.h:37
#define NULL
Definition: omList.c:10
number c
Definition: lattice.h:25
int m
Definition: lattice.h:20
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
int isZero()
Definition: bigintmat.cc:1364
bool integral
Definition: lattice.h:55
void one()
Macht Matrix (Falls quadratisch) zu Einheitsmatrix.
Definition: bigintmat.cc:1326
number * B
Definition: lattice.h:34
int l
Definition: cfEzgcd.cc:93

◆ quadratic_supplement()

bool lattice::quadratic_supplement ( )
inlineprivate

Definition at line 775 of file lattice.cc.

775  {
776  //DEBUG_BLOCK(true);
777  delete Q;
778  Q = NULL;
779  if(n != m) { //NOTE: rank?
780  return true;
781  }
783  Q = gram_matrix;
784 
785  number zero = n_Init(0,coef);
786  number mult;
787 
788  DEBUG_PRINT(("Begin Quadratic Suplement\n"));
789  for(int i = 1; i<Q->cols();i++){
790  if(n_IsZero( Q->view(i,i), coef)){
791  DEBUG_PRINT(("matrix not positive definite\n"));
792  delete Q;
793  Q = NULL;
794  return true;
795  }
796  for( int j=i+1; j<=Q->cols();j++){
797  Q->rawset(j,i,Q->get(i,j),coef);
798  Q->rawset(i,j,n_Div(Q->get(i,j),Q->view(i,i),coef),coef);
799  }
800  for(int m=i+1; m<=Q->rows();m++){
801  for(int n=i+1; n<=Q->cols();n++){
802  mult = n_Mult(Q->view(m,i),Q->view(i,n),coef);
803  Q->rawset(m,n,n_Sub(Q->get(m,n),mult,coef),coef);
804  n_Delete(&mult,coef);
805  }
806  }
807  }
808 
809  DEBUG_PRINT(("Set Zeros\n"));
810  for(int i = 2; i<=Q->cols();i++){
811  for(int j = 1; j<i;j++){
812  Q->set(i,j,zero,coef);
813  }
814  }
815  n_Delete(&zero,coef);
816  DEBUG_PRINT(("Test: matrix positive definite\n"));
817  for(int i=1; i<=Q->cols();i++){
818  if(!n_GreaterZero( Q->view(i,i), coef)){
819  DEBUG_PRINT(("matrix not positive definite\n"));
820  delete Q;
821  Q = NULL;
822  return true;
823  }
824  }
825  return false;
826 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:670
int j
Definition: facHensel.cc:105
bigintmat * Q
Definition: lattice.h:58
bigintmat * gram_matrix
Definition: lattice.h:14
int n
Definition: lattice.h:17
int rows() const
Definition: bigintmat.h:146
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition: bigintmat.cc:95
void rawset(int i, number n, const coeffs C=NULL)
replace an entry with the given number n (only delete old). NOTE: starts at [0]. Should be named set_...
Definition: bigintmat.h:197
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:637
void compute_gram_matrix()
Definition: lattice.cc:828
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:125
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:465
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:647
#define NULL
Definition: omList.c:10
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:616
int m
Definition: lattice.h:20
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:456
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff &#39;n&#39; is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2), where m is the long representing n in C: TRUE iff (Im(n) != 0 and Im(n) >= 0) or (Im(n) == 0 and Re(n) >= 0) in K(a)/<p(a)>: TRUE iff (n != 0 and (LC(n) > 0 or deg(n) > 0)) in K(t_1, ..., t_n): TRUE iff (LC(numerator(n) is a constant and > 0) or (LC(numerator(n) is not a constant) in Z/2^kZ: TRUE iff 0 < n <= 2^(k-1) in Z/mZ: TRUE iff the internal mpz is greater than zero in Z: TRUE iff n > 0
Definition: coeffs.h:495
number get(int i, int j) const
get a copy of an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:119

◆ RED()

void lattice::RED ( int  k,
int  l 
)
inlineprivate

Definition at line 276 of file lattice.cc.

276  {
277  DEBUG_PRINT(("Start RED with k=%d and l=%d\n",k,l));
278  DEBUG_BIM(b[1]);
279  DEBUG_BIM(b[2]);
280  DEBUG_BIM(b[3]);
281  number n_1div2 = n_Div(n_Init( 1,coef),n_Init(2,coef),coef);
282  number n_neg1div2 = n_Div(n_Init(-1,coef),n_Init(2,coef),coef);
283  number my_kl = my->get(k,l);
284  DEBUG_N(my_kl);
285 
286  // if(|my_kl| > 1/2)
287  if (n_Greater (my_kl,n_1div2,coef) || n_Greater (n_neg1div2,my_kl,coef)) {
288 
289  number my_klplus1div2;
290  if(n_Greater (my_kl,n_Init(0,coef),coef)) {
291  my_klplus1div2 = n_Add(my_kl, n_1div2, coef);
292  } else {
293  my_klplus1div2 = n_Add(my_kl, n_neg1div2, coef);
294  }
295 
296  number q = n_Div(n_GetNumerator(my_klplus1div2,coef),n_GetDenom(my_klplus1div2,coef),coef);
297 
298  DEBUG_N(q);
299 
300  b[k]->sub(bimMult(b[l],q,coef));
301 
302  if(trans_matrix) {
303  H->addcol(k,l,n_Mult(q,n_Init(-1,coef),coef),coef);
304  }
305 
306  my->set(k,l,n_Sub(my->view(k,l),q,coef),coef);
307 
308  for(int i=1;i<=l-1;i++){
309  my->set(k,i,n_Sub(my->view(k,i), n_Mult(q, my->view(l,i),coef), coef), coef);
310  }
311  }
312  DEBUG_PRINT(("End of RED\n"));
313 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:670
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff &#39;a&#39; is larger than &#39;b&#39;; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition: coeffs.h:512
static FORCE_INLINE number n_GetNumerator(number &n, const coeffs r)
return the numerator of n (if elements of r are by nature not fractional, result is n) ...
Definition: coeffs.h:609
bool trans_matrix
Definition: lattice.h:49
bool addcol(int i, int j, number a, coeffs c)
addiert a-faches der j-ten Spalte zur i-ten dazu
Definition: bigintmat.cc:960
bigintmat ** b
Definition: lattice.h:28
bigintmat * my
Definition: lattice.h:40
bool sub(bigintmat *b)
Subtrahiert ...
Definition: bigintmat.cc:917
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
int k
Definition: cfEzgcd.cc:92
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition: bigintmat.cc:95
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:637
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:255
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:657
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
#define DEBUG_BIM(x)
Definition: lattice.cc:37
int i
Definition: cfEzgcd.cc:125
#define DEBUG_N(x)
Definition: lattice.cc:36
bigintmat * H
Definition: lattice.h:37
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:616
static FORCE_INLINE number n_GetDenom(number &n, const coeffs r)
return the denominator of n (if elements of r are by nature not fractional, result is 1) ...
Definition: coeffs.h:604
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
number get(int i, int j) const
get a copy of an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:119
int l
Definition: cfEzgcd.cc:93

◆ SWAP()

void lattice::SWAP ( int  k,
int  k_max 
)
inlineprivate

Definition at line 315 of file lattice.cc.

315  {
316  DEBUG_PRINT(("Start SWAP with k=%d and k_max=%d\n",k,k_max));
317 
318  bigintmat * temp = b[k];
319  b[k] = b[k-1];
320  b[k-1] = temp;
321 
322  if(trans_matrix) {
323  H->swap(k,k-1);
324  }
325 
326  for(int j = 1; j <= k-2; j++){
327  number my_kj = my->get(k,j);
328  my->set(k,j,my->view(k-1,j),coef);
329  my->set(k-1,j,my_kj,coef);
330  }
331 
332  number my_ = my->get(k,k-1);
333 
334  number B_ = n_Add(B[k], n_Mult(n_Mult(my_,my_,coef), B[k-1], coef), coef);
335 
336  my->set(k,k-1,n_Div(n_Mult(my_, B[k-1], coef), B_, coef), coef);
337 
338  bigintmat * b_ = bimCopy(b_star[k-1]);
339 
340  b_star[k-1] = bimAdd(b_star[k], bimMult(b_, my_, coef));
341 
342  b_star[k] = bimSub(bimMult(b_, n_Div(B[k], B_, coef),coef), bimMult( b_star[k], my->view(k,k-1), coef));
343 
344  delete b_;
345 
346  B[k] = n_Div(n_Mult(B[k], B[k-1], coef), B_, coef);
347 
348  B[k-1] = n_Copy(B_, coef);
349  for(int i = k+1; i <= k_max; i++){
350  number t = my->get(i,k);
351  my->set(i,k,n_Sub(my->get(i,k-1), n_Mult(my_, t, coef), coef), coef);
352  my->set(i,k-1, n_Add(t, n_Mult(my->view(k,k-1), my->view(i,k), coef), coef), coef);
353  }
354  DEBUG_PRINT(("End of SWAP\n"));
355 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:670
int j
Definition: facHensel.cc:105
bool trans_matrix
Definition: lattice.h:49
bigintmat * bimSub(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:218
bigintmat ** b
Definition: lattice.h:28
Matrices of numbers.
Definition: bigintmat.h:51
bigintmat * my
Definition: lattice.h:40
bigintmat * bimAdd(bigintmat *a, bigintmat *b)
Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ? : NULL as a result means an error (non-compatible m...
Definition: bigintmat.cc:182
bigintmat ** b_star
Definition: lattice.h:31
int k
Definition: cfEzgcd.cc:92
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition: bigintmat.cc:95
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:637
bigintmat * bimCopy(const bigintmat *b)
same as copy constructor - apart from it being able to accept NULL as input
Definition: bigintmat.cc:405
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:255
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:657
void swap(int i, int j)
swap columns i and j
Definition: bigintmat.cc:686
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
int i
Definition: cfEzgcd.cc:125
bigintmat * H
Definition: lattice.h:37
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:452
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:616
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
number get(int i, int j) const
get a copy of an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:119
number * B
Definition: lattice.h:34

◆ SWAPG()

void lattice::SWAPG ( int  k,
int  k_max 
)
inlineprivate

Definition at line 357 of file lattice.cc.

357  {
358  DEBUG_PRINT(("Start SWAPG with k=%d and k_max=%d\n",k,k_max));
359 
360  bigintmat * temp = b[k];
361  b[k] = b[k-1];
362  b[k-1] = temp;
363 
364  if(trans_matrix) {
365  H->swap(k,k-1);
366  }
367 
368  for(int j = 1; j <= k-2; j++){
369  number my_kj = my->get(k,j);
370  my->set(k,j,my->get(k-1,j),coef);
371  my->set(k-1,j,my_kj,coef);
372  }
373 
374  number my_ = my->get(k,k-1);
375 
376  number B_ = n_Add(B[k], n_Mult(n_Mult(my_,my_,coef), B[k-1], coef), coef);
377 
378  if(n_IsZero(B[k],coef)) {
379  if(n_IsZero(my_,coef)) {
380  number tempnumber = B[k];
381  B[k] = B[k-1];
382  B[k-1] = tempnumber;
383 
384  bigintmat * temp = b_star[k];
385  b_star[k] = b_star[k-1];
386  b_star[k-1] = temp;
387 
388  for(int i = k+1; i <= k_max; i++){
389  number tempnumber = my->get(i,k);
390  my->set(i,k,my->get(i,k-1), coef);
391  my->set(i,k-1,tempnumber, coef);
392  }
393  } else {
394  B[k-1] = n_Copy(B_, coef); //delete B[k-1] ?
395 
396  b_star[k-1]->skalmult(my_, coef);
397 
398  my->set(k,k-1, n_Div(n_Init(1,coef),my_, coef), coef);
399 
400  for(int i = k+1; i <= k_max; i++){
401  my->set(i,k-1,n_Div(my->view(i,k-1), my_, coef), coef);
402  }
403  }
404  } else {
405  number t = n_Div(B[k-1], B_, coef);
406 
407  my->set(k,k-1,n_Mult(my_,t,coef),coef);
408 
409  bigintmat * b_ = b_star[k-1];
410 
411  b_star[k-1] = bimAdd(b_star[k], bimMult(b_, my_, coef));
412 
413  b_star[k] = bimSub(bimMult(b_, n_Div(B[k], B_, coef),coef), bimMult( b_star[k], my->view(k,k-1), coef));
414 
415  delete b_;
416 
417  B[k] = n_Mult(B[k],t,coef); // n_InpMult
418 
419  B[k-1] = n_Copy(B_, coef);
420 
421  for(int i = k+1; i <= k_max; i++){
422  t = my->get(i,k);
423  my->set(i,k,n_Sub(my->view(i,k-1),n_Mult(my_,t,coef), coef), coef);
424  my->set(i,k-1,n_Add(t,n_Mult(my->view(k,k-1),my->view(i,k),coef),coef),coef);
425  }
426  }
427  DEBUG_PRINT(("End of SWAPG\n"));
428 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:670
int j
Definition: facHensel.cc:105
bool trans_matrix
Definition: lattice.h:49
bigintmat * bimSub(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:218
bigintmat ** b
Definition: lattice.h:28
Matrices of numbers.
Definition: bigintmat.h:51
bigintmat * my
Definition: lattice.h:40
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
bigintmat * bimAdd(bigintmat *a, bigintmat *b)
Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ? : NULL as a result means an error (non-compatible m...
Definition: bigintmat.cc:182
bigintmat ** b_star
Definition: lattice.h:31
int k
Definition: cfEzgcd.cc:92
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition: bigintmat.cc:95
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:637
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:255
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:657
bool skalmult(number b, coeffs c)
Multipliziert zur Matrix den Skalar b hinzu.
Definition: bigintmat.cc:939
void swap(int i, int j)
swap columns i and j
Definition: bigintmat.cc:686
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:127
int i
Definition: cfEzgcd.cc:125
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:465
bigintmat * H
Definition: lattice.h:37
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:452
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:616
coeffs coef
Definition: lattice.h:22
#define DEBUG_PRINT(x)
Definition: lattice.cc:33
number get(int i, int j) const
get a copy of an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:119
number * B
Definition: lattice.h:34

Field Documentation

◆ b

bigintmat** lattice::b
private

Definition at line 28 of file lattice.h.

◆ B

number* lattice::B
private

Definition at line 34 of file lattice.h.

◆ b_star

bigintmat** lattice::b_star
private

Definition at line 31 of file lattice.h.

◆ basis

bigintmat** lattice::basis
private

Definition at line 11 of file lattice.h.

◆ bound

number* lattice::bound
private

Definition at line 64 of file lattice.h.

◆ c

number lattice::c
private

Definition at line 25 of file lattice.h.

◆ coef

coeffs lattice::coef
private

Definition at line 22 of file lattice.h.

◆ d

number* lattice::d
private

Definition at line 43 of file lattice.h.

◆ gram_matrix

bigintmat* lattice::gram_matrix
private

Definition at line 14 of file lattice.h.

◆ H

bigintmat* lattice::H
private

Definition at line 37 of file lattice.h.

◆ independentVectors

bool lattice::independentVectors
private

Definition at line 52 of file lattice.h.

◆ integral

bool lattice::integral
private

Definition at line 55 of file lattice.h.

◆ m

int lattice::m
private

Definition at line 20 of file lattice.h.

◆ my

bigintmat* lattice::my
private

Definition at line 40 of file lattice.h.

◆ n

int lattice::n
private

Definition at line 17 of file lattice.h.

◆ out_coef

coeffs lattice::out_coef
private

Definition at line 67 of file lattice.h.

◆ Q

bigintmat* lattice::Q
private

Definition at line 58 of file lattice.h.

◆ rank

int lattice::rank
private

Definition at line 46 of file lattice.h.

◆ trans_matrix

bool lattice::trans_matrix
private

Definition at line 49 of file lattice.h.

◆ x

bigintmat* lattice::x
private

Definition at line 61 of file lattice.h.


The documentation for this class was generated from the following files: