It seems to me like to not get public key cryptography you would need math to be different

Just because the equations would have to be the same, it does not mean the other society would know them and use them like we do. Maybe they don't have Internet yet. Maybe their version of Internet has some (weaker) form of cryptography in the lower layers, so inventing cryptography for higher layers did not feel so necessary. Maybe they researched quantum physics before Internet, so they use quantum cryptography. Or at least they can use different kinds of functions for private/public key pairs.