C'est pas une translation qu'il faut, c'est une homothétie par rapport à la fréquence 0 (la relation hauteur de note -> fréquence correspond à une suite géométrique, pas arithmétique).
Tu peux utiliser la FFT pour ça mais ça revient au même de le faire directement en domaine temporel et c'est pas plus compliqué.
Là où c'est vicieux, c'est que le problème est mal défini. Hauteur et tempo sont des concepts humains, pas physiques : un truc périodique à 2 Hz sera perçu comme un tempo, un truc périodique à 2 kHz sera perçu comme une hauteur. En gros, faut que les les propriétés du signal à court terme soit modifiées sans que celles à long terme le soient.
L'une des méthodes les plus simples pour ça consiste à découper le son en petites "granules" de quelques ms de long qui se recouvrent partiellement, avec un fondu de volume progressif au début et à la fin de chacunes pour éviter les cliquetis. Ensuite on étire ou on compresse ces granules suivant ce qu'on veut obtenir.
Le mieux est de choisir une longueur de granule qui soit un multiple de la période correspondant à la fréquence fondamentale du signal à ce moment-là.
Ça marche pas trop mal pour les sons harmoniques monophoniques (instruments de musique, voix unique) et tant qu'on ne change pas la hauteur de plus de quelques demi-tons. Pour des changements plus grands ou des cas plus compliqués (percussions, polyphonie), c'est pas terrible, et là faut sortir des algos plus balèzes (dont certains sont jalousement gardés par les fabricants de racks d'effets et de plugins audio).
Y'a un autre problème rigolo avec le pitch-shifting : le fait que pour la voix humaine, il y ait des résonances à certaines fréquences qui sont indépendantes de la hauteur du chant. On appelle ça des formants, et c'est un des trucs principaux qui permet de différencier une voix d'homme d'une voix de femme même s'ils chantent à la même hauteur. C'est aussi pour ça qu'un enregistrement accéléré donne une voix de stroumph au lieu d'être simplement plus aigü

(y'a moyen de compenser ça avec un algo, mais je me rappelle plus comment ça marche)
EDIT : cross partiel avec Sally