Jailbreak iPhone 3GS 3.1.3
Only one way to jailbreak iPhone 3.1.3 is using Pwnage 3.1.5 that was released by The Dev Team. This tutorial will use that tool as primer software. Unfortunately, it is available just for Mac only, the Windows version is still under development (may be).
But you have to remember before you do these all, everything is under your responsibility so it is better if you read the article that have been written by the Dev Team here. You will find the explanation about what you have to do or not. You should read the details because if you do it wrong you will lose your iphone. warranty will be lost because of it.
The point is if your iPhone has firmware 3.1.3 then you can’t jailbreak your iPhone yet. You have to downgrade to 3.1.2 first before jailbreaking and it can’t to unlock your iPhone from carrier.
You can jailbreak the iPhone (2G, 3G, old bootrom 3GS) 3.1.3.
For new bootroom 05.12.01 you can follow how to jailbreak iPhone 3GS 3.1.3 tutorial.