instale o apt-file
$ sudo apt-get install apt-file
atualize o apt-file
$ sudo apt-file update
pesquise o pacote ao qual um arquivo pertence
$ apt-file search filename
encontre o caminho do executável
$ whereis rename
rename: /usr/bin/rename.ul /usr/bin/rename /usr/bin/X11/rename.ul /usr/bin/X11/rename /usr/share/man/man1/rename.1.gz /usr/share/man/man2/rename.2.gz
pacote de pesquisa
$ apt-file search /usr/bin/rename
ladr4-apps: /usr/bin/renamer
util-linux: /usr/bin/rename.ul
o nome do pacote é: util-linux