README.md

CSCI 466 Project 4

Benjamin Manns

Part 1

• Number of Components: 5
• Average tail length: 105
• Maximum tail length: 257
• Minimum cycle length: 4
• Average cycle length: 69
• Maximum cycle length: 242

Part 2

See new_hash in crypto_md5.rb.

Because new_hash uses a Linear congruential generator that satisfies the three period length conditions, it has a period of M which is 65536.

crypto_md5.rb

require 'digest/md5'

class TarjanGraph
  attr_accessor :graph
  attr_accessor :result
  attr_accessor :stack
  attr_accessor :low
  attr_accessor :inverse

  def initialize graph
    self.graph = graph
    self.result = []
    self.stack = []
    self.low = {}
    self.inverse = {}
    graph.each_with_index do |value, key|
      if inverse[value]
        if inverse[value].is_a? Array
          inverse[value] << key
        else
          inverse[value] = [inverse[value], key]
        end
      else
        inverse[value] = key
      end
    end
  end

  def tarjan
    graph.length.times { |node| visit node }
    return self.result
  end

  def visit node
    return if self.low.include? node
    edge = graph[node]
    low[node] = low.length
    stack_position = stack.length
    stack << node
    visit edge
    if low[edge] < low[node]
      low[node] = low[edge]
    else
      component = stack.slice! stack_position..-1
      self.result << component
      component.each { |item| low[item] = graph.length }
    end
  end

  def tails
    cyclicals = self.tarjan.select { |cycle| cycle.length > 1 }.flatten
    tail_starts = (0..65535).to_a - self.inverse.keys
    tail_starts.map do |tail_start|
      tail = [tail_start]
      until cyclicals.include? self.graph[tail.last]
        tail << self.graph[tail.last]
      end
      tail
    end
  end
end

graph = 65536.times.map { |i| Digest::MD5.digest([i].pack('n')).unpack('@14n').first }
tarjan_graph = TarjanGraph.new(graph)

cycles = tarjan_graph.tarjan.select { |cycle| cycle.length > 1 }
cycle_lengths = cycles.map(&:length)

tails = tarjan_graph.tails
tail_lengths = tails.map(&:length)

puts "Part 1"
puts "Number of Components: #{cycles.length}"
puts "Average tail length: #{tail_lengths.inject(&:+) / tails.length}"
puts "Maximum tail length: #{tail_lengths.max}"
puts "Minimum cycle length: #{cycle_lengths.min}"
puts "Average cycle length: #{cycle_lengths.inject(&:+) / cycles.length}"
puts "Maximum cycle length: #{cycle_lengths.max}"

# I'm not exactly sure how we're supposed to do this.
# I'm going to use a LCG to generate a unique and semi-random mapping from (0..65535) -> (0..65535).
#
# Linear Congruential Generator
#
# For a LCG to have a full period of M, it must satisfy the following conditions:
# 1. C and M are relatively prime
# 2. A - 1 is divisible by prime factors of M
# 3. A - 1 is a multiple of 4 if M is a multiple of 4
#
# Since we're modulo 2**16, let M = 65536.
M = 65536
# Pick random prime for C to satisfy (1).
C = 21437
# A - 1 must be divisible by 2 and by 4 to satisfy (2) and (3).
A = 12345
def new_hash x
  (A * x + C) % M
end