------art_18378_3682514.1195440278316
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Hello,

Here is my solution. First, I used a pre-computed array of the first 256
primes. I did this to streamline things and because after a certain number
of input characters it becomes more practical to break the input into chunks
and start at 2 again:

  # Use first 256 prime numbers from
http://en.wikipedia.org/wiki/List_of_prime_numbers
  Primes = [2, 3, 5, 7 ... 1619]

The following function then encrypts text by using ASCII code + 1 as the
power, per the quiz statement. Spaces are encoded as 0 to slightly reduce
overall processing.

  def GoedelCipher.encrypt(plain_text)
    ascii = plain_text.split("").map{|c| c[0]}

    msg = 1
    for i in 0...ascii.size
      pwr = ascii[i] == ' ' ? 0 : (ascii[i] + 1)
      msg *= Primes[i] ** pwr
    end

    msg
  end

This function converts back to the original plaintext by factoring out each
prime number (2, 3, etc) in turn:

  def GoedelCipher.decrypt(msg)
    # decoding: see
http://www.math.ksu.edu/~dph/010_readings/Unit1Lesson1.html
    # for an intro to factoring prime numbers.
    # eg: 60=2x3x2x5, so could div 60 by 2 until result%2 != 0
    plain_text = ""

    i = 0
    while msg > 1

      letter_count = 0
      while msg % Primes[i] == 0
        letter_count += 1
        msg /= Primes[i]
      end

      plain_text += letter_count == 0 ? ' ' : (letter_count - 1).chr
      i += 1 # Move to next prime
    end

    plain_text
  end

Fortunately, ruby will automatically cast very large integers to BigNum, so
the code does not have to worry about *huge* numbers. The previous 2
functions only work on input that is 256 characters long or less, since only
256 primes are defined in the initial array. To work with larger inputs, the
following functions are provided to break the input up into smaller chunks
(blocks):

  def GoedelCipher.large_encrypt(plain_text, block_size = Primes.size)
    blocks = []
    for i in 0..(plain_text.size / block_size)
      blocks << encrypt(plain_text[i * block_size, block_size])
    end
    blocks
  end

  def GoedelCipher.large_decrypt(msg)
    msg.map{|block| decrypt(block)}.join
  end

This code is then used to kick-off the encryption / decryption:

if ARGV.size != 1
  puts "Usage: goedel_cmb.rb message_text"
else
  msg = GoedelCipher.large_encrypt(ARGV[0])
  puts "Encrypted Message: #{msg}"

  plaintext = GoedelCipher.large_decrypt(msg)
  puts "Decrypted Message: #{plaintext}"
end

Here are pasties of everything:
 Goedel Module: http://pastie.caboo.se/119595
 Command Line Program: http://pastie.caboo.se/119598
 Benchmark: http://pastie.caboo.se/119597

Thanks,

Justin


On Nov 16, 2007 2:43 PM, Ruby Quiz <james / grayproductions.net> wrote:

> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this quiz
> until
> 48 hours have passed from the time on this message.
>
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3.  Enjoy!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps
> everyone
> on Ruby Talk follow the discussion.  Please reply to the original quiz
> message,
> if you can.
>
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> by Hugh Sasse
>
> In the book "Starburst" by Frederik Pohl ISBN 0-345-27537-3, page 56,
> without
> really spoiling the plot, some characters complain about the verbosity of
> communications and encode a message by Göäelizing it (detailed on page
> 58).
>
> The encoding works by taking each successive character of a message and
> raising
> each successive prime to some function of that character, and multiplying
> these
> powers of primes together. So for example we could use the ASCII code + 1
> to
> allow for nulls to be encoded. Then "Ruby\r\n" would end up as:
>
>        (2 ** R) * (3 ** u) * (5 ** b)....
>
>        10992805522291106558517740012022207329045811217010725353610920778
>        28664749233402453985379760678149866991742205982820039955872246774
>        86029159248495553882158351479922840433375701904296875000000000000
>        00000000000000000000000000000000000000000000000000000000000000000
>        000000
>
> The idea is partly to obscure the message by the amount of factorization
> needed.
> This quiz is to write a program to Göäelize a message, and a program to
> deGöäelize it.
>
> The funtion used to map characters described in the book is "A" => 1, "B"
> => 2,
> etc and an example is given where spaces are 0. Nothing further is said
> about
> punctuation, or lower case. The message sent in the book is:
>
>        msg = (3.875 * (12 ** 26)) +
>             (1973 ** 854) + (331 ** 852) +
>             (17 ** 2008) + (3 ** 9707) + (2 ** 88) - 78
>
> which it turns out has lots of 0 powers in it, so I strictly don't need
> the
> ASCII + 1 I've used in my example, I could use just ASCII, and the nulls
> would
> not increase the size of the resulting number. This further means that if
> a list
> of characters is sent in decreasing frequency order with the message, the
> most
> frequent could be encoded as 0 and the number would be that much smaller.
> In
> English it is likely to be an "e" or " " which ends up coded as 0.
>
> Interesting things arising from this:
>
>        1 Finding the power once a prime is selected
>        2 Getting the list of primes in the first place
>        3 encoding of characters, as mentioned above
>        4 representing the number that results from encoding.
>
>

------art_18378_3682514.1195440278316--