Method: Abst::MPQS#find_factor_single_thread

Defined in:

lib/include/prime_mpqs.rb

#find_factor_single_thread ⇒ Object

# File 'lib/include/prime_mpqs.rb', line 147

def find_factor_single_thread
	r_list = []
	factorization = []
	big_prime_sup = []

	loop do
		# Create polynomial
		a, b, c, d = next_poly

		# Sieve
#temp = Time.now.to_i + Time.now.usec.to_f / 10 ** 6
		sieve_rslt = sieve(a, b, c, d)
#@@proc_time[:sieve] += Time.now.to_i + Time.now.usec.to_f / 10 ** 6 - temp
		next if sieve_rslt.empty?
		f, big, r = eliminate_big_primes(sieve_rslt)
		next if f.empty?

		# Gaussian elimination
		factorization += f
		r_list += r
		big_prime_sup += big

#@@proc_time[:gaussian] -= Time.now.to_i + Time.now.usec.to_f / 10 ** 6
		eliminated = gaussian_elimination(f)
#@@proc_time[:gaussian] += Time.now.to_i + Time.now.usec.to_f / 10 ** 6
		eliminated.each do |row|
			x = y = 1
			f = Array.new(@factor_base_size, 0)
			factorization.size.times do |i|
				next if row[i] == 0
				x = x * r_list[i] % @n
				f = f.zip(factorization[i]).map{|e1, e2| e1 + e2}
				y = y * big_prime_sup[i] % @n
			end

			2.upto(@factor_base_size - 1) do |i|
				y = y * Abst.power(@factor_base[i], f[i] >> 1, @n) % @n
			end
			y = (y << (f[1] >> 1)) % @n

			z = Abst.lehmer_gcd(x - y, @original_n)
			return z if 1 < z and z < @original_n
		end
	end
end