New answers tagged


Initially the prizes would have been useful to prove the safety of their system. However they have driven a lot of academic effort and in effect the prizes were deemed at some stage to be counter productive I assume. This would especially have been the case if someone has made a quantum computer and factored all of the challenges in at once: dramatically bad ...


Firstly, it's not co-prime to the modulus, so $\gcd(m,N)$ would be greater than $1$. Secondly, $N$ is the product of two (and only two) prime numbers $p$ and $q$, so if $\gcd(m,N)>1$, then you know $m$ is one of the factors (and prime factors) of $N$.


We have $y^2-1 \equiv 0 \pmod n$, meaning that $y^2-1 = (y+1)(y-1)$ is a multiple of $n$. $y \not \equiv \pm 1 \pmod n$ means that neither of $y+1$ and $y-1$ is a multiple of $n$. Now, clearly $\gcd(y-1,n)$ is a divisor of $n$; we want to show that it is not $1$ or $n$. It cannot be $1$, because that would imply that $n$ divides $y+1$, which we assume is ...


No an attacker will not be able to factor your $n$ (e.g. break it). Your $n$ is of size 700 decimal digits which is $\frac{700}{\log_{10}(2)}\approx2325$ bits. Now 2048-bit moduli is the most widespread size used on the internet and hasn't seen a failure yet (without exploiting bad random number generators), so you are secure with that modulus size. As for ...

Top 50 recent answers are included