Each time crusaders triumphed over Muslims in the Middle Ages, bells pealed from the spires of Christendom. The bells of Notre Dame Cathedral tolled on Thursday, the first of three days of official mourning for 12 people murdered by French Muslims, killers with links to both Islamic State and al-Qaeda.

On the square in front of the cathedral at noon a woman sobbed so hard that she could barely speak as she shared her umbrella with me and Laurent, a 46-year-old policeman in civilian clothing.

Nearly 1,300 years have passed since Charles Martel turned back the Islamic invasion at Tours, and there was a historic resonance to the policeman’s words.

"I refuse to allow Islamist terrorism to establish itself in France, " Laurent said. "I do not want Sharia" – Islamic law – "to be applied in France because somebody thinks the Prophet needs to be avenged for some drawings . . . Sharia is incompatible with democracy."

Amid the blur of stained glass, incense and candles inside the cathedral, Fr Emmanuel Da alluded to the atrocity. “Whatever his religion, whatever his culture, a human being is your brother, and violence is a prison,” he preached. “Harming one brother with homicidal violence is harming God. There is no act more repugnant to God than homicide.”

On Wednesday two masked gunmen had burst into the weekly editorial conference at the satirical magazine Charlie Hebdo, identified its director, Stéphane Charbonnier, shot him dead with assault rifles and then mowed down his colleagues.

The horror of the attack, says Prof Olivier Roy of the European University Institute in Florence, constitutes “a will to create a point of no return in the fracture between Islam and the West.”

Religious war?

Although there was much talk of war in Paris this week, I found no one who called it a war of religion.

“France does not have a problem with Islam. France has a problem with radicalism,” said an MBA student at Notre Dame. A retired social worker was adamant: “It has nothing to do with religion. The name of God is used by terrorists. One doesn’t kill in God’s name.” Yet the assassins shouted “Allahu akbar” (God is greatest), often uttered as a Muslim war cry, and claimed to have avenged the Prophet Muhammad.

“Everyone anticipated a religious target, for example a Christmas market,” says Prof Jean-Pierre Filiu of Sciences Po, the Paris political-studies institute. “Instead they attacked what is sacred for France: secularism and freedom of expression. With a dozen deaths they struck a severe symbolic blow that targeted, literally, the foundations of the Republic.”

Because France colonised Muslim countries, particularly Algeria, it has ended up with the largest Muslim population in Europe, estimated at five million. More citizens have joined the jihad in Syria from France than from any other European country: officially 1,132, although the real number may be far higher.

France stayed out of the 2003 invasion of Iraq and only timidly joined in the war in Afghanistan, but it is now fighting fundamentalist Islam in northern Iraq and across the Sahel region of Africa.

At present 8,000 French soldiers are deployed abroad, including 800 in the Iraq theatre and 3,000 in the Sahel. Only the US has more soldiers outside its territory.

The rise of Islamic State, the extremist group that took over much of northern Iraq and Syria last year, is a direct consequence of Washington's 2003 invasion of Iraq and of its decision not to intervene in the Syrian civil war. The attack on Charlie Hebdo brought the Middle East war to Paris.

Cherif Kouachi, the orphaned son of Algerian immigrants who is suspected of carrying out the bloody commando raid in Paris with his brother Said Kouachi, was involved with a network that sent young Frenchmen to fight the Americans in Iraq in the mid 2000s.

Like thousands of foreign jihadis, Kouachi shifted allegiance from al-Qaeda in Iraq to Islamic State. It apparently trained him in Syria, from where he returned last August. His brother Said was reportedly trained in Yemen by al-Qaeda. Police said the brothers planned and carried out the raid with the precision of soldiers.

Islamists view France as the most anti-Muslim western country, because of its colonial history, its secular ideology (the equivalent of atheism to Islamists), bans on the hijab, and French involvement in wars against radical movements.

“France claims to be a secular country when her heart is full of hatred for Muslims,” the al-Qaeda leader Ayman al-Zawahiri said in 2009, when he was still Osama bin Laden’s deputy. France would, Zawahiri predicted, “pay for her crimes”.

In recent months Islamic State has made numerous threats against France. On a jihadi website two weeks before the attack on Charlie Hebdo a French-speaking jihadi urged brethren in France to "Blow France up! Break it into smithereens. Blow off the heads of these infidels."

Charlie Hebdo had been singled out by Muslim fundamentalists since 2006, when it published Danish cartoons of the Prophet Muhammad.

A few French intellectuals, among them the philosopher Edgar Morin, questioned whether freedom of expression should include the freedom to offend. "I am of those who object to the profanation of holy objects and places," Morin wrote in Le Monde. "But of course, that in no way changes my horror and disgust at the attack on Charlie Hebdo."

Target list

The magazine's previous headquarters were burned down in 2011. In 2013 Inspire, published by al-Qaeda in the Arabian Peninsula, published a photograph of Charbonnier, Charlie Hebdo's director, the first man to be killed on Wednesday. Inspire put "Charb" on a list of nine targets to be eliminated for "crimes against Islam".

Charb’s last cartoon caricatured a Kalashnikov-toting jihadi under the heading “Still no attacks in France”. “Wait!” says the jihadi. “We have until the end of January to present our [new year’s] wishes.”

France’s war with radical Islam has evolved dramatically since 1995, when gendarmes gunned down Khaled Kelkal, the delinquent son of immigrants who planted a bomb for the Algerian Armed Islamic Group.

“There’s no place for me in France,” Kelkal had told a social worker, summing up France’s failure to integrate generations of Muslim immigrants.

In the mid 1990s French Muslims, including converts from Christianity, fought alongside coreligionists from Chechnya, Iran and Arab countries in Bosnia. Some went on to al-Qaeda training camps in Afghanistan and Pakistan, from where seven French Muslims were taken to Guantánamo after 9/11.

From 2003 the US occupation of Iraq became a new magnet for jihadis. Since 2011 the civil war in Syria and the destabilisation of postwar Iraq has opened up another front.

Cherif Kouachi, chief suspect in the Charlie Hebdo massacre, followed the classic scenario for French jihadis: an aimless youth who smoked pot, delivered pizzas and engaged in petty crime, he was converted by Farid Benyettou, an Islamist preacher in northeastern Paris.

Kouachi was prevented from travelling to Iraq in 2005 and was further radicalised in a French prison. Vincent Ollivier, his lawyer, recalled a prison visit: “He had closed up. He wasn’t the same. You couldn’t discuss anything with him.”

Most French jihadis have served time in French prisons, which are known to be breeding grounds for extremist Islam – a problem inadequately addressed by French authorities. “By throwing everyone into prison, I wonder if we weren’t making time bombs,” Ollivier said.

The attack on Charlie Hebdo appeared to follow the teachings of Abu Musab al-Suri, a Syrian-born Spanish Muslim and the author of the 1,600 page Call to Global Islamic Resistance, published on the internet a decade ago. Instead of spectacular 9/11-style atrocities, al-Suri advocates smaller, symbolic attacks carried out by autonomous cells in the West.

Targets suggested by al-Suri include Muslims who join western armed forces; Jewish children, in retaliation for Palestinian children killed by Israel; and "blasphemers" such as the staff of Charlie Hebdo.

Jihadspreading

Jihad has spread from Mauritania to the Philippines to encompass two-thirds of the globe. Seen from a Muslim point of view, they are victims.

As pointed out by the whistle-blower Glenn Greenwald in November, Barack Obama has bombed seven Muslim countries and is the fourth US president to order the bombing of Iraq. The US military historian and former army colonel Andrew Bacevich lists 14 Muslim countries that have been invaded, occupied or bombed by the US since 1980.

France is so attached to the myth of equality that it refuses to gather statistics on the number of Muslims in the country. The left almost never addresses the linked questions of Islam and immigration.

What public debate there is is prompted by the extreme-right National Front, and by writers including Alain Finkielkraut, Eric Zemmour and Michel Houellebecq. Each time they suggest that the spread of Islam in France endangers French identity, it prompts a public scandale.

"We've arrived at a point in France where you can be reproached for merely pronouncing the word 'Islam', Houellebecq told Le Figaro while promoting his new novel, Submission – about the election of a Muslim president in France – just before the attack. "Islam is not a subject that one can really debate here."

French Muslim leaders were unanimous in condemning the attack on Charlie Hebdo. Tariq Ramadan, the Oxford theologian with links to the Muslim Brotherhood in Egypt, wrote on his Facebook page: "It is not the Prophet who has been avenged. It is our religion, our values and our Islamic principles that have been sullied and betrayed."

Politically correct discourse in France constantly stresses that the vast majority of Muslims are peaceful, loyal citizens, that the killers are psychopathic criminals. Yet many Muslims nonetheless feel they’re under a cloud of suspicion, that the attack will strengthen right-wingers who equate Muslims with terrorism.

French intellectuals, including the former justice minister Robert Badinter and the philosopher Pascal Bruckner, this week demanded that French Muslims denounce terrorism.

“It hurts,” says Manigeh, a Muslim Frenchwoman. “I don’t want to condemn the attack as a Muslim but as a human being and a citizen of the French republic. No one ever asks Christians or Jews to denounce the things their people do.”

FRAUGHT HISTORY: FRANCE AND ISLAM

732 The Frankish leader Charles Martel repels the invading Muslim army near Tours, halting the Islamic conquests and preserving Christianity in Europe.

1095-1291 Crusaders are so predominantly French that the Arabic word for crusaders remains Al-Franj – the Franks.

1272 King Louis IX dies of dysentery on the ninth crusade. He is canonised in 1287.

1830-1962 French colonisation of Algeria. The 1832-47 revolt against French rule is headed by the military and religious leader Emir Abdelkader.

1954-62 France's most bitter colonial war, in Algeria, is considered a holy war by Islamists.

December 1994 The Algerian Armed Islamic Group hijacks an Air France flight with the intention of crashing it in Paris. French commandos storm the plane in Marseilles.

March 2012 Algerian-born Frenchman Mohammed Merah murders seven people in Toulouse, including three Jewish children.

May 2014 Mehdi Nemmouche, a Frenchman of Algerian origin, kills four people at the Jewish museum in Brussels.

September 2014 A group affiliated with Islamic State decapitates Frenchman Hervé Gourdel in Algeria.

January 7, 2015 Cherif and Said Kouachi, Algerian orphans who grew up in France, are accused of murdering 12 people at Charlie Hebdo.