-1
$\begingroup$

What is the current conventional algorithm used to calculate factors of large numbers in order to determine if they are coprimes, or if there is a way to do it without calculating factors, what would it be?

I'm creating RSA encryption for files and messages. I need to be able to find coprimes, but I run into the problem I encountered while trying to check if two large numbers are prime; I used the approach that I had for small numbers where I had to try and find any factors of the number, and if I couldn't I would declare it prime. Since my numbers are between 400 to 1024 bits in size, that wouldn't work and I modified my code to use primality tests instead. Now, I'm trying to calculate factors of large numbers to determine if they are coprimes, and I was wondering what the standard convention for doing so was. Would anyone happen to know?

(I was thinking of an approach where I run through small numbers, using simple divisibility rules, until I find a factor of $e$ and [another factor of] $(p-1)(q-1)$. I would then use that factor to keep dividing $e$ and $(p-1)(q-1)$ and add any factors I found in the process. (Helps if the number is even, huh?)

$\endgroup$
  • $\begingroup$ Read this. $\endgroup$ – fkraiem Jan 2 '18 at 3:40
3
$\begingroup$

What is the current conventional algorithm used to calculate factors of large numbers in order to determine if they are coprimes, or if there is a way to do it without calculating factors, what would it be?

The standard way to determine if two large numbers are coprime would be to compute the Greatest Common Denominator of the two numbers; one efficient algorithm to do so is the Euclidean Algorithm

On the other hand...

I'm creating RSA encryption for files and messages. I need to be able to find coprimes

I assume that you're looking for a way to determine whether $e$ and $p-1$ (and $q-1$) are relatively prime. What we usually do is select a small $e$ (with 65537 being the canonical value); that way, all that is needed is to ensure that $p-1 \not\equiv 0 \pmod{65537}$ and $q-1 \not\equiv 0 \pmod{65537}$ (and this is sufficient because 65537 is prime). I personally find it convenient to make that one of the requirements when searching for $p$ and $q$.

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