Crypto::Math

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

Example

Crypto::Math.egcd(120, 23)    # => [-9, 47]
Crypto::Math.egcd(421, 111)   # => [-29, 110]
Crypto::Math.egcd(93, 219)    # => [33, -14]
Crypto::Math.egcd(4864, 3458) # => [32, -45]

Returns the base-256 logarithm of n.

Example

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

Euclid's extended algorithm for finding the multiplicative inverse of two numbers

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

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

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

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

Returns the Euler totient for the positive integer n.

Example

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