It's a very hot day in Aix-en-Provence, and at the crowded terrasse of Le Festival on the Cours Mirabeau, the city's main thoroughfare, harried waiters rush around with expressions on their faces which say "Not now". Here sits Mohammed Mousselehoul: a former Algerian army officer in his early fifties, short, trim, his skin a copper colour after a trip to the West Indies. There's something of the army in the vigour of his handshake. Despite his large, tinted glasses, you glimpse in the eyes some of the melancholy and combativeness of his country, still convalescing after a decade-long civil war to which he was a close witness.
Mousselehoul is better known by another name: Yasmina Khadra, the author of some of the most ambitious fiction to come out of France in recent years. He has found admirers in Nobel Prize winner JM Coetzee, with whom he shares a dislike for the easy consensual read. For instance, his most recent novel on Palestinian terrorism, The Attack , was recently passed over by the Goncourt Prize jury in favour of another polite snooze written on the Left Bank in Paris. France might have fallen in love once more with its ethnically diverse football team, but its reality remains depressingly unchanged. Arab authors, particularly those who dare to write relevant books, have to work twice as hard for half the reward.
Perhaps that's not so hard if the vocation is there? The man who became "Yasmina Khadra" was born in Kenadsa, in the Sahara, in 1955. His mother, of nomadic origins, was her tribe's chief storyteller. As Algeria began its struggle for independence from France, his father, then a nurse, joined the ALN (Algerian National Liberation Army). Of the war, Khadra has few memories. "I was too young," he says. A few minutes later, however, he leans forward to show a scar on the top of his crown. "A French soldier was trying to disperse a crowd. He cracked me over the head with his rifle butt. And broke my skull."
His father, now an officer, enrolled him in the army, or rather the Soviet-inspired School of the Cadets of the Revolution, when he was nine. It's a shock described in his 2001 book, The Writer, and one for which his father was never quite forgiven. But perhaps perfect childhoods don't make for writers. "I was first a reader, devoted to Arabic poetry," he remembers. "As a teenager I discovered Kafka and Gogol. Camus overwhelmed me. From then on I was in love with the novel, in love with the French language. French structured me, and was always my absolute in moments of the greatest solitude. I became a writer."
In newly independent Algeria, imbued with Soviet orthodoxies and Soviet paranoia, writers were isolated. In the army a literary vocation was a heresy. Having fallen foul of the hierarchy with his earliest short stories, he ran into trouble as soon as he began publishing his first novels, under his own name, in the 1980s. Not least, because they portrayed an Algeria where a jaded, corrupt power was rapidly losing ground to Islamic fundamentalism. "In 1988, I was brought before a tribunal. As an officer, I already exerted considerable self-censorship. The situation was becoming unbearable."
His wife suggested a solution. "During those years, she was always my first reader, if not the only one I could confide my manuscripts to. She suggested that I take a pseudonym. She said, 'When I married you, I took your name for life. What if you took mine, for posterity?' So I went into clandestinity."
This was not without problems. By 1999, with the publication of Morituri, set in the Algeria caught in the throes of civil war and fundamentalism, Yasmina Khadra had become Algeria's foremost author, and the subject of much media speculation. "She", or rather he, would do interviews by fax only.
In 2000 he was sufficiently well off to retire from the army. "In the army, your life is not your own. Nevertheless, it was enriching for me as a writer. Living with hundreds of people all the time, you learn to grasp character in an instant - who is sly, who is brave, who is wicked."
After a brief stay with wife and family in Mexico City, he moved to Aix-en-Provence. From this well-heeled, rather conservative town which has yet to honour its most famous author with an official reception, he revealed, with the 2001 publication of The Writer, his true identity to the French public. Yet he continues to publish under his wife's name. "It's not just a tribute to her, but to Arab womanhood in general. In some Arab countries, women account for as much as 60 per cent of the population, and are still completely marginalised."
Indeed, Khadra's women are richly rendered. This is much in evidence in The Swallows of Kabul (2004), shortlisted for the IMPAC prize. The main female characters of this novel set in Afghanistan in the run-up to the attacks of 11 September 2001 - Zunaira, a former lawyer revolted by the burkha she must wear, and the traditionalist Mussarat, terminally ill and married to a boorish prison guard - are more alive, more loving, than their menfolk benumbed by the desolate idiocy of Taliban rule.
The Swallows of Kabul is the first in a trilogy in which Khadra sets out to describe the contemporary Orient, in particular the galvanising power of Islamic fundamentalism. "There is a tremendous ignorance in the West about Arab and Islamic culture, whereas in the Orient, both the Bedouin nomad and the terrorist know what's going on over here, what films Westerners watch, how they think. We are in the middle of the worst misunderstanding to befall our two cultures. I wish to take the Western reader into that other world."
Second in the trilogy, The Attack (translated by John Cullen; Heinemann, £10.99) is probably Khadra's most ambitious novel to date. Amin Jaafiri is an Israeli citizen of Palestinian origins: a successful surgeon in Tel Aviv, he is fêted by Israeli society as a model of successful assimilation. On the day of a suicide bomb attack, he treats patients who spit in his face, only to learn later that it's his adored wife who has blown herself up.
"The Israel/Palestine conflict destabilises not just the Middle East, but the entire world," its author says. "On both sides it shows up man at his most wicked and bestial. The figure of Amin, a naturalised Israeli citizen whose wife cannot share in his happiness because her own happiness is rendered meaningless by the sickening conditions the Palestinians must endure, seemed the best way to encapsulate the problem."
We follow Amin as he spins out of Israeli society. Nursed back to life by a Jewish colleague, Kim Yehuda, he flees police investigators to go to Bethlehem, seeking to meet the movement for whom his wife was willing to offer up her life. The outcome of these encounters is far from conclusive, but their power is in the lucidity and the intelligence of the terrorists Amin despises.
Khadra says that "During the Algerian civil war, I was in charge of a unit specialising in counter-terrorism. Make no mistake - terrorists are rational people... To portray them as mad, unhinged individuals, as is most often the case in the West, is to nourish the problem."
On its publication in the US, The Attack was considered by several commentators to be an apology for terrorism. Its Jewish characters, they argued, were not sympathetic enough. True, no ultra-Orthodox settlers rush out to make their Palestinian neighbours glasses of mint tea, but contemporary Israel is hardly a society at ease with itself. Khadra is scandalised by such criticisms. "In Algeria, I saw comrades blown apart so badly you could only pick them up with a tiny spoon. If people wish to destroy my work with such remarks, let them: 36 years in the army couldn't break me."
In September this year, the final part of the trilogy, The Sirens of Baghdad, will be published in France. As a portrait of a young Bedouin who grows to despise the American occupation of Iraq, it's bound to be the subject of polemic - as well as one of the most important books to be published in Europe this year. "We are living in an age where much of the media coverage of the Orient is lies and fabulation," he says, "driven by an ideology that Arabs are barbarous, Westerners civilised. The soldiers who drag Arab women from their beds at night, however, have nothing on Neolithic man... In the end, the novel is a tool, an instrument, which makes truth accessible. Only fiction tells the truth."
Yasmina Khadra is the pseudonym of Algerian author Mohammed Mousselehoul. Born in Kenadsa in the Algerian Sahara in 1955, Moulessehoul began writing while training to become an army officer. In order to avoid military censors, he began publishing under his wife's name - Yasmina Khadra - in 1988. He is now Algeria's most celebrated writer, translated in 25 languages. His books in English include Morituri, In the Name of God (2000), Wolf Dreams (2004), The Swallows of Kabul (2004), the first in a trilogy which was shortlisted for the IMPAC prize. The second in the trilogy, The Attack, is published by Heinemann this week. He lives in Aix-en-Provence.