JERUSALEM (AP) — The contours of the prisoner swap deal between Israel and the Hamas militant group have long been known: Israel would free hundreds of Palestinian prisoners in exchange for an Israeli soldier held in the Gaza Strip.

But it required a unique set of circumstances, ranging from domestic problems on both sides to a revolution in neighboring Egypt, for the agreement to materialize.

The two bitter enemies announced the deal nearly simultaneously Tuesday, ending a painful five-year saga surrounding Israeli Sgt. Gilad Schalit, captured in a cross-border raid and dragged into Gaza in June 2006. For his return Israel will free more than 1,000 prisoners.

The deal gives each side enough to claim victory.

Israel's embattled prime minister, Benjamin Netanyahu, can say he brought home a soldier whose plight had become a national obsession. Hamas, locked in a rivalry with Palestinian President Mahmoud Abbas, can boast of the most lopsided exchange ever in the region.

Yet each made painful concessions that until recently might not have been possible.

Among the Palestinian prisoners are some 300 serving life sentences for involvement in deadly attacks on Israelis — a Hamas achievement since Israel has historically balked at releasing those with "blood on their hands." But the best-known prisoners, including an uprising leader and a bombing mastermind, will remain in jail.

For Netanyahu, who has built his career as a hard-liner on terrorism, any deal at all was bound to be a bitter pill. Some Israelis had hoped Schalit might be freed in a daring raid of some sort. But memories are still fresh from a botched 1994 effort to free another kidnapped soldier, Nachshon Wachsman, who was killed along with one of the commandos who tried to rescue him.

Piling on the pressure was the grim case of Ron Arad, an air force navigator who was captured in 1986 after his aircraft was brought down over Lebanon. Arad was seen being taken alive by Lebanese guerrillas but his traces vanished shortly thereafter, fueling a bitter sense in Israel that the country failed to seize the moment and bargain for his release.

Netanyahu acknowledged he had no magic formula for such cases.

"I believe we got the best deal that we could get, considering the storms of the Middle East," he said of the Schalit swap. "I don't know if we could have gotten a better deal, or a deal at all, in the future."

To an extent, his hands were tied: Israel has a long history of lopsided prisoner swaps, so Palestinian expectations were high.

And Netanyahu was desperate for a concrete accomplishment at a time of growing criticism over deadlock with the Palestinians, social protests over the country's high cost of living and diplomatic crises with Egypt, Turkey, and even the United States.

Hamas, for its part, has also been on the defensive.

The group, which violently seized power in Gaza in 2007, has seen its popularity wane in the face of continued Israeli military and economic pressure. The country that hosts its headquarters, Syria, is facing global condemnation for the bloody suppression of its domestic uprising.

And for all its fiery rhetoric and calls for Israel's destruction, Hamas has become alarmed by the sudden rise in popularity of its rival, Abbas.

Palestinians have rallied around their president since he asked the U.N. Security Council to recognize Palestinian independence last month, defying the wishes of Israel and the United States. For many, Abbas' dramatic speech at the U.N. turned the normally dour 76-year-old, affectionately known as Abu Mazen, into a hero.

"Hamas felt it was isolated and on the sideline after Abbas' speech," said Mkhaimar Abusada, a prominent Gaza political scientist. "Hamas wanted to try to seize the spotlight from Abu Mazen, and from the popularity that Abu Mazen earned."

In Washington, White House press secretary Jay Carney said the Obama administration was "pleased by the report that Mr. Schalit will be home soon."

"The president, as you know, has called many times for his release and his release is long overdue," said Carney, who reiterated that the White House focus is for the Palestinians and Israelis to take steps toward direct negotiations.

Yoram Cohen, the head of Israel's Shin Bet security agency, told reporters he sensed a breakthrough was near in July when Hamas made two key concessions.

First, it accepted Israel's demand that several prisoners would not be freed under any circumstances. They included Marwan Barghouti, an uprising leader who is serving multiple life sentences for his role in deadly attacks on Israelis; Ahmed Saadat, a faction leader who is imprisoned for involvement in the 2001 assassination of an Israeli Cabinet leader; and Hamas bomb maker Abdullah Barghouti, who is serving 60 life sentences.

Second, Cohen said Hamas agreed to Israel's demand that some 250 freed prisoners not be allowed to return to their homes in the West Bank, where they might more easily carry out new attacks on Israeli targets.

Most of these prisoners will be sent to the Gaza Strip, which is effectively sealed off from Israel by a fence, and some 40 will be deported from the area altogether. Among these are Amna Muna, a woman who met an Israeli teenage boy over the Internet and lured him to the West Bank, where he was killed by waiting militants.

The group's exiled leader, Khaled Mashaal, conceded that he had not been entirely successful. "This deal was not easy. We waged fierce battles. That is why we were years late, because the enemy maneuvered and procrastinated," he said.

Lurking in the background of the negotiations was the Egyptian revolution, which ousted longtime President Hosni Mubarak in February.

Both Israel and Hamas have been scrambling to adjust to the new order.

Hamas may have shown new flexibility in its quest for good relations with its southern neighbor, while Israel was also eager to maintain strong ties with an important Arab ally. Israeli leaders went out of their way to thank Egypt for brokering the deal.

"They took the matter very seriously and were fully engaged," said Cohen, the Israeli security chief.

With momentum back on its side, Hamas can hope to regain the upper hand in its rivalry with Abbas' Fatah movement. The two sides have been at odds since Hamas seized control of Gaza and repeated reconciliation attempts have stumbled.

Following the announcement of the prisoner deal, a senior Fatah official, Azzam al-Ahmed, said Wednesday that a new round of reconciliation talks would begin later in the day in Egypt, said the Palestinian news agency Wafa. Yet it seems that after the past month's events, the divisions between the sides are only deeper, and chances for a breakthrough are dim.

A stronger Hamas also bodes poorly for peace prospects with Israel.

Abbas has refused to negotiate unless Israel ends settlement construction in the occupied West Bank and east Jerusalem — and he is even less likely to resume peace talks at a time when Hamas' confrontational approach is yielding dividends. This could explain the Palestinians' cool response to a new American invitation to resume negotiations at a meeting in Jordan later this month.

___

AP reporters Ibrahim Barzak in Gaza City, Mohammed Daraghmeh in Ramallah and Diaa Hadid in Jerusalem contributed to this report.

___

EDITOR'S NOTE — Josef Federman is AP's news editor in Jerusalem. Dan Perry is the bureau chief for Israel and the Palestinian territories.