Parcelamento e Troca de Valores de Entrada no Método Binário de Congruência

Abstract

Neste artigo, será apresentado o método binário para verificação de congruência de grandes números, como parte do teste de primalidade. Decompor um número de mais 17 milhões de dígitos ou confirmá-lo como número primo não é trivial. Com o advento da computação e a capacidade de processamento das máquinas, os estudos vêm evoluindo com muita rapidez, porém o custo computacional ainda é muito grande, levando-se em consideração, por exemplo, o teste de primalidade de 257885161-1. Como resultado serão apresentadas duas alterações no algoritmo: o parcelamento do expoente binário com o intuito de reduzir o número de iterações; e a troca do resto da congruência priorizando sempre o de menor valor, reduzindo o rmax (resto máximo) em menos da metade em relação a proposta inicial do algoritmo.