Feb 2011
1 / 5
Feb 2011
Feb 2011
mukesh_iiitm
Feb '11

Hello all, I am trying to solve this https://www.spoj.pl/problems/MOD/15 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/5 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 ()

  • created

    Feb '11

  • last reply

    Feb '11
  • 4

    replies

  • 876

    views

  • 3

    users

  • 5

    links

mukesh_iiitm
Feb '11

Till now, i did not get any reply frowning . I also implemented the algorithm given on Wiki http://en.wikipedia.org/wiki/Baby-step_giant-step11 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
Feb '11

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
Feb '11

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