Return to Question

We got strong numerical evidence that primes of the form $p=27a^2+27a+7$ are unsafe for cryptographic reasons 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?

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?

We got strong numerical evidence that primes of the form $p=27a^2+27a+7$ are unsafe for cryptographic reasons 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 $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?

We got strong numerical evidence that primes of the form $p=27a^2+27a+7$ are unsafe for cryptographic reasons 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?