# My Weblog

## 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