0
$\begingroup$

I am using the standard version of the Euclidian Algorithm (i.e. GCD(270, 192) = GCD(192, [270 % 192]) = ...repeat until 0) to determine if two numbers are coprime. I run the algorithm, check if the GCD is 1 and use that to determine if they are.

The problem is that I'm doing this for RSA and when I test the algorithm with 5 or 6 digit numbers it takes about 4 seconds, so I need a way to optimise the algorithm to work with hundreds of digits. I found references to the Extended Euclidean Algorithm online, but to my understanding that is used for checking the modular inverses that you create.

Can anyone confirm that the Extended Euclidean Algorithm should be used for this purpose, or suggest another algorithm that can be used to calculate the GCD of 300 - 600 digit numbers?

$\endgroup$
  • $\begingroup$ I'm not sure if it will help with 300-600 digit numbers, but when you use the sieve of eranthoses you only need to check factors from 0 up to the square root of the prime you're checking. As any factor beyond this bound would have been initially returned with the first check, likewise you could only check factors between the square root and prime you're checking with the same results. $\endgroup$ – Q-Club Jan 4 '18 at 1:23
  • $\begingroup$ What you are doing is not at all standard, and is completely wasteful. Only one GCD computation is needed. $\endgroup$ – fkraiem Jan 4 '18 at 1:26
  • 3
    $\begingroup$ If it takes 4 seconds to run the Euclidean Algorithm of two 5-6 digit numbers, either you've implemented it wrong, or you've implemented it in an extremely efficient language. In any case, why are you computing a GCD to do RSA? $\endgroup$ – poncho Jan 4 '18 at 3:50
  • $\begingroup$ The square root of the number is still way too large; probably between 50 - 100 digits in length, so I would have to check thousands of times even with the sieve of Eratosthenes. I tried it, and it was even slower than the Euclidean Algorithm approach. Thanks, anyway! $\endgroup$ – Madhav Malhotra Jan 5 '18 at 0:53
  • $\begingroup$ Reading your last comment it sounds like you use the gcd to verify that your candidate for being one of the two primes does not have small divisors. As one has only to check this for small divisors that are primes themselves, simple divisions and looking if the remainders are $0$ is enough! $\endgroup$ – j.p. Jan 5 '18 at 7:09
3
$\begingroup$

This answer covers use and implementation of the Euclidean algorithm in RSA, first straight for computing the Greatest Common Divisor of two integers; then (half-)extended for the computation of modular inverses.


The (straight) Euclidean algorithm is often used at one step in RSA: when it comes to choose odd $e>1$ and distinct primes $p$ and $q$ such that $\gcd(p-1,e)=1=\gcd(q-1,e)$. It has very little cost compared to other computations involved in that choice, in particular the test that $p$ and $q$ are prime (which is not performed using the Euclidean Algorithm). $e$ is usually small, thus only the first step of the algorithm needs to be carried with large numbers. Further, often $e$ is prime (including when $e=F_k=2^{(2^k)}+1$ with $0\le k\le 4$, the 5 Fermat primes); hence $\gcd(p-1,e)=1$ holds precisely when $p\bmod e\not=1$, and this simple test sidesteps explicit GCD computation.

Another possible use of the (straight) Euclidean algorithm in RSA is when computing $\lambda(N)=(p-1)(q-1)/\gcd(p-1,q-1)$ , if that's desired.

One possible efficient form of the Euclidean algorithm to compute $\gcd(a,b)$ for positive integers $a$ and $b$ repeats (until the algorithm stops):

  • $a\gets a\bmod b$ .
    That is, replace $a$ with $a'$ matching $0\le a'<b$ and $b$ divides $a-a'$ .
    Or equivalently, $q\gets\lfloor a/b\rfloor$ followed by $a\gets a-q\,b$ .
  • If $a=0$, then output $b$ and stop.
  • Exchange $a$ and $b$ .

Practical implementations often replace the exchange with a copy of the other steps with permutation of $a$ and $b$ .

The average number of steps is significantly reduced in this optimized version, but each step is slightly more complex:

  • $q\gets\lfloor(a+b/2)/b\rfloor$ (that is $a/b$ rounded to nearest, sometime noted $\lfloor a/b\rceil$ )
  • $a\gets|a-q\,b|$ .
  • If $a=0$, then output $b$ and stop.
  • Exchange $a$ and $b$ .

In RSA, the extended Euclidean algorithm is often used to compute one or more of the following modular inverses:

  • $d=e^{-1}\bmod\varphi(N)\;$ with $\varphi(N)=(p-1)(q-1)$ .
  • $d=e^{-1}\bmod\lambda(N)\;$ with $\lambda(N)=(p-1)(q-1)/\gcd(p-1,q-1)$ .
  • $d_p=e^{-1}\bmod(p-1)$ .
  • $d_q=e^{-1}\bmod(q-1)$ .
  • $q_\text{inv}=q^{-1}\bmod p$ .

The last three are used by optimized implementations using the Chinese Remainder Theorem. One of the first two is customary in introductory material on RSA, and useful in practice when $d$ is required (for archival/interchange, or because the CRT optimization is not used).

In all cases, the half-extended Euclidean algorithm can be used to efficiently compute $a^{-1}\bmod b$ for non-negative integer $a$ and positive integer $b$ , manipulating non-negative integers only:

  1. $x\gets0$ and $y\gets1$ and $m\gets b$ .
    Note: $ax+by=m$ will keep holding, with $m$ the original modulus.
  2. if $a=1$, then output "the desired inverse is $y$" and stop.
  3. If $a=0$, then output "the desired inverse does not exists" and stop.
  4. $q\gets\lfloor b/a\rfloor$ .
  5. $b\gets b-aq$ and $x\gets x+qy$ .
  6. if $b=1$, then output "the desired inverse is $m-x$" and stop.
  7. If $b=0$, then output "the desired inverse does not exists" and stop.
  8. $q\gets\lfloor a/b\rfloor$ .
  9. $a\gets a-bq$ and $y\gets y+qx$ .
  10. Continue at 2.

Note: $a$ and $b$ evolve as in the straight Euclidean algorithm; $x$ and $y$ are the (half) extension. The (full) extended Euclidean algorithm keeps two more variables, in order to fully solve the Bezout identity.


Various optimizations apply to the Euclidean algorithm and its (half)-extended variant:

  • The quotient $q$ needs not be computed exactly. If it is too small, the penalty is that the next $q$ will be 0. If $q$ is too large, numbers can get negative (and that can be either dealt with, or corrected). We can thus get away with a rough estimation of $q$ (and it pays to round to nearest if we can deal with that).
  • Usually, $q$ is small. When the numbers handled use multiple limbs/digits, it pays to optimize the case when $q$ fits a single limb. It may even pay to special-case $q=1$ and $q=2$.
  • Large $q$ need to be handled (otherwise worst case execution time becomes linear with the inputs), but is infrequent thus not critical. We can round large $q$ down to a power of two. In fact, restricting to $q$ a power of two is not disastrous, and has the advantage of replacing multiplication with shifts.
  • Usually, it is possible to predict the next few values of the (small) $q$ from the high-order bits of $a$ and $b$. That allows to group several transformations of $a$, $b$, $x$, $y$ into linear transformations with moderate multipliers computed from the predicted values of the $q$.

Off-topic since strictly speaking that's no longer the Euclidean algorithm: there is a binary GCD algorithm that performs only subtraction, additions, and divisions by 2. It also has an extended version fully solving the Bezout identity (see the Handbook or Applied Cryptography, algorithm 14.61), and a half-extended version specialized towards computing the modular inverse (see the first section of this answer). It can be competitive with the Euclidean algorithm when multiplication is expensive; and the two can be blended.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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