In #234 we had some people confused about signature verification failing with ::new, and they had trouble discovering ::new_with_prefix.
It would be good to either improve the documentation here, or eliminate the distinction between ::new and ::new_with_prefix and automatically determining if the prefix is needed (e.g. based on the OID of the provided digest).
It seems like other RSA libraries are able to make this determination automatically.