class Integer
Constants
- MILLER_RABIN_BASES
Public Class Methods
each_prime(ubound) { |prime| ... }
click to toggle source
Iterates the given block over all prime numbers.
See Prime
#each for more details.
# File prime-0.1.2/lib/prime.rb, line 122 def Integer.each_prime(ubound, &block) # :yields: prime Prime.each(ubound, &block) end
from_prime_division(pd)
click to toggle source
Re-composes a prime factorization and returns the product.
See Prime#int_from_prime_division
for more details.
# File prime-0.1.2/lib/prime.rb, line 22 def Integer.from_prime_division(pd) Prime.int_from_prime_division(pd) end
Public Instance Methods
prime?()
click to toggle source
Returns true if self
is a prime number, else returns false. Not recommended for very big integers (> 10**23).
# File prime-0.1.2/lib/prime.rb, line 35 def prime? return self >= 2 if self <= 3 if (bases = miller_rabin_bases) return miller_rabin_test(bases) end return true if self == 5 return false unless 30.gcd(self) == 1 (7..Integer.sqrt(self)).step(30) do |p| return false if self%(p) == 0 || self%(p+4) == 0 || self%(p+6) == 0 || self%(p+10) == 0 || self%(p+12) == 0 || self%(p+16) == 0 || self%(p+22) == 0 || self%(p+24) == 0 end true end
prime_division(generator = Prime::Generator23.new)
click to toggle source
Returns the factorization of self
.
See Prime#prime_division
for more details.
# File prime-0.1.2/lib/prime.rb, line 29 def prime_division(generator = Prime::Generator23.new) Prime.prime_division(self, generator) end
Private Instance Methods
miller_rabin_bases()
click to toggle source
# File prime-0.1.2/lib/prime.rb, line 69 def miller_rabin_bases # Miller-Rabin's complexity is O(k log^3n). # So we can reduce the complexity by reducing the number of bases tested. # Using values from https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test i = case when self < 0xffff then # For small integers, Miller Rabin can be slower # There is no mathematical significance to 0xffff return nil # when self < 2_047 then 0 when self < 1_373_653 then 1 when self < 9_080_191 then 2 when self < 25_326_001 then 3 when self < 3_215_031_751 then 4 when self < 4_759_123_141 then 5 when self < 1_122_004_669_633 then 6 when self < 2_152_302_898_747 then 7 when self < 3_474_749_660_383 then 8 when self < 341_550_071_728_321 then 9 when self < 3_825_123_056_546_413_051 then 10 when self < 318_665_857_834_031_151_167_461 then 11 when self < 3_317_044_064_679_887_385_961_981 then 12 else return nil end MILLER_RABIN_BASES[i] end
miller_rabin_test(bases)
click to toggle source
# File prime-0.1.2/lib/prime.rb, line 96 def miller_rabin_test(bases) return false if even? r = 0 d = self >> 1 while d.even? d >>= 1 r += 1 end self_minus_1 = self-1 bases.each do |a| x = a.pow(d, self) next if x == 1 || x == self_minus_1 || a == self return false if r.times do x = x.pow(2, self) break if x == self_minus_1 end end true end