77

No. If the claim was true, then there would be an extremely simple way to prove it: $10^{10}$ arithmetic operations is nothing. There are tons of 800-bit factoring challenges available online. The author could just solve them and include the factorization in the submission; the lack of such a straightforward validation should be taken as empirical evidence ...


49

Mental calculators do not have the result appearing in their brain by staring at the input. They follow some (broadly sequential) algorithm¹. And computers vastly outperform them when they use the same algorithm. That was already by at least a factor >100 for inexpensive personal computers in the late 1970s. For example, the record for 10 multiplications ...


44

Those appear to be based on the complexity of the General Number Field Sieve, one of the fastest (if not the fastest) classical factoring algorithms. I confirmed this in Mathematica. Here is the complexity for the GNFS (source): $$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$ where $n$ is a ...


44

That number was so quick to factor because its factors are extremely close together, i.e., it factors as $\left(\lfloor\sqrt{n}\rfloor + 70\right)\left(\lfloor\sqrt{n}\rfloor - 68\right)$. Some algorithms, like Fermat's, which work best the closer together the factors are, will find this factorization instantly.


42

I've never heard that RSA becomes less secure when the modulus grows. Obviously the strength doesn't grow as fast as the number of bits, but that only means that it grows sub-exponentially. If it keeps growing (without the growth going near zero) then there is no "trap". Check for instance here where the conclusion is that there is no exponential growth but ...


40

Big issue at the bottom of page 2 where the determinant is quoted as $N^{n+1}\frac{n(n+1)}2 \ln n$ when it should be $N^{n+1} n! \ln n$. If this formula is used directly in the numerical estimates then are likely to be highly inaccurate. UPDATE (5th March): I've taken a bit more time to work through the paper in detail. There's no asymptotic analysis of the ...


26

2) Has anyone claimed to make any progress with this challenge? Ah that question I can answer now... I found the solution on the 15th of April 2019 and sent it to the MIT's CSAIL on the 16th of April. Another team shall have the answer by the 11th or 12th of May (they used a FPGA). I noticed around the end of 2015 that if I used GMP I could find the ...


26

I don't understand at all what this claim is on the website. The claim that RSA becomes very expensive for large $N$ is true, but to say that the gap between encryption/decryption cost and factoring goes down makes no sense at all! The function describing the running time of the best factoring algorithms is clearly asymptotically larger than $n^3$ (the time ...


23

The error in upper bounding the determinant of the matrix $\mathbf{R}_{n,f}$ by $$N^{n+1} \frac{n(n+1)}{2} \ln N$$ instead of by $$N^{n+1} n! \ln N$$ seems to lead to an error in upper bounding the initial short vector by $$\Vert \mathbf{b}_1 \Vert< \exp(2 \ln n/2)$$ instead of by $$\Vert \mathbf{b}_1 \Vert< \exp(\ln n)$$ which is an exponential ...


20

Your thinking is against the common sense in cryptography and computing. And to be blunt, it's blatant pseudoscience. Human brains and the neurons within operate on scalar states. While it's arguable whether the brain process is deterministic or probabilistic, it does not possess the capability to create state superpositions like quantum computers could. ...


18

RSA-768 took 2000 years of 2.2Ghz single-core Opteron from the year 2009. DJB et al wrote in 2013 (see page 30) (see also: 29C3: FactHacks (EN); slide 87/112; about 10 minutes) that RSA-1024 would take $2^{70}$ differences with $2^{24}$ per machine per second in 2009, so 2 million years. Hardware improved since then, and GNFS can use GPUs, so maybe better, ...


16

Actually, the problem is that the above quote uses the term "discrete log" in a way that's different from what you're thinking of. When someone uses the term "discrete log", they can mean two things: A discrete log in the group $Z^*_p$; that is, given $p$, $g$ and $g^x \bmod p$, recover $x$ A discrete log in some other group; that is, given a group $G$, a ...


16

First we may want RSA primes to be something like a safe prime, ie a prime $p$ where $(p-1)/2$ is prime as well. Back in 1974 Pollard found an algorithm to factor moduli whereby you can factor $N=pq$ if $p-1$ or $q-1$ are smooth, that is all prime-factors of $p-1$ or $q-1$ are smaller than a bound $B$. The algorithm will then factor $N$ in time $\mathcal O(...


16

The bozos at Clown Sterling have adapted the advanced technology of bogosort to factoring: randomly blow a candidate solution out your nose and check whether it works. For a semiprime $n$ chosen by modern RSA key generation methods, there are approximately $\sqrt n$ candidate solutions to check, which is also the expected cost of this method. For instance, ...


15

Proving P=NP would not necessarily give you an algorithm, because there are many different methods to prove something (i.e. Direct proof, Proof by contradiction, etc.). But it is shown that if you were to find a polynomial time algorithm to solve a NP-complete problem that you could modify that algorithm to solve all NP-problems, including the Integer ...


15

Your 102-digit nuber is two digits more than the first RSA challenge RSA-100 that has 330-bit. This can be easily achieved with existing libraries like; CADO-NFS ; http://cado-nfs.gforge.inria.fr/ NFS factoring: http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html Factoring as a service https://seclab.upenn.edu/projects/faas/ The Factoring as a ...


14

If $p=2q+1$ is a safe prime (that is, $q$ is a prime as well), then $p-1=2q$ has exactly two prime factors: $2$ and $q=(p-1)/2$.


14

I'm one of the authors of the paper. In order to make the paper more approachable, we factored each major optimizations out into its own paper. There are three of these sub-papers, and they each stand on their own mostly independent of the others. "Approximate encoded permutations and piecewise quantum adders ". We put small amounts of padding at various ...


14

There is no proof that the integer factorization is computationally difficult and similarly, there is no proof that the RSA problem is similarly difficult. The RSA problem RSA problem is finding the $P$ given the public key $(n,e)$ and a ciphertext $C$ computed with $C \equiv P^e \pmod n$. Factoring $\implies $ the RSA problem This is the easiest part. If ...


13

Algorithm An RSA modulus $N$ product of large distinct primes can be factored given $(N,e,d)$ per: Compute $f\gets e\,d-1$, and express $f$ as $2^s\,t$ with $t$ odd Set $i\gets s$ and $a\gets2$ Compute $b\gets a^t\bmod N$ , and if $b=1$ then set $a$ to the next prime, and proceed at 3 If $i\ne1$ then compute $c\gets b^2\bmod N$ , and if $c\ne1$ then ...


12

If the RSA keys were generated randomly, then it is inconceivable that two different devices would happen to pick the same key. Taking 2048 bit RSA keys as an example, there are approximately $2^{1014}$ 1024 bit primes; if we consider them pairwise (and realise that about half the pairs yield a 2047 bit number), that means there are about $2^{2026}$ RSA ...


12

The IEEE paper is silly. The factorization method they give is quite slow, except for rare cases. For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 seconds to factor a 67 bit number; well, I just tried it using a more conventional algorithm, and it took 6msec; yes, that's 100,000 times as fast...


12

might have the terminology wrong when I say "GF(2) polynomial multiplication" You are thinking of multiplication in the ring of binary polynomials, that is polynomials with coefficients in the Galois Field with 2 elements. That set is noted $GF(2)[x]$. It's addition reduces to XOR of the coefficients of equal weight. It's multiplication is called &...


12

No, it's not proved that solving the RSA problem [that is, finding $x$ from the value of $x^e\bmod n$ for unknown random integer $x$ in interval $[0,n)$, and $(n,e)$ a proper RSA key ] is equivalent to factoring. It's even widely believed that does not hold, for $e$ of fixed magnitude (as used in practice) in particular. Trivially, ability to factor implies ...


11

Bill Garsarch just posted about this the other day. The short answer is that there is an explicit algorithm, which is known today, such that if P = NP (or even just FACTORING ∈ P) then the algorithm solves factoring in polynomial time on all instances. However, this algorithm is utterly infeasible for real-world computation because it works by iterating ...


10

No, there is no specific vulnerability associated to choosing $p$ and $q$ with size differing by $i$ bits (or $2\cdot i$ bits as in the statement) for small $i$. However, if $i$ gets too big: That improves the odds that ECM will manage to factor $n$ for some fixed size of $n$, and at some point ECM will become the best algorithm; this is the case if $i$ is ...


10

Yes, they are (deterministically) equivalent. The original RSA paper (Section IX.C), working off Miller's results (Theorem 3), showed how knowing the secret exponent $d$ was probabilistically equivalent to factoring $n$. Later, using more advanced techniques, Coron and May showed how to deterministically reduce finding $d$ to factoring $n$.


10

Breaking such a scheme is easy. Suppose Alice wants to transmit a message $M$ to Bob. First thing, Alice picks an integer $R_a$ and sends the cipher text $C_a = M \times R_a$ to Bob. Bob then picks another integer $R_b$ and transmits $C_b = C_a \times R_b$ back to Alice. Alice calculates $D_a = \frac{C_b}{R_a}$ and sends $D_a$ to Bob. Bob calculates $D_b = ...


10

For human brains, it's all too easy to ignore the depth of the 2048+ bit figure. Let's do some engineering guesstimation exercise to illustrate. The original post by @derjack measures almost 700 characters long. Here's a 2048-bit number, written in 617 decimal digits (almost as long as the question): ...


9

The Prime Number Theorem proves that there are approximately $\frac{x}{\ln x}$ primes less than any positive integer $x$. There are thus about $\frac{2^{2048}-1}{\ln (2^{2048}-1)}-\frac{2^{2047}}{\ln (2^{2047})}=22.8\times 10^{612} - 11.4\times 10^{612}=11\times 10^{612}$ 2048-bit primes. That's a rather large number, since there are only about $10^{80}$ ...


Only top voted, non community-wiki answers of a minimum length are eligible