Module: HenselCode::Tools

Included in:
GAdicBase, PAdicBase, Polynomial
Defined in:
lib/hensel_code/tools.rb

Overview

Required basics of number generation and modular

Instance Method Summary collapse

Instance Method Details

#crt(moduli, remainders) ⇒ Object 



81
82
83
84
85
86
87
88
89
90
 
# File 'lib/hensel_code/tools.rb', line 81

def crt(moduli, remainders)
  g = moduli.inject(:*)
  result = 0
  moduli.zip(remainders) do |modulus, remainder|
    g_prime = g / modulus
    g_prime_inverse = mod_inverse(g_prime, modulus)
    result += ((g_prime * g_prime_inverse * remainder))
  end
  result % g
end

#eea_core(num1, num2, bound = 0) ⇒ Object 



48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/hensel_code/tools.rb', line 48

def eea_core(num1, num2, bound = 0)
  setup = bound.zero? ? [1, 0] : [0, 1]
  x0, x1, y0, y1 = [num1, num2] + setup
  i = 1
  while x1 > bound
    q = x0 / x1
    x0, x1 = x1, x0 - (q * x1)
    y0, y1 = y1, y0 - (q * y1)
    i += 1
  end
  [x0, y0, i, x1, y1]
end

#extended_gcd(num1, num2) ⇒ Object 



61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/hensel_code/tools.rb', line 61

def extended_gcd(num1, num2)
  if num1.negative?
    x, y = extended_gcd(-num1, num2)
    [x, -y]
  elsif num2.negative?
    x, y = extended_gcd(num1, -num2)
    [x, y]
  else
    x, y = eea_core(num1, num2)
    [x, y]
  end
end

#mod_inverse(num, mod) ⇒ Object

Raises:

  • (ZeroDivisionError) 


74
75
76
77
78
79
 
# File 'lib/hensel_code/tools.rb', line 74

def mod_inverse(num, mod)
  x, y, = extended_gcd(num, mod)
  raise ZeroDivisionError, "#{num} has no inverse modulo #{mod}" unless x == 1

  y % mod
end

#random_distinct_numbers(type, quantity, bits) ⇒ Object 



39
40
41
42
43
44
45
46
 
# File 'lib/hensel_code/tools.rb', line 39

def random_distinct_numbers(type, quantity, bits)
  numbers = [send("random_#{type}", bits)]
  while numbers.size < quantity
    number = send("random_#{type}", bits)
    numbers << number unless numbers.include?(number)
  end
  numbers
end

#random_integer(bits) ⇒ Object 



6
7
8
 
# File 'lib/hensel_code/tools.rb', line 6

def random_integer(bits)
  OpenSSL::BN.rand(bits).to_i
end

#random_prime(bits) ⇒ Object 



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/hensel_code/tools.rb', line 19

def random_prime(bits)
  # The OpenSSL library only generates random primes from 16 bits on
  # The 3513 is the first 16-bit number
  # which means there are 3512 primes under 16 bits in length
  # Therefore for allowing values for the parameter 'bits' between 2 and 15,
  # we generate all primes from 2 to 15 bits using Ruby's Prime library
  # and select only those with bit length equal to the value of 'bits'
  # so we sample one element
  # We only do this if the value of 'bits' is less than 16, otherwise we
  # use OpenSSL to generate the prime
  if bits >= 2 && bits < 16
    primes = Prime.first(3512)
    primes.select { |p| p.bit_length == bits }.sample
  elsif bits >= 16
    OpenSSL::BN.generate_prime(bits).to_i
  else
    raise BadBitRangeForRandomPrime, "The bit length must be greater than or equal to 2"
  end
end

#random_rational(bits) ⇒ Object 



10
11
12
13
14
15
16
17
 
# File 'lib/hensel_code/tools.rb', line 10

def random_rational(bits)
  numbers = [random_integer(bits)]
  while numbers.size < 2
    num = random_integer(bits)
    numbers << num if numbers.last.gcd(num) == 1
  end
  Rational(*numbers)
end