Module: ExpMod

Included in:
Integer
Defined in:
lib/exp_mod.rb

Overview

Author

Nicolas Pouillard <[email protected]>.

Copyright

Copyright © 2006 Nicolas Pouillard. All rights reserved.

License

GNU General Public License (GPL).

Revision

$Id: /w/fey/ruby_ex/trunk/lib/exp_mod.rb 53899 2007-01-13T11:21:51.227355Z ertai $

Instance Method Summary collapse

Instance Method Details

#exp(m, p) ⇒ Object 



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
# File 'lib/exp_mod.rb', line 8

def exp ( m, p )
  case m
  when 0 then 1
  when 1 then self % p
  else
    q, r = m.divmod(2)
    tmp1 = self.exp(q, p)
    tmp2 = (tmp1 * tmp1) % p
    if r == 0
      tmp2
    else
      (tmp2 * self) % p
    end
  end
end