My Weblog

Blog about programming and math

Baby-step Giant-step Algorithm

Baby-step giant step algorithm is used for discrete logarithm problem. I implement this code to solve spoj problem 3105 Power Modulo Inverted but i am getting TLE.For this problem i implemented a faster extended Eucleadean algorithm given on Algorithmic Number theory Vol 1 Efficient Algorithms but still out of luck :(.

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 ()  
Advertisements

February 14, 2011 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: