Brute-forcing a n bit symmetric cipher like AES doesn't take O(2^n) steps to break worst-case, but it takes O(2^(n/2)) steps. So it's a reduction from 2^128 to 2^119 in the case of AES-256. Not from 2^256 to 2^119.

It takes 2^128 instead of 2^256 because of the birthday paradox.

Indeed, any piece of fiber which isn't of very good quality will reflect part of the transmitted optical signal. By measuring these reflections with an OTDR like you said, you can pin-point the exact location of the damaged fiber. Even a splice of very good quality creates a little loss (about 0.10 dB), which you can measure.

Measurement with an OTDR is basically an optical radar. Send out an optical pulse and measure what comes back. Do some heavy math and you can plot signal loss vs cable length.

One hard part of this is that you need the exact refractive index of the glass you used (and you need several decimals...). This refractive index is used to calculate the distance the light has traveled before reflecting. If this index is just a bit off, then you're off hundreds of meters.

They cut the cable in half, and put a new piece in it. They can locate the exact point of failure using an OTDR, as already mentioned in other comments by now.

In one such big under-sea cable, there could be hundreds of individual fibers inside. (It doesn't cost alot more to put another fibre in the big cable, and you get alot more bandwidth to sell).

For each fiber inside the cable they "weld" it to the new piece they are putting between. (I'm sorry, I don't have the correct translation for the word in English). But really, they put the fiber in a machine, together with the fiber of the new cable they are putting in between, and they hit a button: "weld". It creates an arc through the point where the fiber needs to be welded together. After the arcing you heat that spot so the atomic structure can repair a little.

Repeat 500 times and put some extra mechanical protection around to protect your welding, and you're done.

There exists equipment that can do multiple fibers at once, so basically the engineer who's doing it just needs to place both ends of the fibers in the machine, hit the button, remove fiber and repeat for a day or 2.