UNIVERSIDADE ESTADUAL DE MATO GROSSO DO SUL

COORDENAÇÃO DO CURSO DE MATEMÁTICA - UNIDADE DE DOURADOS

UMA INTRODUÇÃO AOS MÉTODOS DE FATORAÇÃO

DE INTEIROS DE FERMAT E POLLARD

Vinı́cius Cardoso Barnabé

Orientação
Profa. MSc. Adriana Betânia de Paula Molgora

Dourados - MS
10 de dezembro de 2009
 UNIVERSIDADE ESTADUAL DE MATO GROSSO DO SUL
COORDENAÇÃO DO CURSO DE MATEMÁTICA - UNIDADE DE DOURADOS

UMA INTRODUÇÃO AOS MÉTODOS DE FATORAÇÃO

DE INTEIROS DE FERMAT E POLLARD

Vinı́cius Cardoso Barnabé

Trabalho de conclusão apresentado ao Curso

de Matemática da Universidade Estadual de
Mato Grosso do Sul, como parte dos requi-
sitos para obtenção do tı́tulo de licenciatura
em matemática.

Orientação: MSc. Adriana Betânia de Paula Molgora

Dourados - MS
Uma Introdução aos Métodos de Fatoração de Inteiros de
Fermat e Pollard

Vinı́cius Cardoso Barnabé

Banca Examinadora:

Prof. MSc. Adriana Betânia de Paula Molgora, Docente (UEMS)

Orientador

Prof. MSc. Rildo Pinheiro do Nascimento, Docente (UEMS)

Examinador 1

Prof. Dr. Lucélio Ferreira Simião, Docente (UEMS)

Examinador 2

Dourados.
Dezembro de 2009.
Aos meus pais Augusto e Rosa Maria.
Dedico
 Agradecimentos
Agradeço a Deus por este momento em minha vida. Agradeço aos meus pais pelo incentivo
e a todos que contribuı́ram para realização deste trabalho.

i
 Resumo
A fatoração de números inteiros é um assunto antigo, porém de muito interesse. Esse
interesse deve-se ao fato de que a segurança de alguns sistemas criptográficos como o
RSA (Ronald Rivest, Adi Shamir e Leonard Adleman) depende da ineficiência dos
métodos de fatoração existentes. Existem diverssos métodos de fatoração de inteiros,
dentre esses, os métodos de Fermat e Pollard. Esse trabalho tem o objetivo de descrever
os métodos de Fermat, Pollard-Rho e Pollard p − 1.

Palavras-chave: Fatoração, Método de Fermat, Método de Pollard

ii
Sumário

Introdução 1

1 Embasamento teórico 3
1.1 Existência da fatoração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Divisão De Números Naturais . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Máximo Divisor Comum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Congruência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Unicidade da fatoração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7 Teto e piso de um número . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Método de Fermat 10
2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Fatoração de inteiros pelo Método de Fermat . . . . . . . . . . . . . . . . . 11
2.3 Demonstrando o Método de Fermat . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Algoritmo de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Fatoração por Pollard Rho 16

4 Método de Fatoração p-1 20

5 Discussão sobre os Métodos de Fatoração 23

Conclusão 25

iii
Introdução

A questão de divisibilidade é um dos problemas matemáticos mais antigos. Na literatura

sobre a História da Matemática é atribuı́do ao matemático grego Pitágoras, os primeiros
estudos sobre os números primos. Ao contrário do que muitos pensam, a palavra primo
não tem relação ao parentesco e sim a primário. Os pitagóricos denominavam números
“primários” todos os números naturais que não podiam ser obtidos através do produto
de outros números. Já aqueles gerados a partir do produto de outros números eram
denominados números “secundários”, como por exemplo: 4 = 2 · 2, 6 = 2 · 3, etc [8].
Os gregos antigos perceberam que todo inteiro poderia ser escrito unicamente como um
produto de números primos, e essa descoberta é a base do Teorema fundamental da
Aritmética [5].
Criptografia é a ciência que tem como foco principal a segurança das in-
formações. O sistema criptografico RSA é um dos métodos mais utilizados na atualidade.
Esse método tem sua segurança baseada no fato de que a fatoração de inteiros é um prob-
lema ainda sem solução. Isso torna o estudo de métodos de fatoração imprenscindı́vel.
Existem diversos métodos de fatoração na atualidade. Dentre eles estão os
métodos de Fermat, Pollard Rho e Pollard p-1. Para o entendimento do funcionamento
desses métodos de fatoração é necessário um estudo dos diversos aspectos matemáticos
envolvidos em seu processo de fatoração.
Esse trabalho tem como objetivo principal apresentar uma descrição dos métodos
de fatoração de inteiros de Fermat, Pollard Rho e Pollard p-1. Com base nesse objetivo o
texto está organizado como segue. No capı́tulo 1 são apresentados conceitos matemáticos
elementares para o entendimento dos métodos de fatoração a serem estudados. No capı́tulo

1
2, é realizada uma descrição do método de Fermat. O capı́tulo 3, apresenta o método
de Pollard Rho enquanto o capı́tulo 4 descreve o método de Pollard p-1. Além disso, no
capı́tulo 5 é realizada uma discussão sobre os métodos de fatoração de inteiros apresenta-
dos.

2
Capı́tulo 1

Embasamento teórico

Introdução
Esse capı́tulo apresenta a fundamentação matemática envolvida no funciona-
mento dos métodos de Fermat, Pollard-Rho e Pollard p-1. Informações adicionais podem
ser encontradas em [1] e [4].

1.1 Existência da fatoração

A existência da fatoração de um número inteiro n pode ser provada por indução em n.
Se n é primo, está demonstrado. Se n é composto, deve-se tomar n = 2 como
base de indução. Sabe-se que 2 = 2h , ou seja, 2 = 21 (isso quando h = 1), o que significa
que 2 pode ser fatorado em um produto de primos.
Agora deve-se verificar se n = k + 1 pode ser fatorado em um produto de
primos. Primeiro, se k + 1 é primo a prova está concluı́da. Mas se k + 1 é composto,
supõe-se k + 1 = ab, onde 1 < a, b < k. Mas como a, b < k, então pela hipótese a e b
podem ser escritos como um produto de primos, se, a = p1 ...pr , e q1 ...qs ,
de forma que
k + 1 = ab = p1 ...pr q1 ...qs ,

assim, k + 1 pode ser fatorado em um produto de fatores primos não necessariamente

3
distintos. Assim, foi provado que existe uma fatoração em primos para qualquer número
inteiro n ≥ 2.

1.2 Divisão De Números Naturais

Uma equação do tipo bx = a pode ou não ter solução no conjunto dos números inteiros;
isso dependerá dos coeficientes a e b da equação. Quando tal solução existe, diz-se que a
é divisivel por b. Mais prescisamente:
Definição:
Sejam a e b números inteiros. Diz-se que b divide a (ou que b é um divisor de
a ou, ainda, que a é um múltiplo de b) se existe um inteiro c tal que bc = a.
Convém observar que, se b 6= 0, o inteiro c nas condições da definição é único.
De fato, se existisse outro c0 tal que bc0 = a , terı́amos que bc = bc0 e, cancelando, vem
que c = c0 . O inteiro assim definido chama-se quociente de a por b e é indicado por
c = a/b = ab .
Exemplo:
a) Se a = 10 e b = 5 então dizemos que b|a tal que existe um número c que
satisfaz a equação a = bc logo 10 = 5c então c = 2
b) Se a|b então existe um número c tal que b = ac, então se a = 2 e b = 4
temos que 4 = 2c, logo c = 2.
Por outro lado, note que 0|a se e somente se a = 0. Nesse caso, o quociente não
é único pois 0.c = 0, para todo inteiro c. Por causa disso, costuma-se excluir o caso em
que o divisor é nulo, e nós vamos aderir a essa convenção: em tudo o que segue, mesmo
que não seja explicitamente dito, estaremos admitindo que todos os divisores considerados
são diferentes de zero.

1.3 Máximo Divisor Comum

Definição:

4
 Dado a, b ∈ Z, dizemos que d ∈ Z é máximo divisor comum entre a e b se
(i)d ≥ 0;
(ii) d|a e d|b e
(iii) se d0 é um número inteiro tal que d0 |a e d0 |b, então d0 |d.
Observações
a) d e d1 são máximos divisores comuns entre a e b, então d = d1 . De fato,
como d|d1 e d1 |d e, ainda, são ambos positivos, concluı́mos que d = d1 ;
b) Se a = b = 0, então d = 0, como é óbvio;
c) Se a = 0 e b 6= 0, então d = |b|;
d) Se d é máximo divisor comum entre a e b, então d tambem é máximo divisor
comum entre a e −b, −a e b e, ainda, entre −a e −b.
Notação: Indicaremos por mdc(a, b) o máximo divisor comum entre a e b que
já sabemos ser único, quando existe. A proposição a seguir nos garante sua existência em
todos os casos.
Exemplos:
a) Se a = 4 e b = 6 então
mdc(a, b) = mdc(4, 6) = 2 pois 2|4 e 2|6.
b) Se a = 15 e b = 5 então
mdc(a, b) = mdc(15, 5) = 5 porque 5|15 e 5|5.
c) Se a = 25 e b = 26 então
mdc(a, b) = mdc(25, 26) = 1 pois 1|25 e 1|26.
Proposição 1: Quaisquer que sejam a, b pertencentes aos inteiros, existe d
pertencente aos inteiros que é o máximo divisor comum de a e b.
Demonstração:
Levando em conta as observações acima podemos nos limitar ao caso em que
a > b e b > 0.
Seja L = ax + by | x, y ∈ Z. Evidentemente existem elementos estritamente
positivos em L (faça-se, por exemplo, x = y = 1). Seja d o menor desses elementos.
Mostremos que d é o máximo divisor comum entre a e b.

5
 (i) d é obviamente maior ou igual a zero;
(ii) como d ∈ L, então existem x0 , y0 ∈ Z de maneira que

d = ax0 + by0

Aplicando o algoritmo da divisão aos elementos a e d:

a = dq + r(0 ≤ r < d).
Das duas últimas igualdades tiramos

a = (ax0 + by0 )q + r

ou, ainda

r = a(1 − qx0 ) + b(−y0 )q

o que vem mostrar que r ∈ L. Sendo r ≥ 0 e levando em conta que a escolha do elemento
d a conclusão é que r = 0. Daı́ ficamos com a = dq o que mostra que d|a.
Analogamente se prova que d|b;
(iii) Se d0 |a e d0 |b, como d = ax0 + by0 , então é claro que d0 |d.
N ota : Se d = mdc(a, b), então se verificou, na demonstração acima, que
d = ax0 + by0 onde x0 , y0 ∈ Z. Os elementos x0 e y0 que satisfazem tal identidade não
são únicos. Uma tal identidade recebe o nome de identidade de Bezout em Z para os
elementos a e b.

1.4 Congruência
Definição:
Seja m > 1 um número inteiro. Dado a, b, ∈ Z, dizemos que a é côngruo a b,
módulo m, se, e somente se, m|(a − b).
Notação: a ≡ b(mod m).
Exemplos:

6
 a) 21 ≡ 1(mod 5) pois 21 − 1 = 20 e é divisı́vel por 5.
b) 100 = 1(mod 9) pois 100 − 1 = 99 que é divisı́vel por 9.
Propriedades:
a) a ≡ a(mod m), para todo a ∈ Z, pois a − a = 0 e 0 é divisı́vel por m.
b) a ≡ b(mod m) implica b ≡ a(mod m).
c) a ≡ b(mod m) e b ≡ c(mod m) implica a ≡ c(mod m).
Provemos. Como m|(a − b) e m|(b − c), então m|[(a − b) + (b − c)], ou seja,
m|(a − c). Isto equivale à tese.
d) a ≡ b(mod m) e c ≡ d(mod m) implica a + c ≡ b + d(mod m).
e) a ≡ b(mod m) implica ac ≡ bc(mod m) para todo c ∈ Z.
f) a ≡ b(mod m) implica ar ≡ br (mod m), para todo r ≥ 1.
Para r = 1 a implicação é evidente.
Suponhamos ar ≡ br (mod m). Então ar+1 ≡ abr (mod m). Por outro lado,
de a ≡ b(mod m), segue que abr ≡ br+1 (mod m). Juntando as duas conclusões tiramos
ar+1 ≡ br+1 (mod m).

1.5 Algoritmo de Euclides

Sejam r0 = a e r1 = b inteiros tais que a ≥ b > 0. Se o algoritimo da divisão é
sucessivamente aplicado para obter rj = rj + qj + rj+2 com 0 ≤ rj+2 < rj+1 para j =
0, 1, 2, ..., n − 2 e rn+1 = 0, então mdc(a, b) = rn , o último resto não nulo.

1.6 Unicidade da fatoração

Para provar que a fatoração de um número inteiro em primos é única, pode-se utilizar o
lema apresentado a seguir, que é a primeira aplicação do Algoritmo de Euclides.
Lema 1.1.1. Sejam a, b e c inteiros positivos tais que a e b são relativamente
primos.
(1) Se b|ac então b|c.

7
 (2) Se a|c e b|c, então ab|c.
Prova:
1o Sejam a e b inteiros relativamente primos, isto é, tal que mdc(a, b) = 1.
Pelo Algoritmo de Euclides Estendido existem inteiros m e n tais que

ma + nb = 1

Multiplicando esta equação por c obtêm-se

mac + nbc = c

É óbvio b|nbc. Mas, por hipótese, b|ac. Logo b|(mac = ncb) = c. Portanto,
b|c.
2o Pode ser provado a partir do 1o . De fato, se a|c pode-se escrever c = at,
para algum inteiro t. Mas, b|c, e como mdc(a, b) = 1, segue da 1a afirmação que b|t.
Assim, t = bk para algum k. Portanto,

c = at = a(bk) = (ab)k

é divisı́vel por ab, o que prova a 2a afirmação.

As duas partes deste lema são usadas na demonstração de uma propriedade
muito importante dos números primos.
Seja p um número primo e a e b inteiros positivos. Se p|ab, então p|a ou p|b.
Prova:
Se p|a, a prova está pronta. Supomos então, que p não divide a. Como p é
primo, então mdc(a, p) = 1. Pelo Lema 1.1.1, item 1o segue que p|b.
Teorema Fundamental da Aritmética, Todo inteiro positivo, n ≥ 2 pode
ser representado de modo único, com exceção da ordem, como um produto de fatores
primos, ou seja
n = pe11 ...pehh

onde h ≥ 1, p1 < p2 < p3 < ... < ph são números primos e e1 , ..., eh são inteiros positivos.

8
1.7 Teto e piso de um número
O teto de um número x ∈ R, é dado pelo menor inteiro maior que x. Notação: dxe
Exemplo:
a) x = 2, 35
dxe=d2, 35e=3
b) x = 3, 01 dxe=d3, 01e=4
O piso de um número x ∈ R, é dado pelo maior inteiro menor que x. notação:bxc
Exemplo:
a) x = 2, 35 bxc=b2, 35c=2
b) x = 3, 01
bxc=b3, 01c=3

9
Capı́tulo 2

Método de Fermat

2.1 Introdução
Fermat foi um dos poucos matemáticos amadores famosos. Filho de um rico comerciante
de couro, pôde se dedicar completamente aos estudos. Por influência de sua mãe, descen-
dente de uma famı́lia de juristas, estudou leis na Universidade de Orleans e formou-se
em advocacia. Trabalhou durante toda sua vida na corte de justiça de Toulouse. Foi
nomeado juiz e ocupava os seus momentos de folga em diversos lazeres, entre os quais a
poesia e a Matemática[6].
Seu interesse pela matemática iniciou-se em 1629 com o estudo dos trabalhos
de Apolônio (matemático grego, 260 A.C.) sobre curvas planas. Trocava correspondência
com os maiores matemáticos da época, como Torricelli, Roberval, Huyghens e Pascal, e,
dessa forma relatava suas descobertas. Jamais publicou seus trabalhos de nenhuma outra
forma mas o conteúdo das cartas de Fermat é atualmente incluı́do em todos os textos
usuais de teoria dos números [6].
Seu interesse na teoria dos números surgiu após ler o livro Aritmética de Dio-
fanto (matemático grego, 200 A.C.) e alguns dos problemas propostos por Fermat, nesta
área, eram tão difı́ceis que somente muitos anos mais tarde foram provados. Um desses
problemas afirmava que “todo número inteiro pode ser escrito como a soma de, no máximo,

10
quatro quadrados”e foi provado em 1770, pelo matemático francês Lagrange [6].

2.2 Fatoração de inteiros pelo Método de Fermat

A fatoração de inteiros pelo método de Fermat, tem como base o fato de que dado um
número n composto, se n = x2 − y 2 = (x + y)(x − y) então tem-se que (x + y) e
(x − y) são os fatores de n [5].
Por suposição, n é ı́mpar, pois se n for par é divisı́vel por 2. Ou seja, 2 é um
dos fatores de n. No caso em que n é ı́mpar, pelo método de Fermat deve-se encontrar
números inteiros positivos x e y tal que (x + y)(x − y) = n.
Na prática, pretende-se encontrar dois números naturais x e y, tais que x
√
corresponde a parte inteira da raiz quadrada de n e y = x2 − n.
√
Para poder aplicar o método de Fermat, assume-se que n = r. O caso mais
simples acontece quando n é um quadrado perfeito, ou seja, quando existe um número
inteiro n, tal que n = r2 . Dessa forma r é fator de n, onde x = r e y = 0, pela notação
anterior. Ou seja,

p √
x = n + y2 = n

Exemplo: Fatorar o número n = 1342127. A variável x é iniciada com a

parte inteira da raiz de n, que neste caso vale x = 1158. Mas,
11582 = 1340964 < 1342127 = n
√
Assim x passa a ser incrementado de um em um, até que x2 − n2 seja um
número inteiro. Nesse caso, toma-se esse valor para y. Caso contrário, continua-se incre-
n+1
mentando até o limite 2
.
Se x = 1159, tem-se:
√
y = x2 − n
√
y = 11592 − 1342127
y = 33, 97, como y não é um valor inteiro deve-se continuar com o método, incrementando
mais 1 ao valor de x, então

11
 x = 1160

√
y= x2 − n

√
y= 11602 − 1342127

y = 58, 93, incrementando 1 a x tem-se:

x = 1161

√
y= x2 − n

√
y= 11612 − 1342127

y = 76, 11. Como y ainda não é um valor inteiro vamos continuar com o método, incre-
mentando um ao valor de x, deste modo:

x = 1162

√
y= x2 − n

√
y= 11622 − 1342127

y = 90, 09, como o método ainda não chegou a seu propósito deve-se prosseguir
incrementando um ao valor de x, então

x = 1163

12
 √
y= x2 − n

√
y= 11632 − 1342127

y = 102, 18, y não é um valor inteiro, logo deve-se incrementar um ao valor de

x, portanto

x = 1164

√
y= x2 − n

√
y= 11642 − 1342127

y = 113

Assim, tem-se a fatoração de n. Os 2 fatores de n são (x + y) = 1277 e

(x − y) = 1051. Logo,

n = x2 − y 2

n = (x + y)(x − y)

n = (1277)(1051) = 1342127

2.3 Demonstrando o Método de Fermat

Precisamos considerar separadamente quando n é composto e quando é primo. Quando
√ √
n é composto mostra-se que existe um inteiro x > b ncc tal que x2 − n é um número

13
 (n + 1)
menor que 2
. Então n é composto e encerra-se a execução do método antes de chegar
(n + 1) (n+1)
ax= 2
. Se n é primo então verifica-se que o único valor de x possı́vel é 2
.
Supondo que n pode ser fatorado como n = ab, onde b ≥ a queremos obter
inteiros positivos x e y de forma que n = ab = (x + y)(x − y) = x2 − y 2 .
Como x − y ≤ x + y toma-se a = x − y e b = x + y.
a = x − y (∗)
b = x + y (∗∗)
Então de (∗)e(∗∗) temos
a + b = 2x
a+b
x= 2

b − a = 2y
b−a
y= 2

Espandindo os produtos notáveis temos que

b+a 2 b−a 2
( ) −( ) = ab = n
2 2
Assim x e y são inteiros, mas ( b+a
2
) e ( b−a
2
) estão escritos como fração. Mas n
é ı́mpar, por hipótese, então como a e b são fatores de n, temos que (a + b) e (a − b) são
pares logo ( b+a
2
) e ( b+a
2
) são inteiros.
Se n = ab onde, a = x − y e b = x + y com b ≥ a, então se n for primo teremos
n = 1 · n ou seja a = 1 e b = n assim o único valor possı́vel para x é x = ( n+1
2
).
Se n é composto e a = b então obtemos o resultado desejado na primeira etapa,
pois n seria um quadrado perfeito. Supomos então a 6= b e que 1 < a < b < n. Assim o
b+a n+1
teste acaba quando forem satisfeitas as desigualdades bnc ≤ 2
≤ 2
.
b+a
como 2
≥| n | então
b+a N +1
2
< 2
⇔ a + b < N + 1 = ab + 1
b+a N +1
2
< 2
⇔ a + b − b − 1 < ab + 1 − b − 1
b+a N +1
2
< 2
⇔ a − 1 < ab − b
b+a N +1
2
< 2
⇔ a − 1 < b(a − 1)
b+a N +1
2
< 2
⇔1<b

14
 Isto mostra que vale a desigualdade original. Como 1 < a < b vale por hipótese,
b+a n+1
está provado que 2
< 2
.
√ (a+b)2
Como bnc ≤ n, temos que verificar que n ≤ 4
é verdadeiro. Mas
(b+a)2 (b−a)2 (a+b)2
4
−n= 4
, é sempre não negativo, então temos que 4
− n ≥ 0.
Voltando ao método de Fermat, x é iniciado com o valor bnc e vai sendo
incrementado de uma em uma unidade, até que
(a+b)
x= 2

y 2 = ( a+b
2
)2 − n = ( a−b
2
)2
Esse método não envolve multiplicação nem divisão, mas o problema é a
enorme quantidade de execuções requeridas.
Atualmente esse método não é muito utilizado, porém ele contém a idéia base
de um dos mais poderosos algoritmos usados até hoje para fatorar números com grandes
fatores primos, que é o metodo Crivo Quadrático.
A seguir, apresentamos o algoritmo do método de Fermat que recebe um inteiro
positivo ı́mpar n e retorna o fator de n ou uma mensagem indicando que n é primo.

2.4 Algoritmo de Fermat

√
* Etapa 1: Comece com x = b nc; se x2 = n, então x é fator de n e pode-se
parar.
* Etapa 2: Caso contrário incremente x de uma em uma unidade e calcule
√
y= x2 − n.
* Etapa 3: Repita a etapa 2 até encontar um valor inteiro para y, ou até que
n+1
x seja igual a 2
.

15
Capı́tulo 3

Fatoração por Pollard Rho

Este método foi inicialmente chamado de “Método de Monte Carlo” por sua natureza
pseudo-randônica. Agora é mais conhecido como Método Rho [5].
Para fatorar um número n pelo método de Pollard Rho, supõe-se que n é um
inteiro grande, composto, e que p é seu menor divisor primo. O objetivo é escolher inteiros
x0 , x1 , ..., xs de forma que estes inteiros tenham resı́duos não negativos mı́nimos distintos,
módulo n. Usando argumentos probabilı́sticos, é provável que este seja o caso quando δ
√
é grande comparado a n, e os números são escolhidos randomicamente [5].
Depois de encontrarmos xi e xj , onde 0 ≤ i < j ≤ δ tal que xi ≡ xj (mod p)2
mas xi 6= xj (mod n), temos que mdc(xi − xj , n) pode ser encontrado rapidamente usando
o algoritmo de Euclides. Entretanto, encontrar mdc(xi − xj , n) para cada par (i, j) com
0 ≤ i < j ≤ δ requer que seja encontrado O(δ 2 ) máximos divisores comuns. Em seguida,
mostra-se, como calcular os xi e, logo em seguida como reduzir o número de vezes em que
o algoritmo de Euclides precisa ser usado [5].
Na prática, iniciamos procurando os números inteiros xi e xj . Começaremos
com um valor inicial x0 , que, é escolhido aleatoriamente, e uma função polinomial F(x)
arbitrária com coeficientes inteiros e grau maior que 1. Calculamos os termos xs , com
s = 1, 2, 3, ..., usando a definição recursiva

xs+1 ≡ f (xs )(mod n), 0 ≤ xs+1 < n

16
 O polinômio f (x) deve ter a propriedade que a sequência x0 , x1 , ..., xs , ... se
comporta como uma sequência aleatória. O exemplo a baixo mostra como é gerada esta
sequência.
Exemplo 1:
Seja n = 8051. Supomos x0 = 2 e f (x) = x2 + 1.
Então temos que se
f (xs+1 ) ≡ f (x)(mod(n));
f (x0+1 ) ≡ f (x2 + 1)(mod(n))
f (x1 ) ≡ f (22 + 1)(mod(8051))
f (x1 ) ≡ f (5)(mod(8051))
f (x1 ) ≡ 5;
f (x1+1 ) ≡ f (x1 )(mod(n))
f (x2 ) ≡ f (52 + 1)(mod(n))
f (x2 ) ≡ f (25 + 1)(mod(8051))
f (x2 ) ≡ f (26)(mod(8051))
f (x2 ) ≡ 26;
f (x2+1 ) ≡ f (x2 )(mod(n))
f (x3 ) ≡ f (262 + 1)(mod(n))
f (x3 ) ≡ f (676 + 1)(mod(n))
f (x3 ) ≡ f (677)(mod(8051))
f (x3 ) ≡ 677;
f (x3+1 ) ≡ F (x3 )(modn)
f (x4 ) ≡ F (6772 + 1)(modn)
f (x4 ) ≡ F (458329 + 1)(mod8051)
f (x4 ) ≡ F (458330)(mod8051)
f (x4 ) ≡ 7474;
f (x4+1 ) ≡ f (x4 )(mod(n))
f (x5 ) ≡ f (74742 + 1)(mod(n))
f (x5 ) ≡ f (55860676 + 1)(mod(8051))

17
 f (x5 ) ≡ f (55860677)(mod(8051))
f (x5 ) ≡ 2839;
f (x5+1 ) ≡ f (x5 )(mod(n))
f (x6 ) ≡ f (28392 + 1)(mod(8051))
f (x6 ) ≡ f (8059921 + 1)(mod(8051))
f (x6 ) ≡ f (8059922)(mod(8051))
f (x6 ) ≡ 871;
Assim encontramos os valores x1 = 5, x2 = 26, x3 = 677, x4 = 7474, x5 =
2839, x6 = 871, e assim por diante.
Temos pela definição recursiva de xs , que se
xi ≡ xj (mod(p)),
onde p é um inteiro positivo, então
xi+1 ≡ f (xi ) ≡ f (xj ) ≡ xj+1 (mod(p)).
Temos que, se xi ≡ xj (mod(p)), então essa sequência xs se torna periódica
módulo p com um perı́odo j − i. Então, xq ≡ xr (mod(p)) sempre que q ≡ r(mod(j-i))
que é no mı́nimo igual a i, então xs ≡ x2s (mod(p)).
Para acharmos um fator de n, devemos encontrar o mdc(x2s − xs , n) para
s = 1, 2, 3, .... Sabemos que esse fator de n foi encontrado quando aparecer um valor s
para o qual 1 < x2s − xs < n. Podemos perceber que é provável que tal s seja encontrado
√
próximo a p.
O polinômio f (x) = x2 + 1 é frequentemente escolhido para gerar a sequência
de inteiros x0 , x1 , x2 , ..., xs ,..., pois um polinômio linear f (x) = ax + b não será aleatório
o suficiente para esse propósito. Além disso, o valor inicial x0 = 2 tambem é muito usado.
Esta escolha de valor inicial e de polinômio produz uma sequencia que se comporta como
uma sequência aleatória quando este método é usado.
Exemplo 2:
Encontrar um valor não trivial de n = 8051 usando o método Rho com valor
inicial x0 = 2 e o polinômio f (x) = x2 + 1. No exemplo anterior encontramos x1 =5, x2
=26, x3 =677, x4 =7474, x5 =2839, x6 =871.Usando o algoritmo de Euclides segue que

18
mdc(x2 − x1 ,8051)=mdc(26 - 5,8051)=mdc(21,8051)=1 e mdc(x4 − x2 ,8051)=mdc(7474
- 26,8051)=mdc(7448,8051)=1. No entando, um fator não trivial de 8051 é encontrado
no próximo passo, pois mdc(x6 − x3 ,8051)=mdc(871 - 677,8051)=97. Portanto, 97 é um
fator de 8051.
Pode-se ver que este método é chamado de método Rho, observando o com-
portamento da sequência xi onde x0 = 2 e xi+1 = x2 i+1 = (x2 i + 1)(mod 97), i ≥ 1.
Podemos observar que existe uma parte não periódica, que ocorre antes da periodicidade
e é a cauda do Rho, e uma parte periódica que é o laço.
O método Rho é prático para a fatoração de inteiros com fatores primos mode-
radamente grandes. Em 1980, R. P. Brent propôs uma mudança na forma do algoritmo.
Para tentar evitar armazenar valores dos x0i s, ele sugeriu o cálculo das diferenças:
x1 − x3 ; x3 − x6 ; x3 − x7 ; x7 − x12 ; x7 − x13 ; x7 − x14 ; x7 − x15 ;
resumindo:
n−1
x2 − xj , 2 n +1
- 2n −1
≤ j ≤ 2n +1
- 1.
O importante é a diferença entre coordenadas, onde aumenta um a cada vez.
A menor coodernada é mantida até garantir que saia do intervalo.
Muitos mdc’s tem que ser calculados, normalmente milhares ou mais. Temos
então uma economia substancial de tempo se for tomado o produto de, vamos dizer, dez
valores sucessivos de (xi −xj )(modn) e se depois for calculado o mdc daquele produto com
n. Se for verificar que o mdc é n, volta-se aqueles últimos dez valores e será feito o mdc
de n com cada um deles. No entanto se n divide o produto de dez diferenças sucessivas,
ele normalmente divide exatamente uma destas diferenças.
Em geral, pode-se esperar que o número mı́nimo de ciclos necessários esteja
próximo da raiz quadrada do menor primo dividido por n. Isto porque a sequência dos
xi normalmente se comporta como se eles fossem aleatórios.
A probabilidade de que não haja repetições entre os primeiros t termos da
sequência é então

p
. . . p−(t−1)
p−1 p−2
. p p
e esta probabilidade diminui aproximadamente 50 porcento
√
quando t se aproxima de p.

19
Capı́tulo 4

Método de Fatoração p-1

O pequeno teorema de Fermat é a base do método de Pollard, inventado por J. M. Pollard

em 1974, e ficou conhecido como Método p-1. Com ele podemos encontrar um valor não
trivial de um inteiro n que tem um fator primo p tal que os primos que dividem p-1 são
relativamente primos e pequenos [5].
Para se utilizar esse método deve-se supor que se deseja encontrar um fator
inteiro positivo n . Além disso supõe-se que n tem um fator primo p de tal forma que
p − 1 divide k! onde k é um inteiro não muito grande e deseja-se que p − 1 tenha
apenas fatores pequenos. Por exemplo, se p = 2269 então p − 1 = 2268 = 22 34 7 ,de
forma que p − 1 divide 9! mais não divide nenhum fator menor que a função fatorial.
Pelo Pequeno Teorema de Fermat, se a, b, m são inteiros tais que m > 0 e se
a ≡ r(mod m) então se diz que r é um resı́duo de a módulo m .
Como p divide k! então k! = (p − 1)q . Portanto,

2k! = 2(p−1)q = (2p−1 )q ≡ 1q = 1 (mod p)

o que implica que p divide 2k! − 1 , de forma que M = (2k! − 1) − nt para qualquer
t inteiro. Assim p divide M , já que p divide ambos, 2k! − 1 e n .
Agora para encontrar um divisor de n é preciso somente calcular d = mdc (M, n).
Isto pode ser calculado usando o algoritmo de Euclides.

20
 Para que um divisor d, não seja um divisor trivial é preciso que M não seja
nulo. Este é o caso quando o próprio n não divide 2k − 1, o que é provável quando n tem
divisores primos grandes.
Na prática, para se usar esse método devemos calcular 2k! módulo n, com
k = 0, 1, 2, ... . Podemos fazer isso através de exponenciação modular. Para encontrar
o menor valor de 2k! módulo n fixamos r1 = 20! e usaremos a seguinte sequência de
cálculos:

r2 ≡ r12 (mod n), r3 ≡ r23 (mod n), rk ≡ rk−1

k
(mod n)

Pois 2(n+1)! = 2(n+1)n! = (2n! )(n+1)

Exemplo:
Para encontrar 29! (mod 5157437) devemos realizar as seguintes sequências de
cálculos:
r2 ≡ r12 ≡ 22 ≡ 4 (mod 5157437)
r3 ≡ r23 ≡ 43 ≡ 64 (mod 5157437)
r4 ≡ r34 ≡ 644 ≡ 130495 (mod 5157437)
r5 ≡ r45 ≡ 1304955 ≡ 404913 (mod 5157437)
r6 ≡ r56 ≡ 4049136 ≡ 2157880 (mod 5157437)
r7 ≡ r67 ≡ 21578807 ≡ 4879227 (mod 5157437)
r8 ≡ r78 ≡ 48792278 ≡ 4379778 (mod 5157437)
r9 ≡ r89 ≡ 43797789 ≡ 4381440 (mod 5157437)
segue que

29! ≡ 4381440 (mod 5157437)

O exemplo a seguir mostra o uso do método p-1 de Pollard para encontar um

fator do número inteiro 5157437.
Exemplo:

21
 Para fatorar o número 5157437 usando o método p-1, encontramos sucessiva-
mente rk , que é o menor resto positivo de 2k! módulo 5157437 para k = 1, 2, 3, ..., como
no exemplo anterior. Calculamos mdc(rk − 1, 5157437) em cada passo. Para encontramos
um fator de 5157437 precisaremos de 9 passos pois mdc(rk − 1, 5157437) = 1 para k = 1,
2, ...,8. Mas mdc(r9 − 1, 5157437) = mdc(4381439, 5157437) = 2269, assim temos que
2269 é um divisor de 5157437.
Na prática não se sabe o quão próximo de n precisamos chegar antes de encon-
tar o primeiro valor primo. Como não queremos que todos sejam encontrados precisamos
verificar periodicamente o valor de mdc(ck! − 1, n) onde c é um inteiro positivo e primo
com relação a n. Se for 1, precisamos continuar com o teste. Se for n, então já passamos
todos os divisores de n, sendo nescessário tentar um valor diferente de c, ou tentar um
algoritmo diferente. Se não for nem 1 nem n então encontramos o divisor não trivial que
procuramos [5].
Este método nem sempre funciona. Mas, como o método não depende da base
escolhida, podemos encontrar fatores de outros inteiros usando bases diferentes de 2, desde
que tais bases sejam relativamente primas a n [5].
Na prática, a primeira tentativa de fatorar um inteiro grande n é fazer divisão
por tentativas por todos os primos menores que n, ou então aplicar o método de Fermat,
se já sabemos que existem fatores próximos da raiz de n [5].

22
Capı́tulo 5

Discussão sobre os Métodos de

Fatoração

Os métodos Rho e P-1 são usados para encontrar valores primos de tamanho intermediário
valores de até 105 . Depois desses métodos falharem é que devemos usar métodos mais
poderosos como por exemplo o método Crivo Quadrático. [5]
O método de fatoração de Fermat tem algumas caracterı́sticas importantes. A
principal delas é que as iterações não envolvem multiplicação ou divisões, de forma que
eles tem um tempo de execução extremamente rápido. O problema é o enorme número
de execuções requeridas. O método de Fermat funciona na direção oposta à da divisão
por tentativas. O método de divisão por tentativas começa procurando fatores pequenos
e continua até a raiz quadrada de n, ja no método de Fermat começa procurando fatores
√
próximos à raiz quadrada de n e continua procurando fatores menores que n [5].
Atualmente este método não é muito usado a menos que se saiba que o número
a ser fatorado tem dois fatores que estão relativamente próximos à sua raiz quadrada, mas
ele contém a idéia por trás de um dos mais poderosos algoritmos usados hoje para fatorar
números com grandes fatores primos, o método do Crivo quadrático [5].
Os métodos de Pollard Rho e p-1 são chamados de algoritmos probabilı́sticos,
pois fazem escolhas aleatórias durante o processo de fatoração existindo uma probabilidade

23
de fatorar ou não fatorar um dado número. O método Rho é prático para a fatoração
de inteiros com fatores primos moderadamente grandes. Em geral, pode-se esperar que o
número de ciclos necessários esteja em torno da raiz quadrada do menor primo dividindo
n [5].

24
Conclusão

O estudo de métodos de fatoração de inteiros merece destaque devido a sua aplicação em

sistemas criptográficos como o RSA, que tem sua segurança baseada na ineficiência dos
métodos existentes.
Existem diversos métodos de fatoração dentre os quais estão os métodos de
Fermat, Pollard Rho e Pollard p-1.
Esse trabalho apresentou um estudo teórico dos métodos de Fermat, Pollard
Rho e Pollard p-1, a partir de uma descrição do funcionamento dos mesmos.
Para trabalhos futuros sugere-se um estudo prático desses métodos de fatoração
por meio de implementações computacionais.

25
Referências Bibliográficas

[1] COUTINHO, S. C. Números Inteiros e Criptografia RSA. Rio de Janeiro: IMPA

/SBM, 2000.

[2] DOMINGUES, H. H. ; IEZZI, G. Álgebra Moderna. - 3a edição - São Paulo: Atual,

1982.

[3] MILIES, Cézar Polcino ; COELHO, Sonia Pitta. Números: Uma Introdução à
Matemática - 3a edição - São Paulo: Editora da Universidade de São Paulo, 2001.

[4] CRANDALL, Richard ; POMERANCE, C. Prime Numbers - A Computational Per-

spective. Springer - Verlag, 2002.

[5] ANTUNES, Cristiane Medina. Métodos de Fatoração de Números Inteiros .

Universidade Federal do Rio Grande do Sul.Dissertação de Mestrado. porto Alegre,
outubro de 2002.

[6] Pierrre de Fermat (1601 - 1665). Texto disponivel em:

http : //www.im.uf rj.br/dmm/projeto/diversos/F ermat1.html

[7] Aspectos de Segurança. Texto disponivel em:

http : //www.redes.unb.br/security/criptograf ia/curvaselipticas/seguranca.html

[8] Número Primo. Texto disponivel em:

http : //matematicamania.wordpress.com/category/divisibilidade/