# 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.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.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.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.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.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.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