Tag Info

New answers tagged


The problem is that you got the algorithm wrong. You use it to generate an integer (which is one of 1, $x-1$, or $y^{x-1} \bmod x$, and then say "prime" if that integer is prime. That's not correct; in fact, the three integers you list (90007 91571 94343) are each prime, and Miller Rabin should always return prime when given a prime. Instead, the correct ...


It has to do with the Diffie–Hellman assumption. The DH key exchange is secure in groups where the computational DH assumption holds. One of the simplest such groups is the multiplicative group modulo a large prime. However, that is not necessarily required. At least some composite integers with unknown factors would make a secure Diffie–Hellman modulus, ...


Now that of course gets more complicated with bigger numbers too, but still quite easy/fast. So basically if those numbers are not primes, that you can just split up $n$ as much as possible and from there you have an easier way to find $p$ and $q$. If both are primes you have to try values for $p$ and $q$ until you find exactly the right values.

Top 50 recent answers are included