A5/1 is the strong encryption algorithm which protects the air interface of the GSM cellular network. However, in the Fast Software Encryption Workshop 2000, two attacks, the biased birthday attack and the random subgraph attack against A5/1 were presented. We propose new security enhancements to improve A5/1 encryption algorithm from the biased birthday attack and random subgraph attack in order to be used in future mobile communication systems. The improvements that make both attacks impractical are based on the clocking mechanism of the registers, and their key setup routine. Furthermore, we have increased the linear complexity of A5/1 to make the solution of the linear equations impractical in real time systems. Finally, both original and modified versions of A5/1 were implemented easily in a complex programmable logic device (CPLD). The modified version of A5/1 is fast, easy to implement, and most important small in size which makes it ideal for future mobile terminals.