# Factorisation for Coprimes of Large Numbers - RSA

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?)

• Read this. – fkraiem Jan 2 '18 at 3:40

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