123456789_123456789_123456789_123456789_123456789_

Class: Integer

Relationships & Source Files
Inherits: Object
Defined in: lib/prime.rb

Constant Summary

  • MILLER_RABIN_BASES = private
    # File 'lib/prime.rb', line 52 
    [
  [2],
  [2,3],
  [31,73],
  [2,3,5],
  [2,3,5,7],
  [2,7,61],
  [2,13,23,1662803],
  [2,3,5,7,11],
  [2,3,5,7,11,13],
  [2,3,5,7,11,13,17],
  [2,3,5,7,11,13,17,19,23],
  [2,3,5,7,11,13,17,19,23,29,31,37],
  [2,3,5,7,11,13,17,19,23,29,31,37,41],
].map!(&:freeze).freeze

Class Method Summary

Instance Attribute Summary

Instance Method Summary

Class Method Details

.each_prime(ubound, &block)

Iterates the given block over all prime numbers.

See ::Prime#each for more details.

[ GitHub ] 

  


# File 'lib/prime.rb', line 122



def Integer.each_prime(ubound, &block) # :yields: prime
  Prime.each(ubound, &block)
end


  








  

    .from_prime_division(pd)  
  



  

    

Re-composes a prime factorization and returns the product.



See Prime#int_from_prime_division for more details.


  



  [ GitHub ]


  

  


# File 'lib/prime.rb', line 22



def Integer.from_prime_division(pd)
  Prime.int_from_prime_division(pd)
end


  







Instance Attribute Details



  

    #prime?  ⇒ Boolean  (readonly)
  



  

    

Returns true if self is a prime number, else returns false. Not recommended for very big integers (> 10**23).


  





  


  [ GitHub ]


  

  


# File '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


  







Instance Method Details



  

    #miller_rabin_bases   (private)
  

  [ GitHub ]


  

  


# File 'lib/prime.rb', line 69



private 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)   (private)
  

  [ GitHub ]


  

  


# File 'lib/prime.rb', line 96



private 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


  








  

    #prime_division(generator = Prime::Generator23.new)  
  



  

    

Returns the factorization of self.



See Prime#prime_division for more details.


  



  [ GitHub ]


  

  


# File 'lib/prime.rb', line 29



def prime_division(generator = Prime::Generator23.new)
  Prime.prime_division(self, generator)
end