Oh, they also said to ignore State Street, the precedent that upholds software patents. But they're just the Supreme Court. Nobody listens to them in this area anyway. I know I sound sarcastic, but I'm serious.
Go to court in East Texas and persuade a jury that a bunch of damn Yankee judges up there in Washington know better than an honest American corporation.
Algorithm patents are allowed in most countries, contrary to popular belief; when most people talk about "software patents" they are actually talking about business process patents which rarely exist outside the US. Actual algorithms are recognized as a direct abstraction of electronic circuit designs and electronic circuit designs are widely recognized as patentable subject matter.
(Any consistent application of an "algorithms are mathematics" argument would exclude all currently patentable subject matter, for better or worse. I do not have a strong opinion one way or the other but it is worth pointing out because this fact is lost in many discussions of patents.)
The RSA patent didn't make it through the patent system by claiming a particular algorithm; it made it through by including the hardware: http://en.wikipedia.org/wiki/RSA_(algorithm)
See also http://en.wikipedia.org/wiki/Freeman-Walter-Abele_Test
Insane, yes, but upheld by current precedent.