<commit_before>module RSA
  ##
  # Mathematical helper functions for RSA.
  module Math
    extend ::Math

    class ArithmeticError < ArgumentError; end

    ##
    # Performs a primality test on the integer `n`, returning `true` if it
    # is a prime.
    #
    # @example
    #   1.upto(10).select { |n| RSA::Math.prime?(n) }  #=> [2, 3, 5, 7]
    #
    # @param  [Integer] n
    # @return [Boolean] `true` if `n` is a prime number, `false` otherwise
    # @see    http://en.wikipedia.org/wiki/Primality_test
    # @see    http://ruby-doc.org/core-1.9/classes/Prime.html
    def self.prime?(n)
      if n.respond_to?(:prime?)
        n.prime?
      else
        require 'prime' unless defined?(Prime) # Ruby 1.9+ only
        Prime.prime?(n)
      end
    end

    ##
    # Returns `true` if the integer `a` is coprime (relatively prime) to
    # integer `b`.
    #
    # @example
    #   RSA::Math.coprime?(6, 35)                      #=> true
    #   RSA::Math.coprime?(6, 27)                      #=> false
    #
    # @param  [Integer] a an integer
    # @param  [Integer] b an integer
    # @return [Boolean] `true` if `a` and `b` are coprime, `false` otherwise
    # @see    http://en.wikipedia.org/wiki/Coprime
    # @see    http://mathworld.wolfram.com/RelativelyPrime.html
    def self.coprime?(a, b)
      gcd(a, b).equal?(1)
    end

    ##
    # Returns the greatest common divisor (GCD) of the two integers `a` and
    # `b`. The GCD is the largest positive integer that divides both numbers
    # without a remainder.
    #
    # @example
    #   RSA::Math.gcd(3, 5)                            #=> 1
    #   RSA::Math.gcd(8, 12)                           #=> 4
    #   RSA::Math.gcd(12, 60)                          #=> 12
    #   RSA::Math.gcd(90, 12)                          #=> 6
    #
    # @param  [Integer] a an integer
    # @param  [Integer] b an integer
    # @return [Integer] the greatest common divisor of `a` and `b`
    # @see    http://en.wikipedia.org/wiki/Greatest_common_divisor
    # @see    http://mathworld.wolfram.com/GreatestCommonDivisor.html
    def self.gcd(a, b)
      a.gcd(b)
    end

    ##
    # Returns the Bezout coefficients of the two nonzero integers `a` and
    # `b` using the extended Euclidean algorithm.
    #
    # @example
    #   RSA::Math.egcd(120, 23)                        #=> [-9, 47]
    #   RSA::Math.egcd(421, 111)                       #=> [-29, 110]
    #   RSA::Math.egcd(93, 219)                        #=> [33, -14]
    #   RSA::Math.egcd(4864, 3458)                     #=> [32, -45]
    #
    # @param  [Integer] a a nonzero integer
    # @param  [Integer] b a nonzero integer
    # @return [Array(Integer, Integer)] the Bezout coefficients `x` and `y`
    # @raise  [ZeroDivisionError] if `a` or `b` is zero
    # @see    http://en.wikipedia.org/wiki/B%C3%A9zout's_identity
    # @see    http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
    # @see    http://mathworld.wolfram.com/ExtendedGreatestCommonDivisor.html
    def self.egcd(a, b)
      if a.modulo(b).zero?
        [0, 1]
      else
        x, y = egcd(b, a.modulo(b))
        [y, x - y * a.div(b)]
      end
    end

    ##
    # Returns the modular multiplicative inverse of the integer `b` modulo
    # `m`.
    #
    # This is presently a very naive implementation. Don't rely on it for
    # anything but very small values of `m`.
    #
    # @example
    #   RSA::Math.modinv(3, 11)                        #=> 4
    #   RSA::Math.modinv(6, 35)                        #=> 6
    #   RSA::Math.modinv(-6, 35)                       #=> 29
    #   RSA::Math.modinv(6, 36)                        #=> ArithmeticError
    #
    # @param  [Integer] b
    # @param  [Integer] m the modulus
    # @return [Integer] the modular multiplicative inverse
    # @raise  [ArithmeticError] if `m` <= 0, or if `b` not coprime to `m`
    # @see    http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
    # @see    http://mathworld.wolfram.com/ModularInverse.html
    def self.modinv(b, m)
      if m > 0 && coprime?(b, m)
        (1...m).find { |x| (b * x).modulo(m).equal?(1) } || 0
      else
        raise ArithmeticError, "modulus #{m} is not positive" if m <= 0
        raise ArithmeticError, "#{b} is not coprime to #{m}"
      end
    end

    ##
    # Performs modular exponentiation in a memory-efficient manner.
    #
    # This is equivalent to `base**exponent % modulus` but much faster for
    # large exponents.
    #
    # The running time of the used algorithm, the right-to-left binary
    # method, is O(log _exponent_).
    #
    # @example
    #   RSA::Math.modpow(5, 3, 13)                     #=> 8
    #   RSA::Math.modpow(4, 13, 497)                   #=> 445
    #
    # @param  [Integer] base
    # @param  [Integer] exponent
    # @param  [Integer] modulus
    # @return [Integer]
    # @see    http://en.wikipedia.org/wiki/Modular_exponentiation
    def self.modpow(base, exponent, modulus)
      result = 1
      while exponent > 0
        result   = (base * result) % modulus unless (exponent & 1).zero?
        base     = (base * base)   % modulus
        exponent >>= 1
      end
      result
    end

    ##<commit_msg>Optimized the RSA::Math.modinv method's running time down to O(log2 m) from O(m) previously.<commit_after>module RSA
  ##
  # Mathematical helper functions for RSA.
  module Math
    extend ::Math

    class ArithmeticError < ArgumentError; end

    ##
    # Performs a primality test on the integer `n`, returning `true` if it
    # is a prime.
    #
    # @example
    #   1.upto(10).select { |n| RSA::Math.prime?(n) }  #=> [2, 3, 5, 7]
    #
    # @param  [Integer] n
    # @return [Boolean] `true` if `n` is a prime number, `false` otherwise
    # @see    http://en.wikipedia.org/wiki/Primality_test
    # @see    http://ruby-doc.org/core-1.9/classes/Prime.html
    def self.prime?(n)
      if n.respond_to?(:prime?)
        n.prime?
      else
        require 'prime' unless defined?(Prime) # Ruby 1.9+ only
        Prime.prime?(n)
      end
    end

    ##
    # Returns `true` if the integer `a` is coprime (relatively prime) to
    # integer `b`.
    #
    # @example
    #   RSA::Math.coprime?(6, 35)                      #=> true
    #   RSA::Math.coprime?(6, 27)                      #=> false
    #
    # @param  [Integer] a an integer
    # @param  [Integer] b an integer
    # @return [Boolean] `true` if `a` and `b` are coprime, `false` otherwise
    # @see    http://en.wikipedia.org/wiki/Coprime
    # @see    http://mathworld.wolfram.com/RelativelyPrime.html
    def self.coprime?(a, b)
      gcd(a, b).equal?(1)
    end

    ##
    # Returns the greatest common divisor (GCD) of the two integers `a` and
    # `b`. The GCD is the largest positive integer that divides both numbers
    # without a remainder.
    #
    # @example
    #   RSA::Math.gcd(3, 5)                            #=> 1
    #   RSA::Math.gcd(8, 12)                           #=> 4
    #   RSA::Math.gcd(12, 60)                          #=> 12
    #   RSA::Math.gcd(90, 12)                          #=> 6
    #
    # @param  [Integer] a an integer
    # @param  [Integer] b an integer
    # @return [Integer] the greatest common divisor of `a` and `b`
    # @see    http://en.wikipedia.org/wiki/Greatest_common_divisor
    # @see    http://mathworld.wolfram.com/GreatestCommonDivisor.html
    def self.gcd(a, b)
      a.gcd(b)
    end

    ##
    # Returns the Bezout coefficients of the two nonzero integers `a` and
    # `b` using the extended Euclidean algorithm.
    #
    # @example
    #   RSA::Math.egcd(120, 23)                        #=> [-9, 47]
    #   RSA::Math.egcd(421, 111)                       #=> [-29, 110]
    #   RSA::Math.egcd(93, 219)                        #=> [33, -14]
    #   RSA::Math.egcd(4864, 3458)                     #=> [32, -45]
    #
    # @param  [Integer] a a nonzero integer
    # @param  [Integer] b a nonzero integer
    # @return [Array(Integer, Integer)] the Bezout coefficients `x` and `y`
    # @raise  [ZeroDivisionError] if `a` or `b` is zero
    # @see    http://en.wikipedia.org/wiki/B%C3%A9zout's_identity
    # @see    http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
    # @see    http://mathworld.wolfram.com/ExtendedGreatestCommonDivisor.html
    def self.egcd(a, b)
      if a.modulo(b).zero?
        [0, 1]
      else
        x, y = egcd(b, a.modulo(b))
        [y, x - y * a.div(b)]
      end
    end

    ##
    # Returns the modular multiplicative inverse of the integer `b` modulo
    # `m`, where `b <= m`.
    #
    # The running time of the used algorithm, the extended Euclidean
    # algorithm, is on the order of O(log2 _m_).
    #
    # @example
    #   RSA::Math.modinv(3, 11)                        #=> 4
    #   RSA::Math.modinv(6, 35)                        #=> 6
    #   RSA::Math.modinv(-6, 35)                       #=> 29
    #   RSA::Math.modinv(6, 36)                        #=> ArithmeticError
    #
    # @param  [Integer] b
    # @param  [Integer] m the modulus
    # @return [Integer] the modular multiplicative inverse
    # @raise  [ArithmeticError] if `m` <= 0, or if `b` not coprime to `m`
    # @see    http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
    # @see    http://mathworld.wolfram.com/ModularInverse.html
    def self.modinv(b, m)
      if m > 0 && coprime?(b, m)
        egcd(b, m).first.modulo(m)
      else
        raise ArithmeticError, "modulus #{m} is not positive" if m <= 0
        raise ArithmeticError, "#{b} is not coprime to #{m}"
      end
    end

    ##
    # Performs modular exponentiation in a memory-efficient manner.
    #
    # This is equivalent to `base**exponent % modulus` but much faster for
    # large exponents.
    #
    # The running time of the used algorithm, the right-to-left binary
    # method, is on the order of O(log _exponent_).
    #
    # @example
    #   RSA::Math.modpow(5, 3, 13)                     #=> 8
    #   RSA::Math.modpow(4, 13, 497)                   #=> 445
    #
    # @param  [Integer] base
    # @param  [Integer] exponent
    # @param  [Integer] modulus
    # @return [Integer]
    # @see    http://en.wikipedia.org/wiki/Modular_exponentiation
    def self.modpow(base, exponent, modulus)
      result = 1
      while exponent > 0
        result   = (base * result) % modulus unless (exponent & 1).zero?
        base     = (base * base)   % modulus
        exponent >>= 1
      end
      result
    end

    ##
{'fraction_non_alphanumeric': 0.1351867774911627, 'fraction_numerical': 0.022833667717588612, 'mean_word_length': 1.8445652173913043, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2919888', 'n_tokens_mistral': 3809, 'n_tokens_neox': 3488, 'n_words': 947}