I believe, though I haven't done much with real complexity theory, that most feel P=BPP, and problems like the one you describe can be converted into more typic

I believe, though I haven't done much with real complexity theory, that most feel P=BPP, and problems like the one you describe can be converted into more typical BPP problems. It's unproven, like most of the fun problems, but it's suspected. Regardless, this definitely isn't a result with much to say about practical cryptography, and it wasn't trying to be one. Just another, very interesting link in a field with lots of "if pigs could fly" proofs.