The Tunisian man who killed three people in a French church only recently arrived in Europe, officials say.

The suspect, 21, had an Italian Red Cross document, issued after he arrived on the Italian island of Lampedusa by migrant boat last month.

He was shot by police and is in a critical condition. One of the victims was "virtually beheaded", said the French chief anti-terrorism prosecutor.

President Emmanuel Macron said it was an "Islamist terrorist attack".

Mr Macron said the number of soldiers being deployed to protect public places - such as churches and schools - would rise from 3,000 to 7,000. Anti-terror prosecutors have opened an investigation, and France has raised its national security alert to the highest level.

In another development, a 47-year-old man believed to have been in contact with the attacker was detained by police late on Thursday, French media reported.

Thursday's stabbings at a church in the southern French city of Nice have echoes of another attack earlier this month near a school north-west of Paris. Samuel Paty, a teacher, was beheaded days after showing controversial cartoons of the Prophet Muhammad to some of his pupils.

That murder has heightened tensions in France. Mr Macron's defence of the right to publish the cartoons and the government's attempts to crack down on radical Islam have angered Turkey and other Muslim-majority countries.

The suspect in the Nice attack was heard repeatedly shouting "Allahu Akbar" (God is greatest) before being shot by police.

A Koran, two telephones and a 30cm (12-inch) knife were found on the attacker, said French chief anti-terrorist prosecutor Jean-François Ricard.

"We also found a bag left by the attacker. Next to this bag were two knives that were not used in the attack," he added.

Police sources named the attacker as Brahim Aouissaoui.

The suspect is in a critical condition in hospital, Mr Ricard said.

Speaking after visiting Nice, Mr Macron said: "If we are attacked once again it is for the values which are ours: freedom, for the possibility on our soil to believe freely and not to give in to any spirit of terror.

"I say it with great clarity once again today: we won't surrender anything."

Two other attacks took place on Thursday, one in France and one in Saudi Arabia.

A man was shot dead in Montfavet near the southern French city of Avignon after threatening police with a handgun.

A guard was attacked outside the French consulate in Jeddah in Saudi Arabia. A suspect was arrested and the guard taken to hospital.

All three were attacked inside the basilica on Thursday morning before the first Mass of the day.

Two died inside the church: a 60-year-old woman who was "virtually beheaded", and a 55-year-old man whose throat was cut.

The male victim was a lay member of staff responsible for the upkeep of the church. He reportedly had a wife and two children.

Another woman, aged 44, fled to a nearby cafe with multiple stab wounds but died shortly afterwards. "Tell my children that I love them," she told those who tried to help her, according to French media.

It later emerged that a witness had managed to raise the alarm with a special protection system set up by the city.

Chloe, a witness who lives near the church, told the BBC: "We heard many people shouting in the street. We saw from the window that there were many, many policemen coming, and gunshots, many gunshots."

Four police officers arrived at the scene at 08:57 local time (07:57 GMT) and the attacker was shot and detained shortly afterwards, the anti-terrorist prosecutor said.

Four years ago Nice was the scene of one of France's worst jihadist attacks, when a Tunisian drove a truck into crowds celebrating Bastille Day on 14 July, killing 86 people.

Governments around the world have condemned Thursday's attack, including France's European neighbours, the US, Turkey, Egypt, Qatar and Lebanon.