Ideia para solucao do problema de fatoracao. Minha ideia para encontrar algum fator não trivial de um inteiro composto N, em linhas gerais, eh a seguinte:
[Passo 0] Comece com um natural P par. O ideal seria que fosse P = n# (primorial de n, isto eh, o produto de todos primos menores ou iguais a n), ou P = n!, com n razoavelmente grande. Se MDC(N, P) eh maior que 1 e menor que N, então encontramos um fator. [Passo 1] Eh claro que P + 1 e P - 1 são relativamente primos com P. Então P + 1 e P - 1 tem, ambos, fatores primos que não estao em P. Note que sendo P par, então P + 1 e P - 1 sao coprimos. Essa coprimalidade 2 a 2 vai continuar nas proximas etapas. Fassa P[0] = P - 1 P[1] = P + 1 (O zero indica subtração e 1 indica soma) e Calcule MDC(N, P[0]) Calcule MDC(N, P[1]) Se algum desses MDC for maior que 1 e menor que N, encontramos um fator. Note que como P[0] e P[1] sao relativamente primos com P, e tambem primos entre si, então diferentes fatores primos foram testados. A minha ideia aqui eh "acumular fatores primos distintos" em certos numeros naturais e depois verificar por MDC se ha fatores em comum, como verao adiante. [Passo 2] Fassa P[0, 0] = P * P[0] - 1 = PP - P - 1 P[0, 1] = P * P[0] + 1 = PP - P + 1 P[1, 0] = P * P[1] - 1 = PP + P - 1 P[1, 1] = P * P[1] + 1 = PP + P + 1 (o zero posicional indica subtracao e o 1 soma) Calculemos o MDC de cada um desses quatro numeros com N. Se algum desses MDC for maior que 1 e menor que N, então encontramos um fator. Note que cada um desses numeros eh relativamente primo com P, com P[0] e com P[1]. Mais: eu pude verificar que os 4 (quatro) numeros obtidos no [PASSO 2] sao 2 a 2 coprimos (!) pois a diferenca entre eles ou teria que ser par (nao eh) ou teria que ser divisivel por P (tambem nao eh). Entao varios novos fatores primos foram testados aqui. [Passo 3] Se ainda nao encontramos algum fator, continuamos como jah estamos fazendo, para obter 8 (oito) numeros dois a dois coprimos. Multiplicamos cada um dos 4 (quatro) numeros obtidos Por P, e depois somamos e subtraimos 1 de cada produto, resultando em 8 (oito) numeros dois a dois coprimos, como jah vimos, e coprimos com todos os anteriores P[0, 0, 0] = = P * ( P[0, 0] - 1) - 1 = = PPP - PP - P - 1 P[0, 0, 1] = P * ( P[0, 0] - 1) + 1= = PPP - PP - P + 1 P[0, 1, 0] = = P * ( P[0, 1] + 1) - 1 = = PPP - PP + P - 1 P[0, 1, 1] = PPP - PP + P + 1 P[1, 0, 0] = PPP + PP - P - 1 P[1, 0, 1] = PPP + PP - P + 1 P[1, 1, 0] = PPP + PP + P - 1 Calculamos o MDC de cada um desses oito numeros com N. Se o MDC for maior que 1 e menor que N, encontramos um fator. Como todos esses 8 numeros sao dois a dois coprimos, muitos fatores primos distintos foram testados. Vamos obter uma arvore que se bifurca em dois ramos, ao multiplicarmos cada numero por P e somarmos ou subtrairmos 1 de cada produto. Eh como se considerassemos sucessivamente todas as funcoes polinomiais de grau de 1 ateh m em que o coeficiente lider eh 1 e os demais coeficientes sao 1 ou -1. E depois calculassemos o MDC do valor numerico de cada um desses polinomios aplicado em P. Como os numeros P[ X, Y, ...] sao dois a dois coprimos, então muitos fatores primos serão testados (note que P nao eh o mesmo que P[ X, Y, Z, ...], onde X, Y, Z podem ser 1 ou -1) Acho que eh uma ideia valida. Muito melhor que a de meu email anterior. Alguem pode comentar esse algoritmo? Rodar num sistema de computacao algebrica, tipo Maple ou algo do genero? Pedir a uma IA para rodar esse algoritmo? (sim, elas fazem isso, mas estao cometendo erros grosseiros em contas de aritmetica basica) Abracos fraternos [EricCBGuedes][02-maio-2025] -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
