Device, system, and method of generating and handling cryptographic parameters. A first device and a second device store the same secret seed value, utilize the same deterministic pseudo-random number generation function, and utilize the same deterministic value modification function. The first device generates a candidate value, sequentially modifies its value, and performs primality testing until a confirmed prime number is found. The first device indicates to the second device, how many iterations of value modifications to perform in order to reach and thus re-generate therein the same already-confirmed prime number, without the need to perform any primality testing in the second device.