Power Modulo Inverted

[mukesh_iiitm]

Hello all, I am trying to solve this https://www.spoj.pl/problems/MOD/ in haskell but getting TLE. I just want to know if this problem is solvable in Haskell or not ? I have implemented baby step giant step algorithm http://www.cs.sjsu.edu/~stamp/crypto/PowerPoint_Mac/ 19_DiscreteLog.ppt. Here is my source code.

import Data.List
--a^x=b mod p
modpoW::Integer->Integer->Integer->Integer
modpoW a 0 n=1
modpoW a d n= fun a d where
        fun a 1 = mod a n
        fun a 2 = mod (a^2) n
        fun a d = let
                        p=fun (mod (a^2) n) (div d 2)
                        q=if odd d then mod (a*p) n else p
                  in mod q n
extendedgcD::Integer->Integer->Integer
extendedgcD a b=
        let
           [u,v,d]=exgcD a b where
                exgcD a b | mod a b == 0 = [0,1,b]
                          | otherwise = [y,x-y*(div a b),z]
                          where
                                [x,y,z] = exgcD b (mod a b)
        in if d<0 then -u else u
babysteP a b p=
  let 
    m=ceiling.sqrt.fromIntegral $ (p-1)
    u=extendedgcD a p
    bm=[(i,mod (b*modpoW u (i*m) p) p)|i<-[0..(m-1)]]
  in recfuN a p m 0 bm
recfuN a p m cnt bm
  | cnt>=m = -1
  |otherwise = case find (\(x,y)->y == modpoW a cnt p) bm of 
			Just (x,y)->x*m+cnt
			_-> recfuN a p m (cnt+1) bm
main=do
	line<-fmap words getLine
	let a=read (line!!0)::Integer
	    p=read (line!!1)::Integer
	    b=read (line!!2)::Integer
	case and [a==0,b==0,p==0] of 
	  False-> do 
		    if gcd a p /=1 then putStrLn $ snd (1,"No Solution") else print $ fst(babysteP a b p,"")
		    main
	  _ -> return ()

[mukesh_iiitm]

Till now, i did not get any reply . I also implemented the algorithm given on Wiki http://en.wikipedia.org/wiki/Baby-step_giant-step but still no luck. Although wiki page mentions about hash table but its bit slow in Haskell [i am not sure about this] so i used IntMap but still TLE. It would be nice if problem setter run this program on inputs and tell me how much time it took for this problem. My mail id mukeshtiwariDOTiiitmATgmail.com. Replace DOT with . and AT with @
Thank you

import Data.List
import Data.Bits
import Data.IntMap
--a^x=b mod p find x
modpoW::Integer->Integer->Integer->Integer
modpoW a 0 n=1
modpoW a d n= fun a d where
        fun a 1 = mod a n
        fun a 2 = mod (a^2) n
        fun a d = let
                        p=fun (mod (a^2) n) (shiftR d 1)
                        q=if (.&.) d 1 == 1 then mod (a*p) n else p
                  in mod q n
extendedgcD::Integer->Integer->[Integer]
extendedgcD u v= 
  let
        m=[[1,0],[0,1]]
        n=0
  in helpgcD u v n m
helpgcD::Integer->Integer->Integer->[[Integer]]->[Integer]
helpgcD u v n m
  | v==0 = if u<0 then [-((-1)^n)*(m!!1!!1),-((-1)^(n+1))*(m!!0!!1),-u]
           else [((-1)^n)*(m!!1!!1),((-1)^(n+1))*(m!!0!!1),u]   --ux+vy=gcd(u,v)
  |otherwise = 
      let
        q= div u v 
        t=[[q,1],[1,0]]
        m'=mult m t
        u'=v
        v'=u-q*v
      in helpgcD u' v' (n+1) m'
--matrix multiplicatio
mult::[[Integer]]->[[Integer]]->[[Integer]]
mult m t = [[ sum $ zipWith (*) x y |  y<-transpose t ] | x<-m]
babysteP::Integer->Integer->Integer->Integer
babysteP a b p =
   let
     m=ceiling.sqrt.fromIntegral $ p
     mp=Data.IntMap.fromList [(fromIntegral $ modpoW a j p,fromIntegral j)|j<-[0..(m-1)]]
     [u,_,_]=extendedgcD a p
     inv=modpoW u m p
     y=b
   in recfuN y inv 0 m p mp
recfuN::Integer->Integer->Integer->Integer->Integer->IntMap Key->Integer
recfuN y inv cnt m p mp
	| cnt>=m = -1
	| otherwise = case Data.IntMap.lookup (fromIntegral y) mp of
    					Just x -> cnt*m+(fromIntegral x)
    					_ -> recfuN (mod (y*inv) p) inv (cnt+1) m p mp
main=do
	line<-fmap words getLine
	let a=read (line!!0)::Integer
	    p=read (line!!1)::Integer
	    b=read (line!!2)::Integer
	case and [a==0,b==0,p==0] of 
	  False-> do 
		    if gcd a p /=1 then putStrLn $ snd (1,"No Solution") else print $ fst(babysteP a b p,"")
		    main
	  _ -> return ()

[leppyr64]

It might be more wise to contact the problem setter himself from the problem page. There's no guarantee that he actually reads the forum.

I don't know how fast Haskell is, but I notice that there are very few solutions for this problem and that all are C/C++. That doesn't bode well for many languages.

[mukesh_iiitm]

@leppy Thank you. Yes looking at the solutions does not augur well for Haskell . Although compiled Haskell is not very slow but can't compete with c.

[gorlum0_sof]

Hello all, I am trying to solve this https://www.spoj.pl/problems/MOD/ in haskell but getting TLE.

No idea about the problem itself but for one thing ditch Strings (they are damn slow) and use ByteStrings.

It's a start: http://www.haskell.org/haskellwiki/SPOJ, http://www.haskell.org/haskellwiki/Performance.