Mod Haskell Homework

My homework was to provide a function that computes 'x^y mod n' -for any n < (sqrt maxint32)

So I started by writing doing this:

modPow :: Int -> Int -> Int -> Int 
modPow x y n = (x `mod` n) ^ (y `mod` n) `mod` n

Which seemed to work fine, for any number of n, although my next homework question involved using x^n mod n = x (Camichael numbers) and I could never get modPow to work.

So I made another modPow using pseudocode for mod exponentiation, -from wikipedia:

modPow2 :: Int -> Int -> Int -> Int 
modPow2 x y n 
 = loopmod 1 1
  where
   loopmod count total = if count > y
                          then total
                           else loopmod (count+1) ((total*x) `mod` n)

Whi开发者_如何学运维ch now correctly produces the right answer for my next question, (x^n mod n = x) -for checking for Camichael numbers.

ALTHOUGH, modPow2 does not work for big numbers of 'y' (STACK-OVERFLOW!!)

How could I adjust modPow2 so it no longer gets a stackoverflow in the cases where y > 10,000 (but still less than sqrt of maxint 32 -which is around 46,000)

Or is there a fix on my original modPow so it works with x^n mod n = x? (I always do 560 561 561 as inputs and it gives me back 1 not 560 (561 is a carmichael number so should give 560 back)

Thanks alot.

Your formula for modPow is wrong, you can't just use y mod n as the exponent, it will lead to wrong results. For example:

Prelude> 2^10
1024
Prelude> 2^10 `mod` 10
4
Prelude> 2^(10 `mod` 10) `mod` 10
1

For a better modPow function you could use that x2n+1 = x2n ⋅ x and x2n = xn ⋅ xn and that for multiplication you actually can simply use the mod of the factors.

Where did you get your formula for modPow from?

(x ^ y) `mod` n = ((x `mod` n) ^ (y `mod` φ n)) `mod` n where φ is Euler's totient function.

This is probably because the argument total is computed lazily.

If you use GHC, you can make loopmod strict in total by placing a ! in frontof the argument, i.e.

loopmod count !total = ...

Another way would be to force evaluation of total like so: Replace the last line with

else if total == 0 then 0 else loopmod (count+1) ((total*x) `mod` n)

This does not change semantics (because 0*xis 0 anyway, so the reminder must be 0 also) and it forces hugs to evaluate total in every recursion.

If you are looking for implementation ( a^d mod n ) then

powM::Integer->Integer->Integer->Integer
powM a d n
   | d == 0 = 1
   | d == 1 = mod a n
   | otherwise = mod q n  where
       p = powM  ( mod ( a^2 ) n ) ( shiftR d 1 ) n
       q = if (.&.) d 1 == 1 then mod ( a * p ) n else p