Excluding specific factors for Pohlig-Hellman I want to use Pohlig-Hellman and BSGS to solve the discrete log of an Elliptic Curve which has a composite order generator.

The tricky part is, one of the composite factor groups is large (99bits), so I want to exclude it from the Pohlig-Hellman/BSGS.

Is it possible in SageMath to apply the discrete_log() function to an elliptic curve, and exclude one of the generators factors?

Is there a trick with Chinese remainder theorem?
Suppose we have a point $P$ of order $q$ on an elliptic curve where the prime decomposition of $q$ is $q =  p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$. We also have a point $Q=kP$ and we want to find $k$.

Pohlig-Hellman algorithm

The idea of Pohlig-Hellman's algorithm is to to compute a discrete logarithm in the subgroups of prime order.

Easy case

We suppose $\alpha_i=1$ for $1\leq i \leq n$, so $q=p_1\cdots p_n$ and all primes are distinct.

Let
\begin{align}
q_i &amp; = \frac{q}{\displaystyle\prod_{1 \leq j \leq n, j\neq i} p_j} \\
P_i &amp; =  q_i P, \\
Q_i &amp; =  q_i Q.
\end{align}

The point $P_i$ has order $p_i$ and we have $Q_i = k_i P_i$ where $k_i = k \bmod p_i$. The discrete logarithm can be computed with discrete_log on Sage or another software, and the value $k_i$ is recovered.

Do this only for primes that are in your interest, such as those that are small enough. If the value $k$ is inferior to the product of those primes, it will be found using the Chinese Remainder Theorem (with CRT([list of k_i], [list of p_i]).

Hard case

Now we suppose $\alpha_i$ is larger than $1$ for some of them. Again, we compute
$$
\begin{align}
q_i &amp; = \frac{q}{\displaystyle\prod_{1 \leq j \leq n, j\neq i} p_j^{\alpha_j}} \\
P_i &amp; =  q_i P, \\
Q_i &amp; =  q_i Q.
\end{align}
$$
The point $P_i$ has order $p_i^{\alpha_i}$ and we have $Q_i = k_i P_i$ where $k_i = k \bmod p_i^{\alpha_i}$. Then, we write the decomposition of $k_i$ in base $p_i$:
$$
k_i = k_{i,0} + k_{i,1}p_i + k_{i,2}p_i^2 + \cdots + k_{i,\alpha_i-1}p_i^{\alpha_i-1},
$$
where $0 \leq k_{i,j} &lt; p_i$ for $0 \leq j &lt; \alpha_i$. To obtain $k_i$, we will get all $k_{i,j}$ one by one. First, for $k_{i,0}$, we construct the two following points:
\begin{align}
P_{i,0} &amp; = p_i^{\alpha_i-1} P_i, \\
Q_{i,0} &amp; = p_i^{\alpha_i-1} P_i.
\end{align}
The point $P_{i,0}$ is a point of order $p_i$ and we have the relation $Q_{i,0} = k_{i,0} P_{i,0}$. The discrete logarithm can be computed with discrete_log.

The next value $k_{i,1}$ can be found in a similar way. We compute
$$
Q_{i,1} = p_i^{\alpha_i-2} (Q_i-k_{i,0}P_i)
$$
and we have $Q_{i,1} = k_{i,1}P_{i,0}$, and discrete_log gives the value $k_{i,1}$. Then
$$
Q_{i,2} = p_i^{\alpha_i-3} (Q_i-(k_{i,0}+k_{i,1}p_i)P_i)),
$$
and we have $Q_{i,2} = k_{i,2}P_{i,0}$, and we get $k_{i,2}$, and so on, until $k_i$ is complete.

Again, do this only for primes $p_i$ that are in your interest.