Class: FasterPrime::PrimalityTest::APRCL::ZZeta

Inherits:
Object
  • Object
show all
Defined in:
lib/faster_prime/primality_test.rb

Overview

A group algebra Z (linear sum of p^k-th roots of unity)

Constant Summary collapse

@@one = 
{}

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(coefs, p, k) ⇒ ZZeta

Returns a new instance of ZZeta.



421
422
423
424
425
426
427
428
429
430
 
# File 'lib/faster_prime/primality_test.rb', line 421

def initialize(coefs, p, k)
  @coefs = coefs
  @p, @k = p, k
  @pk1 = p ** (k - 1) # p^(k-1)
  @pk = @pk1 * p      # p^k
  @p1pk1 = @pk - @pk1 # (p-1) p^(k-1)
  if @pk != @coefs.size
    raise "coefs.size (#{ coefs.size }) must be equal to #{ @p }**#{ @k }"
  end
end

Class Method Details

.monomial(p, k, i) ⇒ Object

generates zeta_p^k^i



442
443
444
445
446
 
# File 'lib/faster_prime/primality_test.rb', line 442

def self.monomial(p, k, i)
  coefs = [0] * (p ** k)
  coefs[i] = 1
  ZZeta.new(coefs, p, k)
end

.one(p, k) ⇒ Object

generates 1



436
437
438
 
# File 'lib/faster_prime/primality_test.rb', line 436

def self.one(p, k)
  @@one[p ** k] ||= monomial(p, k, 0)
end

Instance Method Details

#*(other) ⇒ Object

polynomial multiplication



459
460
461
462
463
464
465
466
467
468
 
# File 'lib/faster_prime/primality_test.rb', line 459

def *(other)
  coefs = [0] * @pk
  other.coefs.each_with_index do |oc, j|
    next if oc == 0
    @pk.times do |i|
      coefs[(i + j) % @pk] += @coefs[i] * oc
    end
  end
  ZZeta.new(coefs, @p, @k)
end

#==(other) ⇒ Object Also known as: eql?

for hashing



449
 
# File 'lib/faster_prime/primality_test.rb', line 449

def ==(other); @coefs == other.coefs; end

#hash ⇒ Object 



450
 
# File 'lib/faster_prime/primality_test.rb', line 450

def hash; @coefs.hash; end

#inspect ⇒ Object 



538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
 
# File 'lib/faster_prime/primality_test.rb', line 538

def inspect
  s = []
  (@pk - 1).downto(0) do |i|
    c = @coefs[i]
    next if c == 0
    s << (c > 0 ? ?+ : ?-) +
      case
      when i == 0 then c.abs.to_s
      when c.abs == 1 then i == 1 ? "z" : "z^#{ i }"
      else "#{ c.abs }#{ i == 1 ? "z" : "z^#{ i }" }"
      end
  end
  return "0" if s.empty?
  s.first[0, 1] = "" if s.first[0] == ?+
  s.join
end

#mod_pow(exp, n) ⇒ Object

polynomial power modulo n



471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
 
# File 'lib/faster_prime/primality_test.rb', line 471

def mod_pow(exp, n)
  return ZZeta.one(@p, @k) if exp == 0

  r = nil
  z = reduce_mod!(n)
  len = exp.bit_length
  len.times do |i|
    if exp[i] == 1
      r = r ? (z * r).reduce_mod!(n) : z
      return r if i == len - 1
    end
    z = z.sqr.reduce_mod!(n)
  end

  raise "assert not reached"
end

#reduce! ⇒ Object

generate a reminder divided by CyclotomicPolynomial(p^k)



503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
 
# File 'lib/faster_prime/primality_test.rb', line 503

def reduce!
  # CyclotomicPolynomial(n) = \Prod_{d|n} (x^{n/d} - 1)^\moeb{d}
  #
  # CyclotomicPolynomial(p^k) =
  #   (x^{p^ k   } - 1)^\moeb{p^0}  (case d = p^0)
  # * (x^{p^{k-1}} - 1)^\moeb{p^1}  (case d = p^1)
  # ...
  # * (x^{p^ 0   } - 1)^\moeb{p^k}  (case d = p^k)
  # = (x^{p^k} - 1) / (x^{p^{k-1}} - 1)
  # = \Sum_{0 <= i < p} (x^{i p^{k-1}})
  @p1pk1.times do |i|
    @coefs[i] -= @coefs[@p1pk1 + (i % @pk1)]
  end
  @pk1.times do |i|
    @coefs[@p1pk1 + i] = 0
  end
  self
end

#reduce_mod!(n) ⇒ Object

reduce modulo n



523
524
525
526
527
528
529
 
# File 'lib/faster_prime/primality_test.rb', line 523

def reduce_mod!(n)
  @pk.times do |i|
    # I would use centermod if it was built-in...
    @coefs[i] = (@coefs[i] - @coefs[@p1pk1 + (i % @pk1)]) % n
  end
  self
end

#scalar(n) ⇒ Object

scalar multiplication



454
455
456
 
# File 'lib/faster_prime/primality_test.rb', line 454

def scalar(n)
  ZZeta.new(@coefs.map {|x| x * n }, @p, @k)
end

#sqr ⇒ Object

polynomial square (self * self) assumes self is already reduced



490
491
492
493
494
495
496
497
498
499
500
 
# File 'lib/faster_prime/primality_test.rb', line 490

def sqr
  coefs = [0] * @pk
  @p1pk1.times do |j|
    oc = @coefs[j]
    next if oc == 0
    @p1pk1.times do |i|
      coefs[(i + j) % @pk] += @coefs[i] * oc
    end
  end
  ZZeta.new(coefs, @p, @k)
end

#substitute(x) ⇒ Object

replace zeta with zeta^x



532
533
534
535
536
 
# File 'lib/faster_prime/primality_test.rb', line 532

def substitute(x)
  coefs = []
  @pk.times {|i| coefs << @coefs[(x * i) % @pk] }
  ZZeta.new(coefs, @p, @k)
end