El Algoritmo de Euclides puede ser utilizado para determinar si dos números enteros son coprimos sin saber sus factores primos; el algoritmo funciona en un tiempo polinomial en el número de dígitos implicados.