1 // -*- C++ -*- 2 //============================================================================================== 3 // 4 // This file is part of LiDIA --- a library for computational number theory 5 // 6 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved. 7 // 8 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/ 9 // 10 //---------------------------------------------------------------------------------------------- 11 // 12 // $Id$ 13 // 14 // Author : Michael Jacobson (MJJ), Markus Maurer (MM) 15 // Changes : See CVS log 16 // 17 //============================================================================================== 18 19 20 #ifndef LIDIA_QUADRATIC_IDEAL_H_GUARD_ 21 #define LIDIA_QUADRATIC_IDEAL_H_GUARD_ 22 23 24 #ifndef LIDIA_BIGINT_H_GUARD_ 25 #include "LiDIA/bigint.h" 26 #endif 27 #ifndef LIDIA_BIGRATIONAL_H_GUARD_ 28 #include "LiDIA/bigrational.h" 29 #endif 30 #ifndef LIDIA_BIGFLOAT_H_GUARD_ 31 #include "LiDIA/bigfloat.h" 32 #endif 33 #ifndef LIDIA_XBIGFLOAT_H_GUARD_ 34 #include "LiDIA/xbigfloat.h" 35 #endif 36 #ifndef LIDIA_BASE_VECTOR_H_GUARD_ 37 #include "LiDIA/base_vector.h" 38 #endif 39 40 41 42 #ifdef LIDIA_NAMESPACE 43 namespace LiDIA { 44 # define IN_NAMESPACE_LIDIA 45 #endif 46 47 48 49 class qo_node; 50 class quadratic_order; 51 class quadratic_form; 52 class qi_class; 53 class qi_class_real; 54 55 class quadratic_number_standard; 56 class quadratic_number_power_product; 57 58 59 60 // 61 // Class: quadratic_ideal 62 // 63 // This class represents a normalized fractional ideal of a quadratic order, 64 // i.e., the module q [ aZ + (b+sqrt(Delta))/2 Z ] where a and b are 65 // integers and q is rational. The quadratic order to which an instance of 66 // this class belongs is stored in a list of current quadratic orders, and 67 // a pointer to its list element is stored with each instance of this 68 // class. The form (a, b, c) is always normalized. 69 // 70 71 class quadratic_ideal 72 { 73 protected: 74 75 bigint a; // coefficient in the representation of the ideal 76 bigint b; // coefficient in the representation of the ideal 77 bigrational q; // coefficient in the representation of the ideal 78 qo_node *QO; // pointer to a quadratic order list entry 79 80 bool reduced_flag; // true, implies that ideal is reduced 81 82 void normalize(); 83 void normalize_imag(); 84 void normalize_real(); 85 86 bool is_normalized_imag() const; 87 bool is_normalized_real() const; 88 89 // < MM > 90 void reduce_imag(quadratic_number_standard & g, bool comp_red_number = false); 91 void reduce_real(quadratic_number_standard & g, bool comp_red_number = false); 92 93 void rho_imag(quadratic_number_standard & g); 94 void rho_real(quadratic_number_standard & g); 95 96 void inverse_rho_imag(quadratic_number_standard & g); 97 void inverse_rho_real(quadratic_number_standard & g); 98 // < /MM > 99 100 101 friend void multiply_imag(quadratic_ideal & C, const quadratic_ideal & A, 102 const quadratic_ideal & B); 103 friend void multiply_real(quadratic_ideal & C, const quadratic_ideal & A, 104 const quadratic_ideal & B); 105 106 friend void square_imag(quadratic_ideal & C, const quadratic_ideal & A); 107 friend void square_real(quadratic_ideal & C, const quadratic_ideal & A); 108 109 110 111 public: 112 113 // 114 // constructors and destructor 115 // 116 117 quadratic_ideal(); 118 quadratic_ideal(const bigint & a2, const bigint & b2, 119 const bigrational & q2); 120 quadratic_ideal(const long a2, const long b2, 121 const bigrational & q2); 122 quadratic_ideal(const bigint & a2, const bigint & b2, 123 const bigrational & q2, const quadratic_order & QO2); 124 quadratic_ideal(const long a2, const long b2, 125 const bigrational & q2, const quadratic_order & QO2); 126 quadratic_ideal(const quadratic_form & qf); 127 quadratic_ideal(const qi_class & A); 128 quadratic_ideal(const qi_class_real & A); 129 quadratic_ideal(const quadratic_ideal & A); 130 131 // < MM > 132 quadratic_ideal(const quadratic_order & QO2); 133 // < /MM > 134 135 ~quadratic_ideal(); 136 137 // 138 // assignments 139 // 140 141 void assign_zero(); 142 void assign_one(); 143 void assign_principal(const bigint & x, const bigint & y); 144 bool assign(const bigint & a2, const bigint & b2, const bigrational & q2); 145 bool assign(const long a2, const long b2, const bigrational & q2); 146 147 void assign_zero(const quadratic_order & QO2); 148 void assign(const quadratic_order & QO2); 149 void assign_one(const quadratic_order & QO2); 150 void assign_principal(const bigint & x, const bigint & y, 151 const quadratic_order & QO2); 152 bool assign(const bigint & a2, const bigint & b2, 153 const bigrational & q2, const quadratic_order & QO2); 154 bool assign(const long a2, const long b2, 155 const bigrational & q2, const quadratic_order & QO2); 156 157 void assign(const quadratic_form & qf); 158 void assign(const qi_class & B); 159 void assign(const qi_class_real & B); 160 void assign(const quadratic_ideal & B); 161 162 bool assign_order(const quadratic_order & QO2); 163 // < MM > 164 bool set_order(const quadratic_order & QO2); 165 // < /MM > 166 167 quadratic_ideal & operator = (const quadratic_ideal & A); 168 169 // < MM > 170 private: 171 void assign_module_of (const bigrational & nq, 172 quadratic_number_standard q1, 173 quadratic_number_standard q2); 174 175 public: 176 bool assign (const bigrational & nq, 177 const quadratic_number_standard & q1, 178 const quadratic_number_standard & q2); 179 // < /MM > 180 181 182 // 183 // access functions 184 // 185 186 bigint get_a() const; 187 bigint get_b() const; 188 bigrational get_q() const; 189 bigint get_c() const; 190 const quadratic_order & which_order() const; 191 friend const quadratic_order & which_order(const quadratic_ideal & A); 192 bigint discriminant() const; 193 194 // < MM > 195 const quadratic_order & get_order() const; 196 // < /MM > 197 198 199 200 // 201 // arithmetic operations 202 // 203 204 #ifndef HEADBANGER 205 friend void add(quadratic_ideal & C, const quadratic_ideal & A, 206 const quadratic_ideal & B); 207 friend void intersect(quadratic_ideal & C, const quadratic_ideal & A, 208 const quadratic_ideal & B); 209 #endif 210 friend void multiply(quadratic_ideal & C, const quadratic_ideal & A, 211 const quadratic_ideal & B); 212 friend void divide(quadratic_ideal & C, const quadratic_ideal & A, 213 const quadratic_ideal & B); 214 void invert(); 215 friend void inverse(quadratic_ideal & A, const quadratic_ideal & B); 216 friend quadratic_ideal inverse(const quadratic_ideal & B); 217 void conjugate(); 218 friend void get_conjugate(quadratic_ideal & A, const quadratic_ideal & B); 219 friend quadratic_ideal get_conjugate(const quadratic_ideal & B); 220 friend void square(quadratic_ideal & C, const quadratic_ideal & A); 221 friend void power(quadratic_ideal & C, const quadratic_ideal & A, 222 const bigint & i); 223 friend void power(quadratic_ideal & C, const quadratic_ideal & A, 224 const long i); 225 226 friend quadratic_ideal operator - (const quadratic_ideal & A); 227 228 #ifndef HEADBANGER 229 friend quadratic_ideal operator + (const quadratic_ideal & A, 230 const quadratic_ideal & B); 231 friend quadratic_ideal operator & (const quadratic_ideal & A, 232 const quadratic_ideal & B); 233 #endif 234 friend quadratic_ideal operator * (const quadratic_ideal & A, 235 const quadratic_ideal & B); 236 friend quadratic_ideal operator / (const quadratic_ideal & A, 237 const quadratic_ideal & B); 238 239 #ifndef HEADBANGER 240 quadratic_ideal & operator += (const quadratic_ideal & A); 241 quadratic_ideal & operator &= (const quadratic_ideal & A); 242 #endif 243 quadratic_ideal & operator *= (const quadratic_ideal & A); 244 quadratic_ideal & operator /= (const quadratic_ideal & A); 245 246 247 // < MM > 248 friend void multiply (quadratic_ideal & J, 249 const quadratic_ideal & I, 250 const quadratic_number_standard & g); 251 252 friend void divide (quadratic_ideal & J, 253 const quadratic_ideal & I, 254 const quadratic_number_standard & g); 255 // < /MM > 256 257 // 258 // comparisons 259 // 260 261 bool is_zero() const; 262 bool is_one() const; 263 bool is_equal(const quadratic_ideal & B) const; 264 bool is_subset(const quadratic_ideal & B) const; 265 bool is_proper_subset(const quadratic_ideal & B) const; 266 267 friend bool operator == (const quadratic_ideal &A, const quadratic_ideal &B); 268 friend bool operator != (const quadratic_ideal &A, const quadratic_ideal &B); 269 270 friend bool operator <= (const quadratic_ideal &A, const quadratic_ideal &B); 271 friend bool operator < (const quadratic_ideal &A, const quadratic_ideal &B); 272 friend bool operator >= (const quadratic_ideal &A, const quadratic_ideal &B); 273 friend bool operator > (const quadratic_ideal &A, const quadratic_ideal &B); 274 275 friend bool operator ! (const quadratic_ideal & A); 276 277 278 279 // 280 // basic functions 281 // 282 283 friend void swap(quadratic_ideal & A, quadratic_ideal & B); 284 285 286 // 287 // high level functions 288 // 289 290 bigrational smallest_rational() const; 291 bool is_integral() const; 292 bigint conductor() const; 293 bool is_invertible() const; 294 bigrational norm() const; 295 void ring_of_multipliers(quadratic_order & rm); 296 friend bool generate_prime_ideal(quadratic_ideal & A, const bigint & p); 297 friend bool generate_prime_ideal(quadratic_ideal & A, const bigint & p, 298 const quadratic_order & QO2); 299 // < MM > 300 bigint denominator() const; 301 void multiply_by_denominator(); 302 // < /MM > 303 304 // 305 // reduction 306 // 307 308 bool is_reduced() const; 309 void reduce(); 310 void reduce(quadratic_number_standard & g); 311 312 void rho(); 313 void rho(quadratic_number_standard & g); 314 friend void apply_rho(quadratic_ideal & A, const quadratic_ideal & B); 315 friend quadratic_ideal apply_rho(const quadratic_ideal & B); 316 317 void inverse_rho(); 318 void inverse_rho(quadratic_number_standard & g); 319 friend void apply_inverse_rho(quadratic_ideal & A, const quadratic_ideal & B); 320 friend quadratic_ideal apply_inverse_rho(const quadratic_ideal & B); 321 322 // for debugging purposes; should always return true; 323 bool is_normalized () const; 324 325 326 // < MM > 327 void local_close(quadratic_number_standard & alpha, 328 xbigfloat & a, 329 xbigfloat t, 330 long k); 331 332 void order_close(quadratic_number_power_product & alpha, 333 xbigfloat & a, 334 xbigfloat t, 335 long k); 336 337 void close (quadratic_number_power_product & alpha, 338 xbigfloat & a, 339 xbigfloat t, 340 long k); 341 // < /MM > 342 343 344 // 345 // equivalence and principality testing 346 // 347 348 bool is_equivalent(const quadratic_ideal & B) const; 349 bool is_principal() const; 350 351 352 353 // 354 // order, DL, subgroup 355 // 356 357 bigint order_in_CL() const; 358 bool DL(quadratic_ideal & G, bigint & x) const; 359 friend base_vector< bigint > subgroup(base_vector< quadratic_ideal > & G); 360 bigfloat regulator(); 361 bigint class_number(); 362 base_vector< bigint > class_group(); 363 364 365 // 366 // input/output 367 // 368 369 friend std::istream & operator >> (std::istream & in, quadratic_ideal & A); 370 friend std::ostream & operator << (std::ostream & out, const quadratic_ideal & A); 371 }; 372 373 // friend functions 374 375 void multiply_imag(quadratic_ideal & C, const quadratic_ideal & A, 376 const quadratic_ideal & B); 377 void multiply_real(quadratic_ideal & C, const quadratic_ideal & A, 378 const quadratic_ideal & B); 379 380 void square_imag(quadratic_ideal & C, const quadratic_ideal & A); 381 void square_real(quadratic_ideal & C, const quadratic_ideal & A); 382 383 // 384 // access functions 385 // 386 387 const quadratic_order & which_order(const quadratic_ideal & A); 388 389 // 390 // arithmetic operations 391 // 392 393 #ifndef HEADBANGER 394 void add(quadratic_ideal & C, const quadratic_ideal & A, 395 const quadratic_ideal & B); 396 void intersect(quadratic_ideal & C, const quadratic_ideal & A, 397 const quadratic_ideal & B); 398 #endif 399 void multiply(quadratic_ideal & C, const quadratic_ideal & A, 400 const quadratic_ideal & B); 401 void divide(quadratic_ideal & C, const quadratic_ideal & A, 402 const quadratic_ideal & B); 403 void inverse(quadratic_ideal & A, const quadratic_ideal & B); 404 quadratic_ideal inverse(const quadratic_ideal & B); 405 void get_conjugate(quadratic_ideal & A, const quadratic_ideal & B); 406 quadratic_ideal get_conjugate(const quadratic_ideal & B); 407 void square(quadratic_ideal & C, const quadratic_ideal & A); 408 void power(quadratic_ideal & C, const quadratic_ideal & A, 409 const bigint & i); 410 void power(quadratic_ideal & C, const quadratic_ideal & A, 411 const long i); 412 413 quadratic_ideal operator - (const quadratic_ideal & A); 414 415 #ifndef HEADBANGER 416 quadratic_ideal operator + (const quadratic_ideal & A, 417 const quadratic_ideal & B); 418 quadratic_ideal operator & (const quadratic_ideal & A, 419 const quadratic_ideal & B); 420 #endif 421 quadratic_ideal operator * (const quadratic_ideal & A, 422 const quadratic_ideal & B); 423 quadratic_ideal operator / (const quadratic_ideal & A, 424 const quadratic_ideal & B); 425 426 // < MM > 427 void multiply (quadratic_ideal & J, 428 const quadratic_ideal & I, 429 const quadratic_number_standard & g); 430 void divide (quadratic_ideal & J, 431 const quadratic_ideal & I, 432 const quadratic_number_standard & g); 433 // < /MM > 434 435 // 436 // comparisons 437 // 438 439 bool operator == (const quadratic_ideal &A, const quadratic_ideal &B); 440 bool operator != (const quadratic_ideal &A, const quadratic_ideal &B); 441 442 bool operator <= (const quadratic_ideal &A, const quadratic_ideal &B); 443 bool operator < (const quadratic_ideal &A, const quadratic_ideal &B); 444 bool operator >= (const quadratic_ideal &A, const quadratic_ideal &B); 445 bool operator > (const quadratic_ideal &A, const quadratic_ideal &B); 446 447 bool operator ! (const quadratic_ideal & A); 448 449 // 450 // basic functions 451 // 452 453 void swap(quadratic_ideal & A, quadratic_ideal & B); 454 455 // 456 // high level functions 457 // 458 459 bool generate_prime_ideal(quadratic_ideal & A, const bigint & p); 460 bool generate_prime_ideal(quadratic_ideal & A, const bigint & p, 461 const quadratic_order & QO2); 462 463 // 464 // reduction 465 // 466 467 void apply_rho(quadratic_ideal & A, const quadratic_ideal & B); 468 quadratic_ideal apply_rho(const quadratic_ideal & B); 469 void apply_inverse_rho(quadratic_ideal & A, const quadratic_ideal & B); 470 quadratic_ideal apply_inverse_rho(const quadratic_ideal & B); 471 472 // 473 // order, DL, subgroup 474 // 475 476 base_vector< bigint > subgroup(base_vector< quadratic_ideal > & G); 477 478 // 479 // input/output 480 // 481 482 std::istream & operator >> (std::istream & in, quadratic_ideal & A); 483 std::ostream & operator << (std::ostream & out, const quadratic_ideal & A); 484 485 486 // key function for hash tables 487 bigint quadratic_ideal_key(const quadratic_ideal & G); 488 489 490 491 #ifdef LIDIA_NAMESPACE 492 } // end of namespace LiDIA 493 # undef IN_NAMESPACE_LIDIA 494 #endif 495 496 497 498 #endif // LIDIA_QUADRATIC_IDEAL_H_GUARD_ 499