Class: FasterPrime::PrimalityTest::APRCL::JacobiSumTableClass

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

Instance Method Summary collapse

Constructor Details

#initialize ⇒ JacobiSumTableClass

Algorithm 9.1.27 (Precomputations) Note that this computes the table lazily, i.e., on demand



353
354
355
356
357
 
# File 'lib/faster_prime/primality_test.rb', line 353

def initialize
  @f = {} # a table of the function f(x) in 2. (1)
  @j = {} # J(p,q)
  @j3_j2 = {} # J3(p,q) and J2(p,q)
end

Instance Method Details

#calc_f(q) ⇒ Object

compute a table of the function f(x) such that 1 - g^x = g^f(x), where g is a primitive root modulo q



367
368
369
370
371
372
373
374
375
 
# File 'lib/faster_prime/primality_test.rb', line 367

def calc_f(q)
  return @f[q] if @f[q]

  g = Utils.primitive_root(q)
  f, h = [], {}
  1.upto(q - 2) {|x| h[(1 - Utils.mod_pow(g, x, q)) % q] = x }
  1.upto(q - 2) {|fx| f[h[Utils.mod_pow(g, fx, q)]] = fx }
  @f[q] = f
end

#clear ⇒ Object 



359
360
361
362
363
 
# File 'lib/faster_prime/primality_test.rb', line 359

def clear
  @f.clear
  @j.clear
  @j3_j2.clear
end

#get_j(p, q) ⇒ Object

compute J(p,q)



378
379
380
381
382
383
384
385
386
387
388
389
390
 
# File 'lib/faster_prime/primality_test.rb', line 378

def get_j(p, q)
  # assumes that p >= 3 or (p == 2 && k >= 2)
  return @j[[p, q]] if @j[[p, q]]

  f = calc_f(q)
  k = Utils.valuation(q - 1, p)
  pk = p ** k

  # J(p,q) = \Sum_{1<=x<=q-2} (zeta_{p^k}^{x+f(x)})
  coefs = [0] * pk
  1.upto(q - 2) {|x| coefs[(x + f[x]) % pk] += 1 }
  @j[[p, q]] = ZZeta.new(coefs, p, k).reduce!
end

#get_j3_j2(q) ⇒ Object

compute J_3(q) and J_2(q)



393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
 
# File 'lib/faster_prime/primality_test.rb', line 393

def get_j3_j2(q)
  # assumes that p == 2 && k >= 3
  return @j3_j2[q] if @j3_j2[q]

  f = calc_f(q)
  k = Utils.valuation(q - 1, 2)
  pk = 2 ** k

  # coefs3: \Sum_{1<=x<=q-2} (zeta_{2^k}^{2x+f(x)})
  # coefs2: \Sum_{1<=x<=q-2} (zeta_{2^3}^{3x+f(x)})
  coefs3 = [0] * pk
  coefs2 = [0] * pk
  1.upto(q - 2) do |x|
    coefs3[(2 * x + f[x]) % pk] += 1
    coefs2[(3 * x + f[x]) % 8 * (pk / 8)] += 1
  end
  # J_3(q) = J(2,q) coefs3, J_2(q) = ( coefs2 )^2
  j3 = (get_j(2, q) * ZZeta.new(coefs3, 2, k)).reduce!
  j2 = ZZeta.new(coefs2, 2, k).reduce!.sqr.reduce!
  @j3_j2[q] = [j3, j2]
end