New answers tagged


The quote invites computing $5\,P$ on the Elliptic Curve of equation $E:\ Y^2\equiv X^3+3X+7\pmod{11}$ in order to experimentally come to the realization this is the point at infinity $\mathcal O$ (the neutral of point addition), and get the intuition that's why the computation of $5\,P$ on the Elliptic Curve of equation $E:\ Y^2\equiv X^3+3X+7\pmod{187}$ (...


If $k$ is the same in the two forms, that is $n=(4k+3)(4k+7)$, factorization is trivial: $p=\lceil\sqrt n\,\rceil-2$, $q=p+4$. Assuming the two $k$ are independent from now on: note that for odd primes $p$ of a given size, the quantity $p\bmod4$ is about evenly split in $\{1,3\}$. Thus the known form gives one bit worth of information about $p$. We get that ...


From Fermat's little theorem we know $$ a^p \equiv a \pmod{p}\,. $$ Applying this to the present problem, $c^p \equiv c \equiv x \pmod{p}$, and thus $p = \gcd(x - c, n)$.

Top 50 recent answers are included