Module: RSA::Math

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

Overview

Mathematical helper functions for RSA.

Defined Under Namespace

Classes: ArithmeticError

Constant Summary

ONE =
BigDecimal('1')

Class Method Summary (collapse)

Class Method Details

+ (Boolean) coprime?(a, b)

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:

  • (Integer) a

    an integer

  • (Integer) b

    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

+ (Array(Integer, Integer)) egcd(a, b)

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:

  • (Integer) a

    a nonzero integer

  • (Integer) b

    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

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

Yields the prime factorization of the nonzero integer n.

Examples:

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

Parameters:

  • (Integer) n

    a nonzero integer

Yields:

  • (p, e)

    each prime factor

Yield Parameters:

  • (Integer) p

    the prime factor base

  • (Integer) e

    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

+ (Integer) gcd(a, b)

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:

  • (Integer) a

    an integer

  • (Integer) b

    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

+ (Float) log(n, b = nil)

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:

  • (Integer) n

    a positive integer

  • (Integer) b (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

+ (Float) log2(n)

Returns the binary logarithm of n.

Examples:

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

Parameters:

  • (Integer) n

    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

+ (Float) log256(n)

Returns the base-256 logarithm of n.

Examples:

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

Parameters:

  • (Integer) n

    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

+ (Integer) modinv(b, m)

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:

  • (Integer) b
  • (Integer) m

    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

+ (Integer) modpow(base, exponent, modulus)

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:

  • (Integer) base

    the base

  • (Integer) exponent

    the exponent

  • (Integer) modulus

    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

+ (Integer) phi(n)

Returns the Euler totient for the positive integer n.

Examples:

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

Parameters:

  • (Integer) n

    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

+ (Boolean) prime?(n)

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:

  • (Integer) n

    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

+ (Enumerator) primes {|p| ... }

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:

  • (Integer) p

    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