module Crypto::Math

Extended Modules

Defined in:

crypto/utils/math.cr

Class Method Summary

Class Method Detail

def self.abs(a) #

[View source]
def self.egcd(a, b) #

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]

[View source]
def self.factorize(pq) #

[View source]
def self.gcd(a, b) #

[View source]
def self.log256(n) #

Returns the base-256 logarithm of n.

Example

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

[View source]
def self.mod_inverse(e, phi) #

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


[View source]
def self.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).

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

[View source]
def self.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).

Example

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

[View source]
def self.phi(n) #

Returns the Euler totient for the positive integer n.

Example

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

[View source]