New answers tagged

1

This is for completeness and a complement to the nice answer above. The $n^{th}$ prime number $p_n$ is not known for large $n$. The best unconditional bounds (i.e., without assuming unproved hypotheses such as the Riemann Hypothesis) are are due to Dusart $$ n\left(\ln n+ \ln\ln n-1+ \frac{\ln \ln n -2.1}{\ln n}\right)\leq p_n \leq n\left(\ln n+ \ln\ln ...


4

No. The only plausibly relevant major cryptosystems involving that are RSA-based cryptosystems. A typical RSA prime is chosen uniformly at random from 1024-bit primes, of which there are $\pi(2^{1024}) - \pi(2^{1023}) \approx 2^{1014} - 2^{1013} = 2^{1013}$ possibilities, by the prime-counting approximation $\pi(x) \approx x/\!\log x$. Even if you could ...


6

Efficient is not sufficient in cryptography. You also need secure computation. Consider a standard repeated squaring implementation in Python; def fast_power(base, power): result = 1 while power > 0: # If power is odd if power % 2 == 1: result = (result * base) % MOD # Divide the power by 2 power = ...


8

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? No. Factoring numbers with special forms like that is easy. You have a Mersenne number, $n = 2^e - 1$, whose exponent $e = 2048$ is composite. Whenever $e = u v$, we have $2^u - 1 \mid (2^u)^v - 1 = 2^e - 1$, since in general $x - 1 \mid x^k - 1$. (...


1

Yes. You don't need to wait until the end of the computation to compute the remainder, you can do that in each step of the exponentiation; this way, the largest numbers you'll need to handle are twice the size of n. There are many algorithms to compute the exponentiation itself, the simplest is square-and-multiply.


Top 50 recent answers are included