Module: RSA::Math

Extended by:
Math
Defined in:
lib/rsa/math.rb

Overview

Mathematical helper functions for RSA.

Defined Under Namespace

Classes: ArithmeticError

Constant Summary collapse

ONE = 
BigDecimal('1')

Class Method Summary collapse

Class Method Details

.coprime?(a, b) ⇒ Boolean

Returns ‘true` if the integer `a` is coprime (relatively prime) to integer `b`.

Examples:

RSA::Math.coprime?(6, 35)                      #=> true
RSA::Math.coprime?(6, 27)                      #=> false

Parameters:

  • a (Integer) —

    an integer

  • b (Integer) —

    an integer

Returns:

  • (Boolean) —

    ‘true` if `a` and `b` are coprime, `false` otherwise

See Also:



101
102
103
 
# File 'lib/rsa/math.rb', line 101

def self.coprime?(a, b)
  gcd(a, b).equal?(1)
end

.egcd(a, b) ⇒ Array(Integer, Integer)

Returns the Bezout coefficients of the two nonzero integers ‘a` and `b` using the extended Euclidean algorithm.

Examples:

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]

Parameters:

  • a (Integer) —

    a nonzero integer

  • b (Integer) —

    a nonzero integer

Returns:

  • (Array(Integer, Integer)) —

    the Bezout coefficients ‘x` and `y`

Raises:

  • (ZeroDivisionError) —

    if ‘a` or `b` is zero

See Also:



142
143
144
145
146
147
148
149
 
# File 'lib/rsa/math.rb', line 142

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

.factorize(n) {|p, e| ... } ⇒ Enumerator

Yields the prime factorization of the nonzero integer ‘n`.

Examples:

RSA::Math.factorize(12).to_a                   #=> [[2, 2], [3, 1]]

Parameters:

  • n (Integer) —

    a nonzero integer

Yields:

  • (p, e) —

    each prime factor

Yield Parameters:

  • p (Integer) —

    the prime factor base

  • e (Integer) —

    the prime factor exponent

Returns:

  • (Enumerator)

Raises:

  • (ZeroDivisionError) —

    if ‘n` is zero

See Also:



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/rsa/math.rb', line 48

def self.factorize(n, &block)
  raise ZeroDivisionError if n.zero?
  if block_given?
    n = n.abs if n < 0
    primes.find do |p|
      e = 0
      while (q, r = n.divmod(p); r.zero?)
        n, e = q, e + 1
      end
      yield p, e unless e.zero?
      n <= p
    end
    yield n, 1 if n > 1
  end
  enum_for(:factorize, n)
end

.gcd(a, b) ⇒ Integer

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.

Examples:

RSA::Math.gcd(3, 5)                            #=> 1
RSA::Math.gcd(8, 12)                           #=> 4
RSA::Math.gcd(12, 60)                          #=> 12
RSA::Math.gcd(90, 12)                          #=> 6

Parameters:

  • a (Integer) —

    an integer

  • b (Integer) —

    an integer

Returns:

  • (Integer) —

    the greatest common divisor of ‘a` and `b`

See Also:



121
122
123
 
# File 'lib/rsa/math.rb', line 121

def self.gcd(a, b)
  a.gcd(b)
end

.log(n, b = nil) ⇒ Float

Returns the natural logarithm of ‘n`. If the optional argument `b` is given, it will be used as the base of the logarithm.

Examples:

RSA::Math.log(16, 2)                           #=> 4.0
RSA::Math.log(16, 256)                         #=> 0.5

Parameters:

  • n (Integer) —

    a positive integer

  • b (Integer) (defaults to: nil) —

    a positive integer >= 2, or ‘nil`

Returns:

  • (Float) —

    the logarithm

Raises:

  • (Errno::EDOM) —

    if ‘n` < 1, or if `b` < 2

See Also:



272
273
274
 
# File 'lib/rsa/math.rb', line 272

def self.log(n, b = nil)
  b ? ::Math.log(n, b) : ::Math.log(n)
end

.log2(n) ⇒ Float

Returns the binary logarithm of ‘n`.

Examples:

RSA::Math.log2(16)                             #=> 4.0
RSA::Math.log2(1024)                           #=> 10.0

Parameters:

  • n (Integer) —

    a positive integer

Returns:

  • (Float) —

    the logarithm

Raises:

  • (Errno::EDOM) —

    if ‘n` < 1

See Also:



240
241
242
 
# File 'lib/rsa/math.rb', line 240

def self.log2(n)
  ::Math.log2(n)
end

.log256(n) ⇒ Float

Returns the base-256 logarithm of ‘n`.

Examples:

RSA::Math.log256(16)                           #=> 0.5
RSA::Math.log256(1024)                         #=> 1.25

Parameters:

  • n (Integer) —

    a positive integer

Returns:

  • (Float) —

    the logarithm

Raises:

  • (Errno::EDOM) —

    if ‘n` < 1

See Also:



255
256
257
 
# File 'lib/rsa/math.rb', line 255

def self.log256(n)
  ::Math.log(n, 256)
end

.modinv(b, m) ⇒ Integer

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

Examples:

RSA::Math.modinv(3, 11)                        #=> 4
RSA::Math.modinv(6, 35)                        #=> 6
RSA::Math.modinv(-6, 35)                       #=> 29
RSA::Math.modinv(6, 36)                        #=> ArithmeticError

Parameters:

  • b (Integer)
  • m (Integer) —

    the modulus

Returns:

  • (Integer) —

    the modular multiplicative inverse

Raises:

See Also:



170
171
172
173
174
175
176
177
 
# File 'lib/rsa/math.rb', line 170

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

.modpow(base, exponent, modulus) ⇒ Integer

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

Examples:

RSA::Math.modpow(5, 3, 13)                     #=> 8
RSA::Math.modpow(4, 13, 497)                   #=> 445

Parameters:

  • base (Integer) —

    the base

  • exponent (Integer) —

    the exponent

  • modulus (Integer) —

    the modulus

Returns:

  • (Integer) —

    the result

See Also:



197
198
199
200
201
202
203
204
205
 
# File 'lib/rsa/math.rb', line 197

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

.phi(n) ⇒ Integer

Returns the Euler totient for the positive integer ‘n`.

Examples:

(1..5).map { |n| RSA::Math.phi(n) }            #=> [1, 1, 2, 2, 4]

Parameters:

  • n (Integer) —

    a positive integer, or zero

Returns:

  • (Integer) —

    the Euler totient of ‘n`

Raises:

  • (ArgumentError) —

    if ‘n` < 0

See Also:



220
221
222
223
224
225
226
227
 
# File 'lib/rsa/math.rb', line 220

def self.phi(n)
  case
    when n < 0     then raise ArgumentError, "expected a positive integer, but got #{n}"
    when n < 2     then 1 # by convention
    when prime?(n) then n - 1
    else factorize(n).inject(n) { |product, (p, e)| product * (ONE - (ONE / BigDecimal(p.to_s))) }.round.to_i
  end
end

.prime?(n) ⇒ Boolean

Performs a primality test on the integer ‘n`, returning `true` if it is a prime.

Examples:

1.upto(10).select { |n| RSA::Math.prime?(n) }  #=> [2, 3, 5, 7]

Parameters:

  • n (Integer) —

    an integer

Returns:

  • (Boolean) —

    ‘true` if `n` is a prime number, `false` otherwise

See Also:



76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/rsa/math.rb', line 76

def self.prime?(n)
  case
    when n < 0 then prime?(n.abs)
    when n < 2 then false
    else primes do |p|
      q, r = n.divmod(p)
      return true  if q < p
      return false if r.zero?
    end
  end
end

.primes {|p| ... } ⇒ Enumerator

Yields an infinite pseudo-prime number sequence.

This is a pseudo-prime generator that simply yields the initial values 2 and 3, followed by all positive integers that are not divisible by 2 or 3.

It works identically to ‘Prime::Generator23`, the Ruby 1.9 standard library’s default pseudo-prime generator implementation.

Examples:

RSA::Math.primes.take(5)                       #=> [2, 3, 5, 7, 11]

Yields:

  • (p) —

    each pseudo-prime number

Yield Parameters:

  • p (Integer) —

    a pseudo-prime number

Returns:

  • (Enumerator) —

    yielding pseudo-primes

See Also:



26
27
28
29
30
31
32
33
 
# File 'lib/rsa/math.rb', line 26

def self.primes(&block)
  if block_given?
    yield 2; yield 3; yield 5
    prime, step = 5, 4
    loop { yield prime += (step = 6 - step) }
  end
  enum_for(:primes)
end