2
$\begingroup$

I was wondering if it is possible to solve the discrete logarithm on an Elliptic Curve E(Z/nZ) (defined over the ring of integers modulo a composite n) with #E(Z/nZ)=n by applying a method analogous to the Semaev, Satoh-Araki, and Smart attack for anomalous elliptic curves over prime fields.

$\endgroup$
0

2 Answers 2

3
$\begingroup$

The condition $\#E(\mathbb{Z}/n\mathbb{Z}) = n$ is not enough, I believe. You would need that $E(\mathbb{Z}/p\mathbb{Z})$ is cyclic of order $p$ for all prime divisors $p$ of $n$.

By the Chinese Remainder Theorem, we have $E(\mathbb{Z}/n\mathbb{Z}) = \prod_{p\mid n} E(\mathbb{Z}/p^{k_p}\mathbb{Z})$ where $k_p=\operatorname{ord}_p(n)$. That reduces the problem to prime powers. If $E(\mathbb{Z}/p\mathbb{Z})$ is cyclic of order $p$, then you can use the $p$-adic logarithm to solve $E(\mathbb{Z}/p^{k_p}\mathbb{Z})$, too.

Now if $n=pq$ for two distinct primes and $E(\mathbb{Z}/p\mathbb{Z})$ has $q$ elements then the $p$-adic logarithm won't help to solve the discrete logarithm there.

This means that the naivest version of using the same idea only works in special cases. But maybe I am missing something.

$\endgroup$
1
  • $\begingroup$ I believe you can factor $n$ since you know multiple of the order mod p. $\endgroup$
    – joro
    Mar 15, 2014 at 10:01
0
$\begingroup$

I believe you can factor $n$ if you know such curve.

Assume $n$ is odd. Reason mod $p$. since $n=pq$, you know a multiple of the order (no matter if the order is $p$ or $q$).

Compute the division polynomial $\psi_n(u) \pmod n$ for random $u$.

$\psi_n(u) \equiv 0 \pmod{p}$ iff $u$ is $x$ coordinate in $\mathbb{F_p}$ which happens half the time.

If $u$ is $x$ coordinate mod $p$ but not mod $q$ you find $p$ by computing $\gcd(\psi_n(u) \mod n,n)$.

Here is sage code:

def molog():
    p=113
    q=131
    K=GF(p)
    Kq=GF(q)
    E=EllipticCurve(K,[40,54])
    Eq=EllipticCurve(Kq,[7,62])
    print 'order=',E.order(),Eq.order()
    n=p*q
    for u in [ 1 .. 20]:
            dp=E.division_polynomial(n,u)
            dq=Eq.division_polynomial(n,u)
            print u,'mod p',dp,'mod q',dq

pari/gp example:

? p=113;q=19;a=chinese(Mod(40,p),Mod(16,q));b=chinese(Mod(54,p),Mod(12,q));n=p*q;E=ellinit([0,0,0,a,b]);N=p*q;u=1;dp=SLPDivisionPolynomial(a,b,u,N);g=gcd(lift(dp),N);g
%62 = 113
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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