= Prescribing a factor by elliptic-curve tripling
{title2=$E_a:y^2=x^3+ax-a,\quad P=(1,1)$}
Let $N=pq$ with <prime numbers>[primes] $p\equiv1\pmod{12}$ and $q\equiv5\pmod{12}$. <quadratic reciprocity> makes three a square modulo $p$; choose $r^2=3$ and impose $a=-3+2r\pmod p$, $a=1\pmod q$ by the <Chinese remainder theorem>. The curve has good reduction at both <prime numbers>[primes]. Indeed its discriminant is $-16a^2(4a+27)$; the first condition could make a factor vanish only at $p=3$ or 11, while the second gives $a(4a+27)=31$ and the given residue class excludes $q=31$.
Doubling $P$ gives $x(2P)-1=(a^2+6a-3)/4$. This vanishes modulo $p$ and equals one modulo $q$. Modulo $p$ one also has $y(2P)=-1$, so $2P=-P$ and $3P$ is the identity. Modulo $q$ the addition is finite. Thus computing $3P$ modulo $N$ encounters a denominator whose <greatest common divisor> with $N$ is exactly $p$, revealing the factor. The numerator difference is minus two modulo $p$, so the failed inverse cannot be cancelled. This is a construction of successful <elliptic curve method> data from prescribed local group behavior.
Back to article page
