# This is an implementation of modexp function. This should
# work even once we promote ourself :-). Knuth's Algorithm A, 
# from p462 of latest edition of Seminumerical Algorithms.
# (Actually al-Kashi's method from A.D. 1427). 

module Crypto_math
  def mod_exp(n,q)
    counter=0
    n_p=n.clone  # N 
    y_p=1        # Y
    z_p=self.clone  # Z
    while n_p != 0
      # if N is odd, multiply Y * Z
      # Whoa, we can access the bits of our integer as if they were
      # an array! But will this work on big-endian machines?
      if n_p[0]==1
	y_p=(y_p*z_p) % q
      end
      # divide n_p by 2. Whoa, shifts!
      n_p = n_p >> 1  
      # and square Z. 
      z_p = (z_p * z_p) % q
      counter += 1
    end
    return y_p
  end

  # define a random number of size <self>. <self> is a number of bytes, 
  # *NOT* a  # of bits! This will need to be modified to
  # work on anything other than Unix, because it uses /dev/urandom. If you
  # are on a Unix without a dev/urandom, such as Solaris, use
  # Ocotillo (http://ocotillo.sourceforge.net) as your PRNG. 
  def random()
    n=self.clone
    fh=open("/dev/urandom","r")
    if (!fh) 
      fh=open("/dev/orandom","r")  # optional place. Used on OpenBSD?
    end
    if (!fh)
      raise "NO RANDOM DEVICE"
    end
    
    i=0
    s=fh.read(n)

    # fancy iterator stuff w/Ruby:
    # n times go thru the loop, assigning then-extant value of n to j:
    n.times { |j|
      i = i << 8
      i  = i | s[j]  # yep, a 1 char slice in an integer context is guess what?
    }
    fh.close()
    return i
  end

end

class Bignum
  include Crypto_math
end

class Integer
  include Crypto_math
end

def test2
  a=2
  while ! a.prime?
    a=128.random
  end
end


# This is a function which uses a known good x, prime, and modulus and
# calculates the Diffie-Hellman public key X. It then compares that to
# the known result (verified using GNU 'dc') of that computation.
def modexp_test
    xx = 49117580844089262911901355287841171890576818657783650753208599277090946608629052545518247108642827866451823318941178603034571795108477894778537021991948831723834734775338379867275461698639906953156054434705292259216951056048592911855948753912610254573728484318415808276565668885865182466683752111480091234494
  xx_p = 30158485397977097914735031672721612436752995275618102225850571305439073652645575546335570053366437128295206695951378422564597822594563680088505296658477187110003231072414234938371090319047261957332420471075050710901794412840771927620865592590749106381943024352923477346561065087247748578874293152671594497151
  field=106711310550942323238863446954494903303206603796265590798875260590060843568007841918927773348877395895791048832517368787533445258799160241834659776192282820736018472427221910874308833884006430888272214561307777629540843737689598751552666502301405808925850579645658786877473119117134988654123934303586903124139
  #result=xx.mod_exp(2,field)
  result=2.mod_exp(xx,field)
  print "\n    XX=#{xx_p}\n\nresult=#{result}\n"
  

  print "\nRandom number test: 2.random, 5 times:\n     #{2.random},#{2.random},#{2.random},#{2.random},#{2.random}\n"
  
  
end