# From: http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

class Integer
   def prime?
     n = self.abs()
     return true if n == 2
     return false if n == 1 || n & 1 == 0

     # cf. http://betterexplained.com/articles/another-look-at-prime-numbers/ and
     # http://everything2.com/index.pl?node_id=1176369

     return false if n > 3 && n % 6 != 1 && n % 6 != 5     # added

     d = n-1
     d >>= 1 while d & 1 == 0
     20.times do                               # 20 = k from above
       a = rand(n-2) + 1
       t = d
       y = ModMath.pow(a,t,n)                  # implemented below
       while t != n-1 && y != 1 && y != n-1
         y = (y * y) % n
         t <<= 1
       end
       return false if y != n-1 && t & 1 == 0
     end
     return true
   end
end
 
module ModMath
   def ModMath.pow(base, power, mod)
     result = 1
     while power > 0
       result = (result * base) % mod if power & 1 == 1
       base = (base * base) % mod
       power >>= 1;
     end
     result
   end
end


#------------------------------------------------------------------


# From: http://www.h2np.net/tips/ruby-cipher-math.txt
# Author: Hironobu SUZUKI

# $Id: mathh.rb,v 1.5 2002/11/24 16:15:56 hironobu Exp $
# Simple Secure Stream Cryptography
# Mathematical Library
# Hironobu SUZUKI <hironobu@h2np.net>
# LGPL, (C) 2002, Hironobu SUZUKI

class Random  
  def initialize()
    @random_device="/dev/urandom"
    @verbose=false
  end
  def random_device=(str)
    @random_device=str
  end
  def verbose
    @verbose=true
  end
  def get(size)
    if (@verbose) ;STDERR.print "+";end
    value=0
    r=File.open(@random_device)
    r.read(size).each_byte {|c|
      value = (value << 8) + c.to_i
    }
    r.close
    return value
    
  end
  def get_prime(lower,higher)
    bytesize = higher.bytesize
    while true
      r = self.get(bytesize)
      if (r % 2 == 0) ; r -= 1 ;   end
      if ( lower <=  r && r <= higher && r.prime? == true )
	return r
      end
    end
  end
end


class Integer
  def cdiv(d)			# ceil divide
    w=self.divmod(d)
    if w[1] > 0 ;  w[0] +=1 ; end
    return w[0]
  end
  def powm(i,n)	# square-and-multiply for exp modulo n
    if ( i == 0 )
      return 1
    end
    b=1
    a=self

    if ( (i & 1) == 1 )
      b=a
    end
    i = i>>1

    while ( i > 0 )
      a = (a * a) % n
      if ( (i & 1) == 1 )
	b = (a * b) % n 
      end
      i = i>>1
    end
    return b
  end
  def gcd(b)			# GCD
    a = self
    if ( a < b ); t=b; b=a; a=t; end
    while b > 0 
      r = a % b 
      a = b
      b = r
    end
    return a
  end
  def invert(n)  # Extension Euclid Algorithm
    a = n        # See Knuth's The Art of Computer Programming 
    b = self % n # Vol2 pp.342 -- 343  
    p = 0 ; q = 1;  v = 0;  u = 1;
    while q > 0 
      p = a / b
      q =  a % b
      w = v - (p*u)
      ## DEBUG    printf "%d = %d(%d) + %d  (%d)\n", a,p,b,q,v ###
      a = b
      b = q
      v = u
      u = w
    end
    return (v+n) % n
  end

# Miller-Rabin Test  (Prime Test)
# See, http://www.cs.albany.edu/~berg/csi445/Assignments/pa4.html
  def bitarray(n) 
    b=Array::new  
    i=0       
    v=n
    while v > 0
      b[i] = (0x1 & v)
      v = v/2
      i = i + 1
    end
    return b
  end
  def miller_rabin(n,s)
    b=bitarray(n-1)
    i=b.size 
    j =1
    while j <= s
      a = 1 + (rand(n-2).to_i)
      if witness(a,n,i,b) == true
	return false
      end
      j+=1
    end
    return true
  end
  def witness(a,n,i,b)
    d=1
    x=0
    while i > 0 
      x = d 
      d = (d**2) % n
      if ( (d == 1) && (x != 1) && (x != (n-1)) )
	return true
      end
      if ( b[i-1] == 1 )
	d = (d * a ) % n
      end
      i -= 1
    end
    if ( d != 1) 
      return true
    end
    return false
  end

  #def prime?
  def is_prime?
    a = self
    return miller_rabin(a,30)    
  end

  def bytesize
    n = self
    i=0
    while n > 0
      n = n >> 8
      i += 1
    end
    return i
  end
  def bitsize
    n = self
    i=0
    while n > 0
      n = n >> 1
      i += 1
    end
    return i
  end
end


p 107565456790871.prime?      # true
p 107565456790871.is_prime?   # true

a = 107565456790871

begin
  a += 2
end while !a.prime? && !a.is_prime?

puts a   #=> 107565456790991 (next prime)

CharExponent = 3
BitsPerChar = 1 << CharExponent
LowMask = BitsPerChar - 1

def sieve(m)
  ret = []
  items = "\xFF" * ((m / BitsPerChar) + 1)
  masks = ""
  BitsPerChar.times do |b|
    masks << (1 << b).chr
  end

  count = 0
  pmax = m - 1
  2.step(pmax, 1) do |p|
    if items[p >> CharExponent][p & LowMask] == 1
      ret << p
      count += 1
      p.step(pmax, p) do |mult|
	a = mult >> CharExponent
	b = mult & LowMask
	items[a] -= masks[b] if items[a][b] != 0
        #p items
      end
    end
  end
  #count
  ret
end

n = (ARGV[0] || 2).to_i
n.step(n - 2, -1) do |exponent|
  break if exponent < 0
  m = 2 ** exponent * 10_000
  primes = sieve(m)
  count = primes.size
  puts
  printf "Primes up to %8d %8d\n", m, count
  puts "last ten primes: #{primes[-10..-1].join(' ')}"
  puts
end

class Integer
    # Compute self ^ e mod m
    def mod_exp e, m
        result = 1
        b = self
        while e > 0
            result = (result * b) % m if e[0] == 1
            e = e >> 1
            b = (b * b) % m
        end
        return result
    end

    # A roundabout, slow but fun way of counting bits.
    def bits_set
        ("%b" % self).count('1')
        #to_s(2).count('1')   # alternative
        #count = 0         # alternative
        #byte = self.abs
        #count += byte & 1 and byte >>= 1 until byte == 0     # cf. http://snippets.dzone.com/posts/show/4233
        #count
    end
end


class DH
    attr_reader :p, :g, :q, :x, :e

    # p is the prime, g the generator and q order of the subgroup
    def initialize p, g, q
        @p = p
        @g = g
        @q = q
    end

    # generate the [secret] random value and the public key
    def generate tries=16
        tries.times do
            @x = rand(@q)
            @e = self.g.mod_exp(@x, self.p)
            return @e if self.valid?
        end
        raise ArgumentError, "can't generate valid e"
    end

    # validate a public key
    def valid? _e = self.e
        _e and _e.between?(2, self.p-2) and _e.bits_set > 1
    end

    # compute the shared secret, given the public key
    def secret f
        f.mod_exp(self.x, self.p)
    end
end

alice = DH.new(53, 5, 23)
bob   = DH.new(53, 5, 15)
alice.generate
bob.generate

alice_s = alice.secret(bob.e)
bob_s   = bob.secret(alice.e)
puts alice_s
puts bob_s

#!/usr/local/bin/ruby -Ku

# NOTE: The following is not the complete source code by Kazuhiro NISHIYAMA.
#       For the full source code with more features, comments & test cases please see: 
#       open -e `gem environment gemdir`/gems/punycode4r-0.2.0/lib/punycode.rb
#
# This is pure Ruby implementing Punycode (RFC 3492).
# (original ANSI C code (C89) implementing Punycode is in RFC 3492)
#
# copyright (c) 2005 Kazuhiro NISHIYAMA
# You can redistribute it and/or modify it under the same terms as Ruby.


require "unicode"     # sudo gem install unicode

module Punycode

  module Status
    class Error < StandardError; end
    class PunycodeSuccess; end
    # Input is invalid.
    class PunycodeBadInput < Error; end
    # Output would exceed the space provided.
    class PunycodeBigOutput< Error; end
    # Input needs wider integers to process.
    class PunycodeOverflow < Error; end
  end
  include Status


  BASE = 36; TMIN = 1; TMAX = 26; SKEW = 38; DAMP = 700
  INITIAL_BIAS = 72; INITIAL_N = 0x80; DELIMITER = 0x2D

  module_function

  def basic(cp)
    cp < 0x80
  end

  def delim(cp)
    cp == DELIMITER
  end

  def decode_digit(cp)
    cp - 48 < 10 ? cp - 22 :  cp - 65 < 26 ? cp - 65 :
      cp - 97 < 26 ? cp - 97 : BASE
  end

  def encode_digit(d, flag)
    return d + 22 + 75 * ((d < 26) ? 1 : 0) - ((flag ? 1 : 0) << 5)
  end

  def flagged(bcp)
    (0...26) === (bcp - 65)
  end

  def encode_basic(bcp, flag)
    # bcp -= (bcp - 97 < 26) << 5;
    if (0...26) === (bcp - 97)
      bcp -= 1 << 5
    end
    # return bcp + ((!flag && (bcp - 65 < 26)) << 5);
    if !flag and (0...26) === (bcp - 65)
      bcp += 1 << 5
    end
    bcp
  end

  MAXINT = 1 << 64


  def adapt(delta, numpoints, firsttime)
    delta = firsttime ? delta / DAMP : delta >> 1
    delta += delta / numpoints

    k = 0
    while delta > ((BASE - TMIN) * TMAX) / 2
      delta /= BASE - TMIN
      k += BASE
    end

    k + (BASE - TMIN + 1) * delta / (delta + SKEW)
  end

  def punycode_encode(input_length, input, case_flags, output_length, output)

    n = INITIAL_N
    delta = out = 0
    max_out = output_length[0]
    bias = INITIAL_BIAS

    input_length.times do |j|
      if basic(input[j])
        raise PunycodeBigOutput if max_out - out < 2
        output[out] =
          if case_flags
            encode_basic(input[j], case_flags[j])
          else
            input[j]
          end
        out+=1
      # elsif (input[j] < n)
      #   raise PunycodeBadInput
      # (not needed for Punycode with unsigned code points)
      end
    end

    h = b = out

    if b > 0
      output[out] = DELIMITER
      out+=1
    end

   while h < input_length

      m = MAXINT
      input_length.times do |j|
        # next if basic(input[j])
        # (not needed for Punycode)
        m = input[j] if (n...m) === input[j]
      end

      raise PunycodeOverflow if m - n > (MAXINT - delta) / (h + 1)
      delta += (m - n) * (h + 1)
      n = m

      input_length.times do |j|
        # Punycode does not need to check whether input[j] is basic:
        if input[j] < n # || basic(input[j])
          delta+=1
          raise PunycodeOverflow if delta == 0
        end

        if input[j] == n

          q = delta; k = BASE
          while true
            raise PunycodeBigOutput if out >= max_out
            t = if k <= bias # + TMIN # +TMIN not needed
                  TMIN
                elsif k >= bias + TMAX
                  TMAX
                else
                  k - bias
                end
            break if q < t
            output[out] = encode_digit(t + (q - t) % (BASE - t), false)
            out+=1
            q = (q - t) / (BASE - t)
            k += BASE
          end

          output[out] = encode_digit(q, case_flags && case_flags[j])
          out+=1
          bias = adapt(delta, h + 1, h == b)
          delta = 0
          h+=1
        end
      end

      delta+=1; n+=1
    end

    output_length[0] = out
    return PunycodeSuccess
  end

  def punycode_decode(input_length, input, output_length, output, case_flags)

    n = INITIAL_N

    out = i = 0
    max_out = output_length[0]
    bias = INITIAL_BIAS

    b = 0
    input_length.times do |j|
      b = j if delim(input[j])
    end
    raise PunycodeBigOutput if b > max_out

    b.times do |j|
      case_flags[out] = flagged(input[j]) if case_flags
      raise PunycodeBadInput unless basic(input[j])
      output[out] = input[j]
      out+=1
    end

    in_ = b > 0 ? b + 1 : 0
    while in_ < input_length

      oldi = i; w = 1; k = BASE
      while true
        raise PunycodeBadInput if in_ >= input_length
        digit = decode_digit(input[in_])
        in_+=1
        raise PunycodeBadInput if digit >= BASE
        raise PunycodeOverflow if digit > (MAXINT - i) / w
        i += digit * w
        t = if k <= bias # + TMIN # +TMIN not needed
              TMIN
            elsif k >= bias + TMAX
              TMAX
            else
              k - bias
            end
        break if digit < t
        raise PunycodeOverflow if w > MAXINT / (BASE - t)
        w *= BASE - t
        k += BASE
      end

      bias = adapt(i - oldi, out + 1, oldi == 0)

      raise PunycodeOverflow if i / (out + 1) > MAXINT - n
      n += i / (out + 1)
      i %= out + 1

      # not needed for Punycode:
      # raise PUNYCODE_INVALID_INPUT if decode_digit(n) <= base
      raise PunycodeBigOutput if out >= max_out

      if case_flags
        #memmove(case_flags + i + 1, case_flags + i, out - i)
        case_flags[i + 1, out - i] = case_flags[i, out - i]

        # Case of last character determines uppercase flag:
        case_flags[i] = flagged(input[in_ - 1])
      end

      #memmove(output + i + 1, output + i, (out - i) * sizeof *output)
      output[i + 1, out - i] = output[i, out - i]
      output[i] = n
      i+=1

      out+=1
    end

    output_length[0] = out
    return PunycodeSuccess
  end

  def encode(unicode_string, case_flags=nil, print_ascii_only=false)
    input = unicode_string.unpack('U*')
    output = [0] * (ACE_MAX_LENGTH+1)
    output_length = [ACE_MAX_LENGTH]

    punycode_encode(input.size, input, case_flags, output_length, output)

    outlen = output_length[0]
    outlen.times do |j|
      c = output[j]
      unless c >= 0 && c <= 127
        raise Error, "assertion error: invalid output char"
      end
      unless PRINT_ASCII[c]
        raise PunycodeBadInput
      end
      output[j] = PRINT_ASCII[c] if print_ascii_only
    end

    output[0..outlen].map{|x|x.chr}.join('').sub(/\0+\z/, '')
  end

  def decode(punycode, case_flags=[])
    input = []
    output = []

    if ACE_MAX_LENGTH*2 < punycode.size
      raise PunycodeBigOutput
    end
    punycode.each_byte do |c|
      unless c >= 0 && c <= 127
        raise PunycodeBadInput
      end
      input.push(c)
    end

    output_length = [UNICODE_MAX_LENGTH]
    Punycode.punycode_decode(input.length, input, output_length,
                             output, case_flags)
    output.pack('U*')
  end

  UNICODE_MAX_LENGTH = 256
  ACE_MAX_LENGTH = 256

  # The following string is used to convert printable
  # characters between ASCII and the native charset:

  PRINT_ASCII =
    "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n" \
    "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n" \
    " !\"\#$%&'()*+,-./" \
    "0123456789:;<=>?" \
    "@ABCDEFGHIJKLMNO" \
    "PQRSTUVWXYZ[\\]^_" \
    "`abcdefghijklmno" \
    "pqrstuvwxyz{|}~\n"
end



# cf. http://snippets.dzone.com/posts/show/4527

UTF8REGEX = /\A(?:                                                            
              [\x09\x0A\x0D\x20-\x7E]            # ASCII
            | [\xC2-\xDF][\x80-\xBF]             # non-overlong 2-byte
            |  \xE0[\xA0-\xBF][\x80-\xBF]        # excluding overlongs
            | [\xE1-\xEC\xEE\xEF][\x80-\xBF]{2}  # straight 3-byte
            |  \xED[\x80-\x9F][\x80-\xBF]        # excluding surrogates
            |  \xF0[\x90-\xBF][\x80-\xBF]{2}     # planes 1-3
            | [\xF1-\xF3][\x80-\xBF]{3}          # planes 4-15
            |  \xF4[\x80-\x8F][\x80-\xBF]{2}     # plane 16
            )*\z/mnx


UTF8_REGEX_MBYTE = /(?:                                 
                 [\xC2-\xDF][\x80-\xBF]             # non-overlong 2-byte
               |  \xE0[\xA0-\xBF][\x80-\xBF]        # excluding overlongs
               | [\xE1-\xEC\xEE\xEF][\x80-\xBF]{2}  # straight 3-byte
               |  \xED[\x80-\x9F][\x80-\xBF]        # excluding surrogates
               |  \xF0[\x90-\xBF][\x80-\xBF]{2}     # planes 1-3
               | [\xF1-\xF3][\x80-\xBF]{3}          # planes 4-15
               |  \xF4[\x80-\x8F][\x80-\xBF]{2}     # plane 16
               )/mnx



# cf. http://demo.icu-project.org/icu-bin/idnbrowser (samples)
# on Mac OS X you can check the Ruby conversions with the GUI app PunyCode, http://software.dibomedia.de/products/show/2

str = "http://www.ﺱﺲﺷ.com/"
str = "www.сделат картинки.com"
str = "http://www.сделаткартинки.com/"
str = "http://tūdaliņ.lv/"
str = "http://www.zürich.com/"
str = "http://www.hören.at/"
str = "http://www.žlutý kůň.com/"
str = "www.färgbolaget.nu"
str = "www.brændendekærlighed.com"
str = "www.mäkitorppa.com"
str = "www.färjestadsbk.net"
str = "あーるいん.com"
str = "www.예비교사.com"
str = "www.ハンドボールサムズ.com"
str = "www.日本平.jp"
str = "www.räksmörgås.se"
str = "www.różyczka.pl/"
str = "理容ナカムラ.com"
str = "http://Bücher.ch/"
str = "tūdaliņ.lv"


if str =~ UTF8REGEX && str =~ UTF8_REGEX_MBYTE

   s1 = str.gsub(/^(http:\/\/www\.|http:\/\/|).*?\.[^\.\/]+\/?$/n, '\1')
   s2 = str.gsub(/^(?:http:\/\/www\.|http:\/\/|)(www\.|).*?\.[^\.\/]+\/?$/n, '\1')
   s3 = str.gsub(/^(?:http:\/\/www\.|http:\/\/|www\.|)(.*?)\.[^\.\/]+\/?$/n, '\1')
   s4 = str.gsub(/^(?:http:\/\/www\.|http:\/\/|www\.|).*?(\.[^\.\/]+\/?)$/n, '\1')

   if s1.empty? then s1 = 'http://' end

   s3 = Punycode.encode(Unicode::normalize_KC(Unicode::downcase(s3)))

   punycoded_url = s1 << s2 << "xn--" << s3 << s4

   puts punycoded_url

   %x{ /usr/bin/open "#{punycoded_url}" }

end

# This module lazily defines constants of the form Uxxxx for all Unicode
# codepoints from U0000 to U10FFFF. The value of each constant is the
# UTF-8 string for the codepoint.
# Examples:
#   copyright = Unicode::U00A9
#   euro = Unicode::U20AC
#   infinity = Unicode::U221E
#
module Unicode
  def self.const_missing(name)  
    # Check that the constant name is of the right form: U0000 to U10FFFF
    if name.to_s =~ /^U([0-9a-fA-F]{4,5}|10[0-9a-fA-F]{4})$/
      # Convert the codepoint to an immutable UTF-8 string,
      # define a real constant for that value and return the value
      #p name, name.class
      const_set(name, [$1.to_i(16)].pack("U").freeze)
    else  # Raise an error for constants that are not Unicode.
      raise NameError, "Uninitialized constant: Unicode::#{name}"
    end
  end
end


puts copyright = Unicode::U00A9
puts euro = Unicode::U20AC
puts euro = Unicode::U20AC
puts infinity = Unicode::U221E
puts Unicode.const_get(:U221E)
p Unicode.constants
puts Unicode.constants
Unicode.constants.each { |u| puts Unicode.const_get(u) }

require 'socket'

#abort "Usage: server_addr, server_port, cmd_str" unless ARGV.length == 3

UDP_RECV_TIMEOUT = 3  # seconds

def q2cmd(server_addr, server_port, cmd_str)
  resp, sock = nil, nil
  begin
   cmd = "\377\377\377\377#{cmd_str}\0"
    sock = UDPSocket.open
    sock.send(cmd, 0, server_addr, server_port)
    resp = if select([sock], nil, nil, UDP_RECV_TIMEOUT)
      sock.recvfrom(65536)
    end
    if resp
      resp[0] = resp[0][4..-1]  # trim leading 0xffffffff
    end
  rescue IOError, SystemCallError
  ensure
    sock.close if sock
  end
  resp ? resp[0] : nil
end

# your firewall has to allow communication with IP address 67.19.248.74 (port 27912)
#server, port, cmd = *ARGV
server = "tastyspleen.net"
port = 27912
cmd = "status"

result = q2cmd(server, port, cmd)
puts result

function gemdocs() { 

  if [[ -n "$(whereis gem_server)" ]]; then
     gem_server >/dev/null 2>&1 &
     sleep 3
     open http://127.0.0.1:8808/
  fi

}