Prova da existência da

solução de Euler e algumas novas propostas para a fatoração de inteiros

Almir Paz de Lima

Dep. Eng. Produção

UFF – Niterói / RJ

RESUMO:

Prova-se a existência da solução de Euler para a fatoração de inteiros e propõe-se um enfoque que permite tratar, com vantagem, vários métodos de fatoração existentes, via um paralelismo natural na busca de soluções.

Anuncia-se a generalização da fatoração de Fermat para números poligonais e a próxima conclusão da generalização do método de Euler para os mesmos números.

1 – Fatoração de Euler

Seja n um inteiro positivo, com:

D² = t² N + n (1)

onde D, t, N são inteiros.

Se N = h², h inteiro,

n = (D - th) (D + th) (2)

que é a fatoração de Fermat [1].

Se N não é quadrado, segundo Euler [2], procura-se uma segunda equação:

G² = a² N + n (3)

com G, a inteiros, G² ¹ D² .

Multiplicam-se (1) por a² e (3) por t² e subtraem-se os resultados:

a² D² – t² G² = (a² – t²) n (4)

De (4), se:

mdc (aD + tG, n) = b,

b ¹ 1 e b ¹ n,

b é fator não trivial de n.

Registros históricos disponíveis indicam que Euler não teria provado a existência da segunda equação (3), essencial para o método.

A construção exposta a seguir prova a existência de (3) e sugere um método de fatoração que generaliza métodos descritos na literatura, com a vantagem, entre outras, de permitir um paralelismo natural na busca de soluções.

Natural aqui quer dizer, por exemplo, sem deixar o anel dos inteiros, em oposição ao paralelismo buscado na construção de curvas elípticas distintas. [3]

2 – Prova da existência da solução de Euler

Tudo o que se segue é válido para a fatoração de

n = 1 mod 4.

Para n = 3 mod 4, as soluções podem ser adaptadas por simples troca de sinais e modificações nas definições.

Por exemplo:

4N + n = D² transforma-se em:

4N – n = D², e

a = (q – p) / 4 em a = (p + q) / 4.

Mais objetivamente, se n = 3 mod 4, fatora-se

3n = 1 mod 4.

Não há, insiste-se, perda de generalidade em supor

n = 1 mod 4. (5)

Claro, também, que qualquer fatoração de um número grande só será tentada depois da verificação de que n não é primo nem quadrado perfeito.

Sejam então, n = 1 mod 4,

n = pq,

p, q ímpares, p < q.

Definem-se:

a = (q – p) / 4, (6)

r = (p + q) / 2. (7)

Note-se que, de (5), (6), (7), a é inteiro e r é ímpar.

Sejam ℓ inteiro e

D = r - 2ℓ (8)

É fácil ver que D é ímpar e que D² – n é múltiplo de 4.

Assim,

D² = 4N + n, N inteiro. (9)

Teorema 1

a² = N + ℓD + ℓ² (10)

Prova: De (9),

N = (D² – n) / 4 (11)

Substituindo D, de (8) em (11):

N = (r² + 4ℓ² - 4ℓr – n) / 4 (12)

De (6), (7) e n = pq,

r² – n = 4a² (13)

Substituindo (13) em (12);

N = a² + ℓ² - rℓ (14)

De (8),

r = D + 2ℓ (15)

Substituindo (15) em (14):

a² = N + ℓD + ℓ²

cqd.

De (9), a primeira equação de Euler (1), foi obtida com

t = 2f (N pode ser f²N’), para qualquer D inteiro (positivo ou não!) ímpar.

Provar-se-á, agora, que a segunda equação (3) ocorrerá com G = 2N + ℓD, (16)

G² = (2a)² N + ℓ² n. (17)

Não há perda de generalidade na introdução do fator ℓ² em n, a saber:

Multiplicando-se ambos os membros de (9)

por ℓ², tem-se:

D² ℓ² = 4Nℓ² + ℓ²n. (18)

Admitindo-se (17), conclui-se, como na obtenção de (4);

ℓ² G² - ℓ² a² D² = ℓ² (ℓ² n - a²n). (19)

Se ℓ = 0, N = a ² , por (10), e não haveria necessidade da segunda equação de Euler,

n seria fatorado por (1).

Admite-se ℓ ¹ 0, e, de (19),

G² - a² D² = (ℓ² - a²) n. (20)

De (17), se ℓ² = a² ,

G² = 4Nℓ² + ℓ² n,

D² = (G / ℓ)² = 4N + n.

Assim, ℓ² - a² ¹ 0 e ...

de (20), como em (4),

tem-se a fatoração de n,

se mdc (G - aD, n) = g, g ¹ 1, g ¹ n.

Teorema 2 (Segunda Equação de Euler)

Se G = 2N + ℓD,

G² = (2a)² N + ℓ² n.

Prova: Seja G = 2N + ℓD.

Então ... G² = 4N² + ℓ² D² + 4NℓD. (21)

Subtraindo ℓ²n a ambos os membros de (21),

G² - ℓ² n = 4N² + 4NℓD + ℓ² (D² – n). (22)

De (9), D² – n = 4N. (23)

Substituindo (23) em (22),

G² - ℓ² n = 4N (N + ℓD + ℓ²). (24)

Mas, de (10),

N + ℓD + ℓ² = a².

Substituindo em (24),

G² = 4N a² + ℓ² n.

cqd.

Exemplo 1

Seja fatorar n = 37 x 277 = 10249 = 1 mod 4.

Se D = 121 (ímpar, arbitrário),

r = 157, a = 60,

N = (D² – n) / 4 = 1098; ℓ = (r - D) / 2 = 18,

G = 2N + ℓD = 4374.

G - aD = 2886

mdc (G - aD, n) = mdc (2886, 10249) = 37

3 – Alguns novos resultados

3.1. – Registre-se que, de ...

N + ℓD + ℓ² = a²,

tem-se, para cada primo ímpar g, um crivo (cf crivo de Eratóstenes) para valores de ℓ, ie, determinam-se valores de ℓ que não satisfazem a condição:

D = r - 2ℓ. (8)

Exemplo 2

n = 10249, a = 60, r = 157, como no exemplo anterior.

Seja D = 129 (por (8), ℓ = 14)

(Quem tenta a fatoração de n não conhece r, nem ℓ).

De (9), N = 1598.

Seja g = 7 e faça-se:

N + ℓD + ℓ² = a² mod 7

ie,

2 + 3ℓ + ℓ² = a² mod 7 (25)

Os possíveis quadrados, mod 7, são 0, 1, 2, 4. Assim, valores de ℓ que fizerem o lado esquerdo de (25) igual a 3, 5, ou 6 não podem ocorrer.

ℓ = 1 mod 7, em (25), faz 6 = a², absurdo.

Logo, ℓ ¹ 1 mod 7.

Testando os valores 0, 1, 2, 3, 4, 5, 6 para ℓ, verifica-se que ℓ ¹ 1, 2, 3 mod 7 e, a propósito,

que a² = 0 ou 2 mod 7.

Realmente, ℓ = 14 = 0 mod 7 e a² = 3600 = 2 mod 7.

3.2. – De ...

D² = t² N + n (1)

e

G² = a² N + n, (3)

tem-se:

(G² - D²) = (a² - t² ) N. (26)

Seja w um fator primo de N. De (26), w é divisor de

(G - D) (G + D).

De teorema conhecido, w divide (G - D) ou (G + D), ie,

G = +D mod w ou G = - D mod w. (27)

A busca de G, por tentativas, pode então ser feita, não por valores consecutivos como em [2], mas por saltos que dependem de w, como se verá no Exemplo 3.

Pode-se provar que, para ...

D² = t² N + n , (1)

se ℓ é divisor de ta, então

a = (ta) / ℓ é uma solução de (3).

Mostra-se, no Exemplo 3, que

a = (ta) / ℓ é uma condição suficiente, mas não necessária, ie, existem soluções que não atendem a condição.

Exemplo 3

Seja fatorar n = 43 x 523 = 22489

a = 120, r = 283.

Se D = 155, ℓ = 64

155² = 16² x 6 + n, D² = t² N + n.

t = 16 , a = (16 x 120) / 64 = (ta) / ℓ = 30.

a² N + n = 30² x 6 + n = 167².

Se D = 163, ℓ = 60,

163² = 4² x 255 + n,

a = (4 x 120) / 60 = 8.

8² x 255 + n = 197².

Note-se: D’s diferentes levaram à fatoração, e a condição suficiente foi atendida.

Sejam agora:

D = 157 , ℓ = 63,

157² = 12² x 15 + n,

t = 12, N = 15.

Note-se que ℓ = 63 não é divisor de ta = 12 x 120, mas a equação (3) tem solução, obtida por busca a partir de (27),

G = ± D mod w, w primo, w divisor de N.

No caso, G = ± 157 mod 3,

G = ±157 mod 5.

Daí, G = 2, 7, 8 ou 13, mod 15

ie, G = 15t + 2, 15t + 7, 15t + 8, 15t + 13.

Fazendo a busca para G > D,

tem-se G = 158, 163, 167, 172, ... , 227.

227² = 44² x 15 + n.

G foi obtido na 19 ª tentativa.

Observe-se, também, que, como no método de Fermat, podem-se compor equações que não resolvem o problema para obter uma solução.

Ainda no exemplo acima,

158² = 165 x 15 + n , 165 = 5 x 11 x 3

163² = 272 x 15 + n , 272 = 2⁴ x 17

167² = 360 x 15 + n , 360 = 2² x 3² x 2 x 5

.

.

.

.

197² = 1088 x 15 + n , 1088 = 8² x 17

Note-se que 272 x 1088 = 2⁴ x 8² x 17²

é um quadrado.

Multiplicando-se as duas equações:

(163 x 197)² = (15 x 2 x 272)² + vn, v inteiro.

[(163 x 197) + (30 x 272)] [(163 x 197) – (30 x 272)]=vn

(32111 + 8160) (32111 – 8160) = vn

mdc (40271, n) = 523

Note-se que a solução também existe se for necessário um número ímpar de equações para gerar o quadrado, porque aí ter-se-á (com 3 equações, sem perda de generalidade):

(G₁G₂G₃)² = T² N + un,

como a 2 ª equação de Euler.

3.3. – Como visto no exemplo anterior, cada D ímpar, arbitrário, gera um “universo de fatoração” para o método de Euler, o que sugere uma forma natural para fazer a fatoração por paralelismo.

3.4. – São conhecidos os números poligonais,

g (a, k) = ((k – 2) a² – (k – 4) a) / 2 , onde ...

a é natural e k = 3, 4, ... é o número de lados do polígono.

Uma generalização do método de Fermat pode ser obtida considerando-se que a fatoração de Fermat ocorre quando o número n é escrito como a diferença de 2 números poligonais de ordem 4, quadrados.

Assim, por exemplo, se ...

K = 3, g (a, 3) = (a² + a) / 2.

Pode-se escrever o número n como a diferença de 2 números triangulares:

(a² + a) / 2 - (b² + b) / 2 = n

(a² - b²) + (a – b) = 2n

(a – b) (a + b + 1) = 2n

Para n = pq , a – b = p, a + b + 1 = q,

a = (p + q – 1) / 2 , b = (q – p – 1) / 2

Sem entrar em detalhes, pode-se mostrar que, para

l = q / p, a fatoração de Fermat é mais eficiente (tem menor número de tentativas) se l é próximo de 1, e a fatoração por diferença de triangulares é melhor para l próximo de 2.

Conseguiu-se uma generalização do método aqui seguido para números triangulares.

A primeira equação de Euler seria:

4N + n = G (G + 2), G ímpar qualquer

e a segunda ...

a² N + n = S (S + a)

A prova da existência da 2 ª equação não foi concluída, mas parece viável pelos resultados até agora obtidos.

Tem-se:

(2b)²N + ℓ²n = S(S + 2b), 2b = (q – p) / 2, q + p = 0 mod 4

A construção precisa ser feita para n = 3 mod 4.

Por exemplo, a fatoração de 6767 x 3 = 20301 pelo método de Euler para quadrados foi feita em 17 passos com D = 143. A mesma fatoração, com a método Euler-triangular se obteve em 7 passos.

Referências

1. S. C. Coutinho

Números Inteiros e Criptografia RSA.

IMPA / Soc. Bras. Matemática

Rio de Janeiro – 1997.

2. H. Riesel

Prime Numbers and Computer Methods For Factorization

2nd ed.

Birkhauser – Berlin – 1994.

3. D. M. Bressoud

Factorization And Primality Testing

Springer – New York – 1989.