001/* 002 * $Id$ 003 */ 004 005package edu.jas.structure; 006 007 008import java.util.List; 009 010import org.apache.logging.log4j.LogManager; 011import org.apache.logging.log4j.Logger; 012 013 014/** 015 * Power class to compute powers of RingElem. 016 * @author Heinz Kredel 017 */ 018public class Power<C extends RingElem<C>> { 019 020 021 private static final Logger logger = LogManager.getLogger(Power.class); 022 023 024 private static final boolean debug = logger.isDebugEnabled(); 025 026 027 private final RingFactory<C> fac; 028 029 030 /** 031 * The constructor creates a Power object. 032 */ 033 public Power() { 034 this(null); 035 } 036 037 038 /** 039 * The constructor creates a Power object. 040 * @param fac ring factory 041 */ 042 public Power(RingFactory<C> fac) { 043 this.fac = fac; 044 } 045 046 047 /** 048 * power of a to the n-th, n positive. 049 * @param a element. 050 * @param n integer exponent ≥ 0. 051 * @return a^n. 052 */ 053 public static <C extends RingElem<C>> C positivePower(C a, long n) { 054 if (n <= 0) { 055 throw new IllegalArgumentException("only positive n allowed"); 056 } 057 if (a.isZERO() || a.isONE()) { 058 return a; 059 } 060 C b = a; 061 long i = n - 1; 062 C p = b; 063 do { 064 if (i % 2 == 1) { 065 p = p.multiply(b); 066 } 067 i = i / 2; 068 if (i > 0) { 069 b = b.multiply(b); 070 } 071 } while (i > 0); 072 return p; 073 } 074 075 076 /** 077 * power of a to the n-th, n positive. 078 * @param a element. 079 * @param n java.math.BigInteger exponent ≥ 0. 080 * @return a^n. 081 */ 082 public static <C extends RingElem<C>> C positivePower(C a, java.math.BigInteger n) { 083 if (n.signum() <= 0) { 084 throw new IllegalArgumentException("only positive n allowed"); 085 } 086 if (a.isZERO() || a.isONE()) { 087 return a; 088 } 089 C b = a; 090 if (n.compareTo(java.math.BigInteger.ONE) == 0) { 091 return b; 092 } 093 if (n.bitLength() <= 63) { 094 long l = n.longValue(); 095 return positivePower(a, l); 096 } 097 C p = a; 098 java.math.BigInteger i = n.subtract(java.math.BigInteger.ONE); 099 do { 100 if (i.testBit(0)) { 101 p = p.multiply(b); 102 } 103 i = i.shiftRight(1); 104 if (i.signum() > 0) { 105 b = b.multiply(b); 106 } 107 } while (i.signum() > 0); 108 return p; 109 } 110 111 112 /** 113 * power of a to the n-th, n positive, modulo m. 114 * @param a element. 115 * @param n integer exponent ≥ 0. 116 * @param m modulus. 117 * @return a^n mod m. 118 */ 119 public static <C extends RingElem<C>> C modPositivePower(C a, long n, C m) { 120 if (n <= 0) { 121 throw new IllegalArgumentException("only positive n allowed"); 122 } 123 if (a.isZERO() || a.isONE()) { 124 return a; 125 } 126 127 C b = a.remainder(m); 128 long i = n - 1; 129 C p = b; 130 do { 131 if (i % 2 == 1) { 132 p = p.multiply(b).remainder(m); 133 } 134 i = i / 2; 135 if (i > 0) { 136 b = b.multiply(b).remainder(m); 137 } 138 } while (i > 0); 139 return p; 140 } 141 142 143 /** 144 * power of a to the n-th, n positive, modulo m. 145 * @param a element. 146 * @param n big integer exponent ≥ 0. 147 * @param m modulus. 148 * @return a^n mod m. 149 */ 150 public static <C extends RingElem<C>> C modPositivePower(C a, java.math.BigInteger n, C m) { 151 if (n.signum() <= 0) { 152 throw new IllegalArgumentException("only positive n allowed"); 153 } 154 if (a.isZERO() || a.isONE()) { 155 return a; 156 } 157 158 C b = a.remainder(m); 159 java.math.BigInteger i = n.subtract(java.math.BigInteger.ONE); 160 C p = b; 161 do { 162 if (i.testBit(0)) { // i % 2 == 1 163 p = p.multiply(b).remainder(m); 164 } 165 i = i.shiftRight(1); // / 2; 166 if (i.signum() > 0) { 167 b = b.multiply(b).remainder(m); 168 } 169 } while (i.signum() > 0); 170 return p; 171 } 172 173 174 /** 175 * power of a to the n-th. 176 * @param a element. 177 * @param n integer exponent. 178 * @param fac ring factory. 179 * @return a^n, with 0^0 = 0 and a^{-n} = {1/a}^n. 180 */ 181 @SuppressWarnings("unchecked") 182 public static <C extends RingElem<C>> C power(RingFactory<C> fac, C a, long n) { 183 if (a == null || a.isZERO()) { 184 return a; 185 } 186 //return a; 187 return (C) Power.<MonoidElem> power((MonoidFactory) fac, a, n); 188 } 189 190 191 /** 192 * power of a to the n-th. 193 * @param a element. 194 * @param n integer exponent. 195 * @param fac monoid factory. 196 * @return a^n, with a^{-n} = {1/a}^n. 197 */ 198 public static <C extends MonoidElem<C>> C power(MonoidFactory<C> fac, C a, long n) { 199 if (n == 0) { 200 if (fac == null) { 201 throw new IllegalArgumentException("fac may not be null for a^0"); 202 } 203 return fac.getONE(); 204 } 205 if (a.isONE()) { 206 return a; 207 } 208 C b = a; 209 if (n < 0) { 210 b = a.inverse(); 211 n = -n; 212 } 213 if (n == 1) { 214 return b; 215 } 216 if (fac == null) { 217 throw new IllegalArgumentException("fac may not be null for n > 1"); 218 } 219 C p = fac.getONE(); 220 long i = n; 221 do { 222 if (i % 2 == 1) { 223 p = p.multiply(b); 224 } 225 i = i / 2; 226 if (i > 0) { 227 b = b.multiply(b); 228 } 229 } while (i > 0); 230 if (n > 11 && debug) { 231 logger.info("n = {}, p = {} ", n, p); 232 } 233 return p; 234 } 235 236 237 /** 238 * power of a to the n-th modulo m. 239 * @param a element. 240 * @param n integer exponent. 241 * @param m modulus. 242 * @param fac monoid factory. 243 * @return a^n mod m, with a^{-n} = {1/a}^n. 244 */ 245 public static <C extends MonoidElem<C>> C modPower(MonoidFactory<C> fac, C a, long n, C m) { 246 if (n == 0) { 247 if (fac == null) { 248 throw new IllegalArgumentException("fac may not be null for a^0"); 249 } 250 return fac.getONE(); 251 } 252 if (a.isONE()) { 253 return a; 254 } 255 C b = a.remainder(m); 256 if (n < 0) { 257 b = a.inverse().remainder(m); 258 n = -n; 259 } 260 if (n == 1) { 261 return b; 262 } 263 if (fac == null) { 264 throw new IllegalArgumentException("fac may not be null for n > 1"); 265 } 266 C p = fac.getONE(); 267 long i = n; 268 do { 269 if (i % 2 == 1) { 270 p = p.multiply(b).remainder(m); 271 } 272 i = i / 2; 273 if (i > 0) { 274 b = b.multiply(b).remainder(m); 275 } 276 } while (i > 0); 277 if (n > 11 && debug) { 278 logger.info("n = {}, p = {} ", n, p); 279 } 280 return p; 281 } 282 283 284 /** 285 * power of a to the n-th modulo m. 286 * @param a element. 287 * @param n integer exponent. 288 * @param m modulus. 289 * @param fac monoid factory. 290 * @return a^n mod m, with a^{-n} = {1/a}^n. 291 */ 292 public static <C extends MonoidElem<C>> C modPower(MonoidFactory<C> fac, C a, java.math.BigInteger n, 293 C m) { 294 if (n.signum() == 0) { 295 if (fac == null) { 296 throw new IllegalArgumentException("fac may not be null for a^0"); 297 } 298 return fac.getONE(); 299 } 300 if (a.isONE()) { 301 return a; 302 } 303 C b = a.remainder(m); 304 if (n.signum() < 0) { 305 b = a.inverse().remainder(m); 306 n = n.negate(); 307 } 308 if (n.compareTo(java.math.BigInteger.ONE) == 0) { 309 return b; 310 } 311 if (n.bitLength() <= 63) { 312 long l = n.longValue(); 313 return modPower(fac, a, l, m); 314 } 315 if (fac == null) { 316 throw new IllegalArgumentException("fac may not be null for n > 1"); 317 } 318 C p = fac.getONE(); 319 java.math.BigInteger i = n; 320 do { 321 if (i.testBit(0)) { 322 p = p.multiply(b).remainder(m); 323 } 324 i = i.shiftRight(1); 325 if (i.signum() > 0) { 326 b = b.multiply(b).remainder(m); 327 } 328 } while (i.signum() > 0); 329 logger.debug("n = {}, p = {} ", n, p); 330 return p; 331 } 332 333 334 /** 335 * power of a to the n-th. 336 * @param a element. 337 * @param n integer exponent. 338 * @return a^n, with 0^0 = 0. 339 */ 340 public C power(C a, long n) { 341 return power(fac, a, n); 342 } 343 344 345 /** 346 * power of a to the n-th. 347 * @param a long. 348 * @param n integer exponent. 349 * @return a^n, with a^0 = 1. 350 */ 351 public static long power(long a, long n) { 352 if (n == 0) { 353 return 1L; 354 } 355 if (a == 1L) { 356 return a; 357 } 358 long b = a; 359 if (n == 1L) { 360 return b; 361 } 362 long p = 1L; 363 long i = n; 364 do { 365 if (i % 2 == 1) { 366 p = p * b; 367 } 368 i = i / 2; 369 if (i > 0) { 370 b = b * b; 371 } 372 } while (i > 0); 373 if (n > 11 && debug) { 374 logger.info("n = {}, p = {} ", n, p); 375 } 376 return p; 377 } 378 379 380 /** 381 * power of a to the n-th mod m. 382 * @param a element. 383 * @param n integer exponent. 384 * @param m modulus. 385 * @return a^n mod m, with 0^0 = 0. 386 */ 387 public C modPower(C a, long n, C m) { 388 return modPower(fac, a, n, m); 389 } 390 391 392 /** 393 * power of a to the n-th mod m. 394 * @param a element. 395 * @param n integer exponent. 396 * @param m modulus. 397 * @return a^n mod m, with 0^0 = 0. 398 */ 399 public C modPower(C a, java.math.BigInteger n, C m) { 400 return modPower(fac, a, n, m); 401 } 402 403 404 /** 405 * Logarithm. 406 * @param p logarithm base. 407 * @param a element. 408 * @return k ≥ 1 minimal with p^k ≥ a. 409 */ 410 public static <C extends RingElem<C>> long logarithm(C p, C a) { 411 //if ( p.compareTo(a) < 0 ) { 412 // return 0L; 413 //} 414 long k = 1L; 415 C m = p; 416 while (m.compareTo(a) < 0) { 417 m = m.multiply(p); 418 k++; 419 } 420 return k; 421 } 422 423 424 /** 425 * Logarithm. 426 * @param p logarithm base. 427 * @param a element. 428 * @return k ≥ 1 minimal with p^k ≥ a. 429 */ 430 public static <C extends RingElem<C>> long logarithm(long p, long a) { 431 long k = 1; 432 long m = p; 433 while (m < a) { 434 m = m * p; 435 k++; 436 } 437 return k; 438 } 439 440 441 /** 442 * Multiply elements in list. 443 * @param A list of elements (a_0,...,a_k). 444 * @param fac ring factory. 445 * @return prod(i=0,...k) a_i. 446 */ 447 public static <C extends RingElem<C>> C multiply(RingFactory<C> fac, List<C> A) { 448 return multiply((MonoidFactory<C>) fac, A); 449 } 450 451 452 /** 453 * Multiply elements in list. 454 * @param A list of elements (a_0,...,a_k). 455 * @param fac monoid factory. 456 * @return prod(i=0,...k) a_i. 457 */ 458 public static <C extends MonoidElem<C>> C multiply(MonoidFactory<C> fac, List<C> A) { 459 if (fac == null) { 460 throw new IllegalArgumentException("fac may not be null for empty list"); 461 } 462 C res = fac.getONE(); 463 if (A == null || A.isEmpty()) { 464 return res; 465 } 466 for (C a : A) { 467 res = res.multiply(a); 468 } 469 return res; 470 } 471 472 473 /** 474 * Sum elements in list. 475 * @param A list of elements (a_0,...,a_k). 476 * @param fac ring factory. 477 * @return sum(i=0,...k) a_i. 478 */ 479 public static <C extends RingElem<C>> C sum(RingFactory<C> fac, List<C> A) { 480 return sum((AbelianGroupFactory<C>) fac, A); 481 } 482 483 484 /** 485 * Sum elements in list. 486 * @param A list of elements (a_0,...,a_k). 487 * @param fac monoid factory. 488 * @return sum(i=0,...k) a_i. 489 */ 490 public static <C extends AbelianGroupElem<C>> C sum(AbelianGroupFactory<C> fac, List<C> A) { 491 if (fac == null) { 492 throw new IllegalArgumentException("fac may not be null for empty list"); 493 } 494 C res = fac.getZERO(); 495 if (A == null || A.isEmpty()) { 496 return res; 497 } 498 for (C a : A) { 499 res = res.sum(a); 500 } 501 return res; 502 } 503 504}