rename math into maths, add function and specs

1 files changed, 125 insertions, 52 deletions

diff --git a/lib/ayk/math.rb b/lib/ayk/maths.rb
index 90a3b3a..5084eac 100644
--- a/lib/ayk/math.rb
+++ b/lib/ayk/maths.rb
@@ -1,14 +1,7 @@
 #! /usr/bin/env ruby
 # -*- coding: UTF-8 -*-
-
-#----------------------------------------------------------------------------
-#
-# File     : math.rb
-# Author   : Jérémy Zurcher <jeremy@asynk.ch>
-# Date     : 14/09/09 
-# License  :
 #
-#   Copyright (c) 2009 Jérémy Zurcher
+#   Copyright (c) 2009-2011 Jérémy Zurcher
 #
 #   Permission is hereby granted, free of charge, to any person obtaining
 #   a copy of this software and associated documentation files (the
@@ -34,9 +27,41 @@
 #def prime?
 #    ('1'*self) !~ /^1?$|^(11+?)\1+$/
 #end
-#def Math.gcd(x,y)
-#    /^(1+)\1*=\1+$/.match('1'*x+'='+'1'*y)[1].length
-#end
+#
+# return true if is a prime number
+def Math.prime? x
+    return true if x==2 or x==3
+    return false if x<2 or ( x%2 == 0 ) or ( x%3 == 0 )
+    r = (x**0.5).floor
+    d = 5
+    while d<=r
+        return false if ( x%d == 0 ) or ( x%(d+2) == 0 )
+        d+=6
+    end
+    true
+end
+#
+# return a bits long prime number
+def Math.prime bits
+    bytes_n,bits_n = bits.divmod 8
+    bytes = []
+    begin
+        # n = ( (rand()*Time.now.to_f).to_i & 0xff) | 0x80 random char better than rand(255) + 1 ?????
+        # rand currently uses a modified Mersenne Twister with a period of 2**19937-1
+        srand()
+        bytes.clear
+        bytes_n.times do
+            bytes << rand(255)+1
+        end
+        bytes << ( ((rand()*Time.now.to_f).to_i & 0xFF | 0x80) >> (8 - bits_n) )
+        n = Bignum.from_bytes bytes.inject(''){|s,b|s+=b.chr}
+        n+= 1 if n%2 == 0
+        while not Math::prime? n
+            n += 2
+        end
+    end while n.bits != bits
+    n
+end
 #
 # generate prime numbers < n
 def Math.sieve n
@@ -50,62 +75,110 @@ def Math.sieve n
     sieve.compact
 end
 #
+#def Math.gcd(x,y)
+#    /^(1+)\1*=\1+$/.match('1'*x+'='+'1'*y)[1].length
+#end
+#
 # return greater common divisor
 def Math.gcd x, y
     y,x=x,y if x<y
-    while y > 0 
-        r = x % y 
+    while y > 0
+        r = x % y
         x = y
         y = r
     end
     return x
 end
 #
-# return true if is a prime number
-def Math.prime? x
-#    return false if x <0
-    if x==3
-        return true
-    elsif x % 2 == 0
-        return false
-    elsif x % 3 == 0
-        return false
+def Math.prime_power_modulus(b, p, m)
+    if p == 1
+        b % m
+    elsif (p & 0x1) == 0
+        t = prime_power_modulus(b, p >> 1, m)
+        (t * t) % m
     else
-        r = (x**0.5).floor
-        d = 5
-        while d<r
-            if x % d == 0
-                return false
-            end
-            if x % (d + 2) == 0
-                return false
-            end
-            d+=6
+        (b * prime_power_modulus(b, p-1, m)) % m
+    end
+end
+#
+class Fixnum
+    #
+    class << self
+        def from_bytes bytes
+            val = 0
+            idx = 0
+            bytes.each_byte{ |b|
+                val += b << 8 * idx
+                idx += 1
+            }
+            val
+        end
+    end
+    #
+    def to_bytes
+        str = ''
+        int = self
+        while int!=0 do
+            int,r = int.divmod 256
+            str += r.chr
         end
-        return true
+        str
     end
+    #
+    def bits
+        s = self.to_bytes
+        while s[-1].ord==0
+            s.slice!(-1)
+        end
+        bit_len = s.length * 8
+        tmp = s[-1].ord
+        while not tmp & 0x80
+            bit_len-=1
+            tmp <<=1
+        end
+        bit_len
+    end
+    #
 end
 #
-# return a bits long prime number
-def Math.prime bits
-    bytes_n,bits_n = bits.divmod 8
-    bytes = []
-    begin
-        # n = ( (rand()*Time.now.to_f).to_i & 0xff) | 0x80 random char better than rand(255) + 1 ?????
-        # rand currently uses a modified Mersenne Twister with a period of 2**19937-1
-        srand()
-        bytes.clear
-        bytes_n.times do
-            bytes << rand(255)+1
+class Bignum
+    #
+    class << self
+        def from_bytes bytes
+            val = 0
+            idx = 0
+            bytes.each_byte{ |b|
+                val += b << 8 * idx
+                idx += 1
+            }
+            val
         end
-        bytes << ( ((rand()*Time.now.to_f).to_i & 0xFF | 0x80) >> (8 - bits_n) )
-        n = Bignum.from_bytes( bytes.inject(''){|s,b|s+=b.chr} )
-        puts n
-        n+= 1 if n%2 == 0
-        while not Math::prime? n
-            n += 2
+    end
+    #
+    def to_bytes
+        str = ''
+        bint = self
+        while bint!=0 do
+            bint,r = bint.divmod 256
+            str += r.chr
         end
-    end while n.bits != bits
-    n
+        str
+    end
+    #
+    def bits
+        s = self.to_bytes
+        while s[-1].ord==0
+            s.slice!(-1)
+        end
+        bit_len = s.length * 8
+        tmp = s[-1].ord
+        while not tmp & 0x80
+            bit_len-=1
+            tmp <<=1
+        end
+        bit_len
+    end
+    #
 end
 #
+#EOF