New answers tagged


Consider two numbers $a$ and $b$ that square to the same value modulo $n$ and don't just differ by the sign. $$a^2 \equiv b^2 \pmod n2$$ $$(a-b)(a+b) \equiv 0 \pmod n$$ Neither of the factors on the left is 0 (or equivalently a multiple of $n$), thus each of them must contain one of the prime factors of $n$. Thus you can use $\operatorname{GCD}(a-b, n)$ ...


Hello, welcome to crypto.SE. This is not cryptography, but I will answer it with a simplified example to give you the intuition. Lets consider $123 \times 456$. 123 x 456 ----- 738 615 + 492 ------- 56088 Right ? How did you get $738$? Obviously you did $6 \times 3 + 6 \times 20 + 6 \times 1$. Therefore you made 3 multiplications. ...


Add the two numbers, and keep only the lower 4 digits. To reverse, add 10000 then subtract the second number and keep only the lower 4 digits again. Works like a charm.


I'll give a brief and simple example of what is described in the quote, which is now known as RSA for which there are plenty of descriptions and tutorials for all levels of understanding as pointed out by yyyyyyy. ... so I thought of the product of two primes ... So, for our example this will be $p=21$ and $q=23$ of which the product is $n=21\times ...

Top 50 recent answers are included