2
$\begingroup$

Let $A$ be an abelian variety over $\mathbb{F_q}$ with dimension $n$. Let $q$ be a constant. Is there polynomial algorithm of finding discrete logarithm in $A$?

UPD: really I don't undestend: can we polynomial fast calculate $P+Q$ if $P, Q \in A$ (as it is in case of elliptic curve)?

$\endgroup$

1 Answer 1

3
$\begingroup$

For the original question, which I understand to be whether there is an algorithm, which is polynomial time in $n$ that computes discrete logarithms on an abelian variety of dimension $n$ over a finite field of $q$ elements, where $q$ is fixed, the answer is no. This problem has been studied in the context of the Weil descent attack, which reduces discrete logs on an elliptic curve over a finite field of $q^n$ elements to the above situation. See the book of S. Galbraith "Mathematics of public key cryptography".

The second question is much more basic, how to compute addition on an abelian variety as above. The answer depends on the description of the abelian variety. If you want a projective embedding and a complete group law, this will require exponentially many variables but you can get away with a group law defined on an open subset and that I believe is polynomial in $n$. I don't think there is any systematic research on this general problem. If the abelian variety is given as a quotient of a Jacobian, then there are, I believe, algorithms. Have a look at Galbraith's book mentioned above.

$\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.