Well, by the time of the War (which, contrary to what many Frenchmen would say, certainly qualified as a war and a failed uprising), the French in Algeria already made up a good portion of the people living in Algeria (something like 1/3). They certainly didn't want to leave France, and with more Frenchmen immigrating every day, time was on the side of the French and against the Algerians.
You'd need one of two PoDs, in my opinion. Either A. One in World War 2. The French government was on the verge of surrender when the Nazis took over Paris in the 1940s, but decided to fight on and eventually evacuate to Algeria. With an official surrender, it's unlikely that you would have so many Frenchmen leaving for Algeria and bolstering the French presence their.
Alternatively, you'd need to prevent the post-war boom in population. This is going to be even harder to do- with so many fleeing Communist Germany, France's population is going to inevitably grow quickly. You'd either need a stronger Allied presence in Germany, to prop up a true German state that can take in German refugees (maybe an earlier D-Day? It would be hard to slow down the USSR when the Nazis started losing the war), the Soviets to not create conditions for the trickle of immigration (again, hard, they wanted revenge and were under Stalin at the time. People forget, but the Soviet Union of 1944 was a far different beast than the one that exists today), or for France to not have a post-war baby boom (very hard as well. The French government was supporting population growth anyways).
Of all those, getting a bigger, united Capitalist Germany would probably be the easiest. If more of Central and Northern Germany ends up under Allied control, instead of just the Rhineland, Bavaria, and Austria, the United States and Britain are probably going to keep it all together rather than split it up, offering a viable alternative to France for Germans fleeing the Soviets.
By the time the Algerian War started, France simply had too much invested in North Africa to let it go. The French public was fully behind keeping the war going, the French in North Africa especially. No matter how much funding they got from the Soviet Bloc, the Algerians were simply too disorganized and not strong enough to beat the French army. Algeria was not Vietnam.