Tag Info

New answers tagged


Consider the discrete logarithm problem. If the group order does not contain large prime factor, you can solve the problem for each of small prime factors and "combine" them into the full solution. So, it can be described that here primes are needed because they can't be divided into smaller things.


For many areas of encryption, you actually DO want as truly random of a value as possible. Primes (or more accurately, relative primes) only enter in to the equation when dealing with certain forms of asymmetric encryption. Asymmetric encryption is where one person has a public key to encrypt a message and then the recipient has a different private key ...


In RSA, exponents are small, so the encryption/decryption can be done quickly. Here, exponent is of the form $2^t$, where $t$ is very large. For example, consider RSA 2048 - exponents have at most 2048 bits. If you set $t=2048=2^{11}$, then to solve this puzzle one will need to do only 2048 squarings, roughly the same as you need to do a decryption in RSA. ...


Hint: modular inverses are unique, therefore the following holds: $$2^x \equiv 3 \pmod{p} ~ ~ \iff ~ ~ 2^{-x} \equiv 3^{-1} \pmod{p}$$ Now what is the inverse of $3$ modulo this particular $p$? Can you express it as a power of two modulo $p$? Solve for $x$. If you end up with a negative $x$, use Fermat's little theorem to derive a positive exponent.

Top 50 recent answers are included