any ruby libs to do modular integer arithmetic?

S

Sam Roberts

Modular reductions, modulare inversions, etc.

I'm looking through the library docs now, but not seeing anything.

Cheers,
Sam
 
B

Bret Jolly

Sam Roberts said:
Modular reductions, modulare inversions, etc.

I'm looking through the library docs now, but not seeing anything.

Cheers,
Sam

It's far from complete or optimal, and it's nearly undocumented,
but maybe my Imod library might do what you need. Ultimately, it
should have the functionality of "Mod" in Pari/gp. This generates
"integermods" -- mathematical entities equivalent to residue classes
of integers. My rules for arithmetic of integermods with different
moduli are derived from Pari/gp.

The Imod library can create integermods in two ways:
a = Imod(7, 13) # 7 mod 13
a = 7.imod(13) # 7 mod 13
b = a.inv # mod 13 reciprocal: b == Imod(2, 13)
a*b # => Imod(1, 13)
Imod(5, 13)*Imod(7,13) # => Imod(9, 13)
b = Imod(4, 12)
b.inv # => nil (no inverse) (probably should raise exception)
7.imod(4) == -1.imod(4) # => true

BTW, if there is some particular functionality you'd like,
feel free to ask.

Here is what I have so far.

Put the following in a file "imod.rb"
-------------------------------------
#!/usr/bin/env ruby
# -*- ruby -*-
# file imod.rb
# Integermods for ruby
# Uses ordinary integers for modulus == 0

reqfiles = %w(English mathn)
reqfiles.each{|f| require f}

class Integer
# The lcm bundled with mathn (from rational.rb) is broken
alias :eek:ld_lcm :lcm
def lcm(b)
if self == 0 and b == 0 then return 0 end
old_lcm(b)
end

def num
self
end

def modulus
0
end

def factors # prime factors with multiplicities
a = self.abs; factor_hash = Hash.new
Prime.new.each { |p|
while a % p == 0 do
factor_hash[p] ||= 0 # initialize if it doesn't exist
factor_hash[p] += 1
a = a.div(p)
end
break if a < p
}
factor_hash
end

def moebius_mu
h = factors; mu = 1
h.each_key{ |k|
return 0 if h[k] > 1
mu = -mu
}
mu
end

def totatives
t = [1] # 1 is always a totative
(2..self).each{|k| t << k if self.gcd(k) == 1}
t
end

# Is this really much faster than self.totatives.length ?
# Can this be rewritten with inject?
def totient
p = 1
self.factors.each{|k, s| p *= k**s - k**(s-1)}
p
end

alias :euler_phi :totient

def primitive_roots
# STUB
end

def imod(m)
Imod(self,m)
end

end

# a & m are integers
def Imod(a, m)
if m == 0 then a else Imod.new(a, m) end
end

# Duck-type x.is_a?(Integer) as x.responds_to?(modulus) and x.modulus==0
# @modulus.totient is used a lot. This should be precalculated or at
# least memoized.
class Imod < Numeric
attr_reader :num, :modulus

# Imod.new should not be used directly: use constructor Imod or n.imod(m)
# instead. num and modulus are integers: modulus != 0
# In the constructor Imod and integer method imod, a modulus of 0 results
# in an integer

def initialize(num, modulus)
raise ArgumentError unless num.kind_of?(Integer)
raise ArgumentError unless modulus.kind_of?(Integer)
raise ArgumentError if modulus == 0
@num = num.modulo(modulus.abs)
@modulus = modulus
end

def coerce(other)
if other.is_a?(Integer)
[Imod(other, @modulus), self]
end
end

def unit?
@num.gcd(@modulus) == 1
end

def ==(other)
other.is_a?(Imod) and @num == other.num and @modulus == other.modulus
end

def +(other)
if other.is_a?(Integer)
self + Imod(other, @modulus)
else # assume Imod
g = @modulus.gcd(other.modulus)
Imod(@num + other.num, g)
end
end

def -(other)
if other.is_a?(Integer)
self - Imod(other, @modulus)
else # assume Imod
g = @modulus.gcd(other.modulus)
Imod(@num - other.num, g)
end
end

def *(other)
if other.is_a?(Integer)
g = @modulus
else # assume other is Imod
g = @modulus.gcd(other.modulus)
end
return Imod(@num * other.num, g)
end

def **(n)
raise ArgumentError unless n.is_a?(Integer)
if n < 0
raise ArgumentError unless self.unit?
return (self.inv)**(-n)
else # TODO: better algorithm for the else branch
n = n.modulo(@modulus.totient)
p = 1
n.times do p *= self end
end
return p
end

# probably should raise exception for non-unit
def inv
if self.unit?
self**(@modulus.totient - 1)
else
nil
end
end

# temporary bone-headed implementation
def square?
s = false
(0...@modulus).each{|num|
t = Imod(num, @modulus)
if t*t == self
s = true
break
end
}
s
end

alias :quadratic_residue? :square?

def primitive_root?
# STUB
end
alias :prim_root? :primitive_root?

def discrete_log(g)
# STUB
end

alias :ind :discrete_log

def haupt_exponent
# STUB
end

alias :multiplicative_order :haupt_exponent
alias :modulo_order :haupt_exponent
# Would "#{@num}.imod(#{@modulus})" be better?
def to_s
"Imod(#{@num}, #{@modulus})"
end

# Need Legendre-Jacobi symbols and other good stuff
# Need Chinese remainder stuff

end
 
B

Bret Jolly

I forgot to mention that Shin-Ichiro Hara's wonderful
algebra package can certainly do anything you want.
Look at his residue-class-ring.rb However, it can do
so much that you might find it overkill. My Imod package,
though unfinished and undocumented, should be easier to
use.

Regards, Bret
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top