From: Justin Ethier <justin.ethier@...>
Date: 2007-11-19T11:44:38+09:00
Subject: Re: [QUIZ] Goedel (#147)

------=_Part_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 chunk=
s
and start at 2 again:

  # Use first 256 prime numbers from
http://en.wikipedia.org/wiki/List_of_prime_numbers
  Primes =3D [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 =3D plain_text.split("").map{|c| c[0]}

    msg =3D 1
    for i in 0...ascii.size
      pwr =3D ascii[i] =3D=3D ' ' ? 0 : (ascii[i] + 1)
      msg *=3D 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=3D2x3x2x5, so could div 60 by 2 until result%2 !=3D 0
    plain_text =3D ""

    i =3D 0
    while msg > 1

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

      plain_text +=3D letter_count =3D=3D 0 ? ' ' : (letter_count - 1).chr
      i +=3D 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 onl=
y
256 primes are defined in the initial array. To work with larger inputs, th=
e
following functions are provided to break the input up into smaller chunks
(blocks):

  def GoedelCipher.large_encrypt(plain_text, block_size =3D Primes.size)
    blocks =3D []
    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 !=3D 1
  puts "Usage: goedel_cmb.rb message_text"
else
  msg =3D GoedelCipher.large_encrypt(ARGV[0])
  puts "Encrypted Message: #{msg}"

  plaintext =3D 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.
>
>
> -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=
=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D
>
> 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=F6delizing 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=F6delize a message, and a program to
> deG=F6delize it.
>
> The funtion used to map characters described in the book is "A" =3D> 1, "=
B"
> =3D> 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 =3D (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.
>
>

------=_Part_18378_3682514.1195440278316--