2
$\begingroup$

I have a question about CRT.

Assuming, that we have this system (S):

x=a0 mod n0

x=a1 mod n1

with N=n0*n1 and n0,n1 are two distinct prime numbers.

Then the complexity in terms of binary operation is O(log(N)^2) in order to find x.

My problem is that I study the complexity of Pohlig–Hellman algorithm in term of the number of multiplication in a cyclic group G of order N=n1*n0. Pohlig–Hellman algorithm use CRT algorithm.

So, I don't see how can I measure the complexity of Chinese remainder theorem in term of the number of multiplication in G of order N.

Any ideas?

$\endgroup$
5
  • $\begingroup$ You might want to use the same base of complexity over your question. You start name binary operations and complexity in term of multiplications. Your statement about the CRT is probably wrong- a single multiplication is already $O(log(n)^2$ in binary operations. Modulo is much more, similar to division. $\endgroup$
    – tylo
    Apr 5, 2021 at 16:49
  • $\begingroup$ No, I'm not wrong : untruth.org/~josh/math/effective-crt.pdf $\endgroup$
    – Altario
    Apr 5, 2021 at 16:54
  • $\begingroup$ The problem is to convert binary complexity to algebric complexity, or find algebric complexity of CRT because I need to proof complexity of Pohlig–Hellman algorithm in term of group operation in G that is my problem $\endgroup$
    – Altario
    Apr 5, 2021 at 16:58
  • $\begingroup$ Are you looking for complexity of the Pohlig-Hellman exponentiation cipher, or of the Pohlig-Hellman algorithm for discrete logarithm? Both usually use a prime modulus, but can be reformulated for composite modulus of known factorization. Hint: in both cases, the CRT is used to compute the final result, and you'll find the cost of the CRT is negligible compared to the rest. Note: the text you cite as reference for the cost of the CRT asserts the cost of the modular inversion step is $O((\log N)^2)$ without reference or proof; and that's the only non-trivial step; thus it's not very useful. $\endgroup$
    – fgrieu
    Apr 5, 2021 at 18:25
  • $\begingroup$ I found an answer. Yes this is a stretch of proof but I have the complete proof. But I have an answer and your are right there is a proof that CRT can be consider negligible compared to the rest. :) $\endgroup$
    – Altario
    Apr 5, 2021 at 20:58

1 Answer 1

5
$\begingroup$

So, I don't see how can I measure the complexity of Chinese remainder theorem in term of the number of multiplication in G of order N.

Any ideas?

Well, the standard way to solve for $x$ (given that $n_0, n_1$ are relatively prime) is to compute:

$$x = n_1 ((a_0 - a_1) n_1^{-1} \bmod n_0) + a_1$$

(where $n_1^{-1}$ is computed modulo $n_0$)

It is straightforward to verify that:

$$ 0 \le x < n_0n_1$$ $$ x \equiv a_0 \pmod{ n_0 }$$ $$ x \equiv a_1 \pmod{ n_1 }$$

As for the cost of the computation, $n_1^{-1}$ can be computed with $O(\log N)$ multiplication operations; the rest of the operations are two multiplication operations (one modulo $n_0$), and two addition/subtraction operations.

So, I don't see how can I measure the complexity of Chinese remainder theorem in term of the number of multiplication in G of order N.

So, in Pohlig-Hellman, you compute $H = a_0(n_1G)$ and $H = a_1(n_0G)$, and combine $a_0$ and $a_1$ to form the value $x$ s.t. $H = xG$. Computing $a_0, a_1$ takes $O(\sqrt{\max(n_0, n_1)})$ multiplications (assuming the curve does not have any special form that allows us to compute the discrete logs faster); combining $a_0, a_1$ doesn't take any (because those are computed using integer computations, not elliptic curve operations).

$\endgroup$
1
  • $\begingroup$ First, G can be a group of elliptic curve for example so even this $O(\log N)$ integer multiplication this is not multiplication in G and that is my problem. Because in Pohlig–Hellman algorithm we considerre the number of multiplications in G for the complexity en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm cf "Complexity" $\endgroup$
    – Altario
    Apr 5, 2021 at 17:57

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.