diff options
| -rw-r--r-- | lib/ayk/maths.rb (renamed from lib/ayk/math.rb) | 177 | ||||
| -rw-r--r-- | spec/maths_spec.rb | 74 |
2 files changed, 199 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 diff --git a/spec/maths_spec.rb b/spec/maths_spec.rb new file mode 100644 index 0000000..aaa76e6 --- /dev/null +++ b/spec/maths_spec.rb @@ -0,0 +1,74 @@ +#! /usr/bin/env ruby +# -*- coding: UTF-8 -*- +# +require 'ayk/maths' +# +describe "Maths" do + # + PRIMES = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, + 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, + 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, + 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, + 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, + 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, + 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, + 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, + 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, + 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 + ] + describe Math do + it "check Math.prime? on 1..1000" do + (0..1000).each do |n| + if PRIMES.include? n + Math.prime?(n).should be_true + else + Math.prime?(n).should be_false + end + end + end + it "check Math.prime" do + Math.prime?( Math.prime 8).should be_true + end + it "check Math.sieve on 1..1000" do + primes = Math.sieve 1000 + primes.length.should eql PRIMES.length + primes.each do |p| + PRIMES.include?(p).should be_true + end + end + it "check Math.gcd" do + Math.gcd(123,27).should eql 3 + Math.gcd(54,24).should eql 6 + end + end + describe Fixnum do + it '#to_bytes #from_bytes should work' do + 16777700.should eql Bignum.from_bytes(16777700.to_bytes) + end + it '#bits' do + (1..255).each do |n| n.bits.should eql 8 end + (256..500).each do |n| n.bits.should eql 16 end + (60000..60500).each do |n| n.bits.should eql 16 end + (65536..66000).each do |n| n.bits.should eql 24 end + (16777000..16777215).each do |n| n.bits.should eql 24 end + (16777216..16777700).each do |n| n.bits.should eql 32 end + (1073741000..1073741823).each do |n| n.bits.should eql 32 end + (1073741000..1073741823).each do |n| n.should be_a Fixnum end + end + end + describe Bignum do + it '#to_bytes #from_bytes should work' do + 0x217962755220666f207463657073612074656577732061207369206d756e676942 + .should eql Bignum.from_bytes(0x217962755220666f207463657073612074656577732061207369206d756e676942.to_bytes) + end + it '#bits' do + (1073741824..1073742000).each do |n| n.should be_a Bignum end + (1073741824..1073742000).each do |n| n.bits.should eql 32 end + (4294967000..4294967295).each do |n| n.bits.should eql 32 end + (4294967296..4294967500).each do |n| n.bits.should eql 40 end + end + end + # +end +# +#EOF |