No sooner had we started exploring our surroundings and naming the birds and the beasts, than Peter Shor put an end to that apparent innocence by showing that factoring could be turned—by means of quantum hardware—into a po- nomial task.