Module: Obfuskey::Math

Defined in:
lib/obfuskey/math.rb

Class Method Summary collapse

Class Method Details

.extended_gcd(a, b) ⇒ Object 



85
86
87
88
89
 
# File 'lib/obfuskey/math.rb', line 85

def extended_gcd(a, b)
  return [a, 1, 0] if b.zero?
  g, x1, y1 = extended_gcd(b, a % b)
  [g, y1, x1 - (a / b) * y1]
end

.factor(n) ⇒ Object 



5
6
7
8
9
10
11
12
13
 
# File 'lib/obfuskey/math.rb', line 5

def factor(n)
  s = 0
  d = n - 1
  while d.even?
    s += 1
    d /= 2
  end
  [s, d]
end

.mod_inv(base, mod) ⇒ Object

Raises:

  • (ArgumentError) 


79
80
81
82
83
 
# File 'lib/obfuskey/math.rb', line 79

def mod_inv(base, mod)
  g, x, _ = extended_gcd(base % mod, mod)
  raise ArgumentError, "base and mod are not coprime" unless g == 1
  x % mod
end

.next_prime(n) ⇒ Object 



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/obfuskey/math.rb', line 59

def next_prime(n)
  if n.bit_length > 512
    raise MaximumValueError,
      "For integers larger than 512-bit, a more advanced prime generator is required."
  end

  return 2 if n < 2
  return [3, 5, 5][n - 2] if n < 5

  gap = [
    1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3,
    2, 1, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 2
  ]

  n += 1 + (n & 1)
  n += gap[n % 30] if (n % 3).zero? || (n % 5).zero?
  n += gap[n % 30] until prime?(n)
  n
end

.prime?(n) ⇒ Boolean

Returns:

  • (Boolean) 


50
51
52
53
54
55
56
57
 
# File 'lib/obfuskey/math.rb', line 50

def prime?(n)
  return true if n == 2
  return false if n < 2 || n.even?
  return [3, 5, 7, 11, 13, 17].include?(n) if n.gcd(510_510) > 1
  return trial_division(n) if n < 2_000_000

  small_strong_pseudoprime(n)
end

.small_strong_pseudoprime(n) ⇒ Object 



46
47
48
 
# File 'lib/obfuskey/math.rb', line 46

def small_strong_pseudoprime(n)
  [2, 13, 23, 1_662_803].all? { |base| strong_pseudoprime(n, base) }
end

.strong_pseudoprime(n, base = 2) ⇒ Object 



29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/obfuskey/math.rb', line 29

def strong_pseudoprime(n, base = 2)
  return false if n.even?
  return false if n == 1

  s, d = factor(n)
  x = base.pow(d, n)
  return true if x == 1 || x == n - 1

  (s - 1).times do
    x = x.pow(2, n)
    return true if x == n - 1
    return false if x == 1
  end

  false
end

.trial_division(n) ⇒ Object 



15
16
17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/obfuskey/math.rb', line 15

def trial_division(n)
  return false if n <= 1
  return true if n == 2
  return false if n.even?

  i = 3
  limit = Integer.sqrt(n)
  while i <= limit
    return false if (n % i).zero?
    i += 2
  end
  true
end