The ones that can reply will already have your certificate (public key) stored in their address book.