French and Malian troops are fighting Islamist rebels in the Sahara outside northern Mali's biggest town, France's defense minister said on Wednesday, describing the desert campaign against al Qaeda as a "real war" that was far from won.

After driving the Islamists from northern Mali's main towns with three weeks of air strikes and a lightning ground advance, France is now pursuing them in the remote northeast, where pro-autonomy Tuaregs are pressing their own territorial claims.

French Defence Minister Jean-Yves Le Drian said French and Malian joint patrols were searching the scrubland outside the desert trading towns of Timbuktu and Gao. Gao residents said on Tuesday the town had been hit by rebel rockets fired from the bush.