4
$\begingroup$

Quoting Wikipedia on Algebraic-group factorisation algorithm

Algebraic-group factorisation algorithms are algorithms for factoring an integer N by working in an algebraic group defined modulo N whose group structure is the direct sum of the 'reduced groups' ... The aim is to find an element which is not the identity of the group modulo N, but is the identity modulo one of the factors

To our knowledge current implementations work only on groups of elliptic curves or primitively of $(\mathbb{Z}/N\mathbb{Z})[x]/f(x)$ and hyperelliptic curves are only of theoretical interest.

For the elliptic curve factorization method the order of the group is close to $p$ for a prime factor $p$ of $N$.

Q1 Are there other groups suitable for practical algebraic group factorizations of integers?

Q2 Are there groups of order $o(p)$? (small Oh on purpose).

Q3 Are Abelian varieties candidates?

$\endgroup$

1 Answer 1

5
$\begingroup$

Q3 (and, to some extent, Q1) is discussed in Chudnovsky and Chudnovsky's Sequences of Numbers Generated by Addition in Formal Groups and New Primality and Factorization Tests (Adv. in Appl. Math. 7, 385-434):

In the factorization algorithm of Section 4 the immediate use of higher dimensional Abelian varieties does not seem to be helpful, because whenever $g > 1$, $N_p$ grows as $p^g + O(p^{g/2})$ and "it is less likely" that $N_p$ will be divisible by small primes only. Nevertheless, several possibilities arise. First of all we can try to decrease the number of computations. For this we propose to consider $g$ "arbitrary" elliptic curves simultaneously as a single Jacobian of a curve of genus $g > 1$, isogeneous to the product of these $g$ elliptic curves.

Edit: Here, $g$ is the dimension of the Abelian variety, and thus the genus of the curve $C$ when the Abelian variety is isomorphic or isogenous to a Jacobian $J_C$.

Cosset has used this approach successfully in the case $g = 2$.

$\endgroup$
1

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.