part of the Sahara and the hills of the eastern Maghreb. The eastern Sanhaja included the Kutama Berbers, who had been the base of the Fatimid rise in the early 10th century, and the Zirid dynasty, who ruled Ifriqiya as vassals of the Fatimids after the latter moved to Egypt in 972. The western Sanhaja were divided into several tribes: the Gazzula and the Lamta in the Draa valley and the foothills of the Anti-Atlas range; further south, encamped in the western Sahara, were the Massufa, the Banu Warith; and most southerly of all, the Lamtuna and Gudala, in littoral Mauritania down to the borderlands of the Senegal River. The western Sanhaja had been converted to Islam some time in the 9th century. They were subsequently united in the 10th century and, with the zeal of new converts, launched several campaigns against the "Sudanese" (pagan peoples of sub-Saharan Africa). Under their king Tinbarutan ibn Usfayshar, the Sanhaja Lamtuna erected (or captured) the citadel of Aoudaghost, a critical stop on the trans-Saharan trade route. After the collapse of the Sanhaja union, Aoudaghost passed over to the Ghana Empire; and the trans-Saharan routes were taken over by the Zenata Maghrawa of Sijilmasa. The Maghrawa also exploited this disunion to dislodge the Sanhaja Gazzula and Lamta out of their pasturelands in the Sous and Draa valleys. Around 1035, the Lamtuna chieftain Abu Abdallah Muhammad ibn Tifat (alias Tarsina), tried to reunite the Sanhaja desert tribes, but his reign lasted less than three years. Around 1040, Yahya ibn Ibrahim, a chieftain of the Gudala (and brother-in-law of the late Tarsina), went on pilgrimage to Mecca. On his return, he stopped by Kairouan in Ifriqiya, where he met Abu Imran al-Fasi, a native of Fez and a jurist and scholar of the Sunni Maliki school. At this time, Ifriqiya was in ferment. The Zirid ruler, al-Mu'izz ibn Badis, was openly contemplating breaking with his Shi'ite Fatimid overlords in Cairo, and the jurists of Kairouan were agitating for him to do so. Within this heady atmosphere, Yahya and Abu Imran fell into conversation on the state of the faith in their western homelands, and Yahya expressed his disappointment at the lack of religious education and negligence of Islamic law among his southern Sanhaja people. With Abu Imran's recommendation, Yahya ibn Ibrahim made his way to the ribat of Waggag ibn Zelu in the Sous valley of