We got strong numerical evidence that primes of the form $p=27a^2+27a+7$ are unsafe for cryptographic purposes since they can be found in the factorization.

Consider the following generic factoring algorithm for factoring $n$ which is divisible by $p$. Suppose you known an elliptic curve in Weierstrass form with known multiple $m$ of the order of $E$ modulo $p$. Let $\psi_n$ denote the $n$-th division polynomial of $E$.

Choose random integer $X$. If $X$ is the $x$ coordinate on $E$ modulo $p$ then $\psi_m(X) \equiv 0 \pmod{p}$. If it is not, $\psi_m(X)$ need not vanish modulo $p$. By selecting few random $X$ we probabilistically find $p$ from $\gcd(n,\psi_m(X))$.

This question conjectures that if $p=27a^2+27a+7$ and $\textrm{kronecker}(2k^3,p)= -1$ then the order of $y^2=x^3+2k^3$ is $p$. In this case $n$ is multiple of the order, so we can use the above algorithm by trying in addition random $k$.

We found $200$ bit factor with pari/gp in just few seconds.

Are these conjecturally unsafe RSA primes known?

  • 4
    $\begingroup$ The conjecture mentioned in the post is true, see the proof under the link given in the post. $\endgroup$
    – GH from MO
    Oct 18, 2017 at 19:03
  • 6
    $\begingroup$ It would be a terrible idea and it would raise suspicions of a deliberate trapdoor if the primes for RSA were chosen from a quadratic progression rather than randomly. $\endgroup$ Oct 18, 2017 at 20:10
  • 3
    $\begingroup$ @FelipeVoloch This is not threat to sound RSA implementation, but there is interest in mathematics and cryptography about factors which can be found efficiently. $\endgroup$
    – joro
    Oct 19, 2017 at 5:26
  • 9
    $\begingroup$ @DavyWybiral The density of primes of size about $x$ is approximately $1/\log x$, while the density of primes of size $x$ in such a quadratic progression is at most $1/({\sqrt x}{\log x})$. If primes are chosen at random this essentially will never happen. You can try for yourself to see if you find these primes in the wild. People have done large scale searches for vulnerable (against other attacks) keys in use online factorable.net $\endgroup$ Oct 19, 2017 at 7:20
  • 3
    $\begingroup$ @joro Yes, it is interesting but doesn't deserve the "unsafe RSA" clickbait title. $\endgroup$ Oct 19, 2017 at 7:40

1 Answer 1


This appears special case of "A New Special-Purpose Factorization Algorithm":


From the abstract: a new factorization algorithm is presented, which finds a prime factor $p$ of an integer $n$ in time $(D \log{n})^{O(1)}$, if $4p - 1 = Db^2$

If $p=27a^2+27a+7$ we have $4p-1=3\square$ which is covered by the paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.