Class: FasterPrime::MPQS::GaussianElimination

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

Overview

Incremental gaussian elimination.

    1. Lenstra, and M. S. Manasse,

“Compact incremental Gaussian Elimination over Z/2Z.” (1988) dl.acm.org/citation.cfm?id=896266

Instance Method Summary collapse

Constructor Details

#initialize(m) ⇒ GaussianElimination

Returns a new instance of GaussianElimination.



395
396
397
398
399
400
401
402
 
# File 'lib/faster_prime/prime_factorization.rb', line 395

def initialize(m)
  @n = 0
  @m = m
  @d = []
  @e = []
  @u = []
  @v = []
end

Instance Method Details

#[]=(es, val) ⇒ Object 



404
405
406
407
408
 
# File 'lib/faster_prime/prime_factorization.rb', line 404

def []=(es, val)
  @d << es
  @e << nil
  @v << val
end

#eliminate ⇒ Object 



414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
 
# File 'lib/faster_prime/prime_factorization.rb', line 414

def eliminate
  n2 = @d.size

  @n.times do |i|
    if @u[i]
      @e[@u[i]] = i
      @n.upto(n2 - 1) do |j|
        @d[j] ^= @d[i] if @d[j][@u[i]] == 1
      end
    end
  end

  @n.upto(n2 - 1) do |j|
    found = false

    @m.times do |i|
      if @d[j][i] == 1 && !@e[i]
        @u[j] = i
        @e[@u[j]] = j
        @d[j] &= ~(1 << @u[j])
        (j + 1).upto(n2 - 1) do |k|
          @d[k] ^= @d[j] if @d[k][@u[j]] == 1
        end
        found = true
        break
      end
    end

    if !found
      # linear dependency found
      @u[j] = nil
      c = {}
      c[j] = true
      @m.times do |k|
        c[@e[k]] = true if @d[j][k] == 1
      end
      yield c.keys.map {|k| @v[k] }
    end
  end

  @n = n2
end

#size ⇒ Object 



410
411
412
 
# File 'lib/faster_prime/prime_factorization.rb', line 410

def size
  @d.size
end