The Integer Greatest Common Divisor is NC
Autores
|
3977 |
Side Mohamed Sedjelmaci
|
1759
|
Informações:
Publicações do PESC
Título
The Integer Greatest Common Divisor is NC
Linha de pesquisa
Otimização
Tipo de publicação
Relatório Técnico
Número de registro
ES-706/7
Data
3/2007
Resumo
Provamos que o maior divisor comum (mdc) de dois inteiros de no máximo n bits pode ser computado em tempo O (log2 n) por um número polinomial de processadores. Conseqüentemente, os problemas de co-primalidade e de inversão modular pertencem também à classe NC.
Abstract
We prove that the Greatest Common Divisor (gcd) of two integers of less than n bits, can be computed in O (log2 n)time with a polynomial number of processors. As a consequence, integer coprimality and modular inversion problems also belong to the NC class.
Keywords: Parallel algorithms, Parallel integer GCD, Complexity analysis, NC class Complexity, Number theory.
Keywords: Parallel algorithms, Parallel integer GCD, Complexity analysis, NC class Complexity, Number theory.
Arquivo