test de primalidad

5/16/2018 Test de Primalidad - slidepdf.com

http://slidepdf.com/reader/full/test-de-primalidad 1/7

Prueba de Primalidad

Rodolfo A. Nieves Rivas*

[email protected]

[email protected]

[email protected]

*Autodidacta en estudios matemáticos

RESUMEN

En este trabajo se presenta una prueba de primalidad basada en algunos teoremas quepermiten crear las bases para su desarrollo y confiabilidad en tiempo polinomial.

En otras palabras esta prueba de primalidad atiende el problema sobre la determinación

de si un número (n) dado es primo o no, y de igual forma se puede realizar un algoritmo

con el cual obtener un número primo aleatorio dada una entrada.

Cuestión que es conocida como el problema de la primalidad y todo esto nos conduce a

resolver de una manera sencilla este problema el cual es el objetivo de esta

investigación.

Palabras claves: prueba, algoritmo, primo

ABSTRACT

This paper presents a primality test based on some theorems that allow to create the

foundations for its development and reliabil ity in polynomial time.

In other words this test of primality addresses the problem of determining if a given

number (n) is prime or not, and likewise an algorithm can be designed to get a random

prime number, given an input.

This fact is known as the problem of primality and all this leads to a simple way of

solving this problem which is the objective of this research.

Keywords: test, algorithm, prime

mailto:[email protected]











INTRODUCCION

Existen hasta los momentos algunas pruebas de primalidad las cuales tienen

aplicaciones puntuales para resolver el problema de la primalidad, las cuales presentan

limitaciones que conducen a considerarlas no satisfactorias para resolver el problema

sobre la determinación de si un número (n) dado es primo o no.

Las ventajas que tiene esta nueva prueba de primalidad consiste en que el diseño del

algoritmo con el cual se desarrolla el software donde se evita tener que realizar la

factorización siendo esta el mayor obstáculo presente hasta la fecha en la práctica dado

que aún no se ha encontrado una solución que permita acotar la misma en tiempo

polinomial y esto nos conduce a un desarrollo óptimo que nos garantiza afirmar el grado

de certidumbre.

Por todo lo anterior se presenta este trabajo de investigación con el fin de aportar a la

comunidad científica las bases que garantiza la solución definitiva de este problema.

PLANTEAMIENTO DEL PROBLEMA

La elaboración de un algoritmo que permita el diseño de un software que sea

aplicado en una prueba de primalidad.

MARCO TEÓRICO

Definición 1: Un test (o chequeo) de primalidad es un algoritmo que, dado un número

de entrada n, no consigue verificar la hipótesis de un teorema cuya conclusión es que n

es compuesto.

Definición 2: Un algoritmo de prueba de primalidad (o test verdadero de primalidad) esun algoritmo determinístico que, dado un número de entrada n, verifica la hipótesis de

un teorema cuya conclusión es que n es primo. Una prueba de primalidad es laverificación computacional de dicho teorema.

Así pues se puede hablar de dos grados de certidumbre: las pruebas de primalidad

(existe certidumbre matemática) y los tests de primalidad (existe certidumbre práctica).



BASES TEÓRICAS

TEOREMA 1: El producto de n primos diferentes, tiene dos elevado a la n divisores.

TEOREMA 2: El producto de dos primos diferentes tiene cuatro divisores y nada más

que cuatro.

TEOREMA 3: Si el producto de dos primos diferentes tiene cuatro divisores y nada más

que cuatro. Entonces los divisores son: El producto; Los dos primos y la unidad.

TEOREMA 4: Si un múltiplo de diez mas cinco tiene solo y nada mas que cuatro

divisores propios. Entonces es producto de dos primos diferentes de los cuales uno de

ellos es el numero cinco.

ESCOLIO 1: Y los cuatro divisores propios de un múltiplo de diez mas cinco son: La

unidad; El cinco; El múltiplo de diez mas cinco y otro primo.

COROLARIO 1: Si los cuatro divisores propios de un múltiplo de diez mas cinco son:

La unidad; El cinco; El múltiplo de diez mas cinco y otro primo. Entonces el múltiplo

de diez mas cinco es producto de cinco por este otro primo.

TEOREMA 5: Todo número natural que termina en cinco es un múltiplo de diez más

cinco.

CRITERIO 1: Para demostrar que dos números diferentes son primos, solo es necesario

y suficiente determinar que el producto de los mismos tiene cuatro y nada más que

cuatro divisores propios.

TEOREMA 5: Si el producto de dos números impares, donde uno de ellos es el número

cinco, tiene más de cuatro divisores propios. Entonces el otro número es compuesto.

ANÁLISIS Y RESULTADOS

ALGORITMO: PARA LA OBTENCIÓN DE UN NÚMERO PRIMO

ALEATORIO

BASADO: TEOREMAS

ENTRADA: Elíjase un número natural (n) arbitrario con cualquier cantidad de dígitos;

con la condición que el último dígito de este número sea el cinco.



Realice ((x - 5)/10) – 1 iteraciones hasta encontrar un cociente exacto.

Justificación

COMO: La entrada es de la forma: 10.k + 5 = x

DONDE: K es la constante

Y CUANDO: El cociente es exacto y de la forma: 10.K + 5 / 10.m + 5

DONDE: m y k sean naturales

PARA: 0 < m < k

ENTONCES: 2.n + 1 es igual al cociente

SI: En la ejecución de la búsqueda, se encuentra un cociente exacto; deténgase la

ejecución y la Salida expresaría un número compuesto.

ENTONCES: Con esto queda demostrado que existe al menos un valor para m E IN

donde n sea natural.

SALIDA: 10.k + 5 / 10.M + 5 = 2.n + 1 (Compuesto)

DONDE: k = n y m =0

SI: En la búsqueda, no se encuentra un cociente exacto; realícese todas las

iteraciones y la salida en este caso es un número primo.

ENTONCES: Con esto queda demostrado que no existe ningún valor para m natural

donde n sea natural.

SALIDA: 10.k + 5 / 10.M + 5 = 2.n + 1 (Primo)

DONDE: k = n y m =0

He de resaltar que una vez realizado este análisis y haber obtenido este resultado que

nos permite demostrar que hemos cumplido con el objetivo de esta investigación; el

cual era elaborar un algoritmo con el cual diseñar un software que nos garantice el

poder presentar una prueba de primalidad eficiente, suficiente y satisfactoria que nos

permita asegurar cuando un número es primo o compuesto.



Dado que el número de iteraciones viene determinado por el número en la entrada; esto

nos garantiza que el tiempo es polinomial y los teoremas con los cuales se fundamenta

todo el desarrollo de este algoritmo, son los que de una forma deductiva nos despejan

cualquier duda sobre la validez en la ejecución del software, lo cual queda demostrado

en forma inductiva.

Desarrollo interno del software:

10.k + 5 / 10.m + 5 = 2.n + 1

10.40 + 5 / 10.0 + 5 = 2.40 + 1 (es compuesto)

10.40 + 5 / 10.l + 5 = 2.13 + 1

10.40 + 5 / 10.2 + 5 ≠ 2. m + 1

10.40 + 5 / 10.3 + 5 ≠ 2. m + 1

10.40 + 5 / 10.4 + 5 = 2.4 + 1

10.40 + 5 / 10.5 + 5 ≠ 2. m + 1

10.40 + 5 / 10.13 + 5 = 2.1 + 1

10.40 + 5 / 10.40 + 5 = 2.0 + 1

Nota 1: cuando la división es exacta en al menos uno de los pasos intermedios el

proceso en el algoritmo al igual que en el software se detiene y se ejecuta el siguiente

paso: e cual es realizar el cociente de los términos extremos y el resultado final o salida

es un compuesto

10.k + 5 / 10.m + 5 = 2.n + 1

10.3 + 5 / 10.0 + 5 = 2.3 + 1 (es primo)

10.3 + 5 / 10.l + 5 ≠ 2.2 + 1

10.3 + 5 / 10.2 + 5 ≠ 2.1 + 1

10.3 + 5 / 10.3 + 5 = 2.0 + 1



Nota 2: Cuando la división es inexacta en todos y cada uno de los pasos intermedios el

proceso en el algoritmo al igual que en el software no de se detiene hasta haber

realizado todos y cada uno de los pasos y al finalizar ejecuta el siguiente paso: el cual es

determinar el cociente de los términos extremos y el resultado final o salida es un

número primo.

CONCLUSIONES Y RECOMEDACIONES

Una vez presentados todos los resultados obtenidos a través del análisis del

algoritmo se llega a la siguiente conclusión con el desarrollo de un software que se

diseñe con las bases que han sido demostradas en esta investigación nos garantiza una

amplia aplicación en la solución definitiva de algunos problemas tales como:

- Los primos de Mersenne

- Los primos de Fermat

- Los primos de Gauss

- La hipótesis de Golbach (Par e Impar)

- La hipótesis de Riemann

- Y todo lo relacionado con los números primos entre otros.

Cabe resaltar que todos estos problemas están aun pendiente dado que hasta la fecha

la dificultad estaba en la solución del problema que en esta investigación se ha

presentado y por lo cual se propone el diseño de este software a fin de permitir el

avance de la ciencia lo cual es el propósito de todo investigador.



BIBLIOGRAFIA

es.wikipedia.org/wiki/Test_de_primalidad - 77k –

www.monografias.com/trabajos15/algoritmos/algoritmos .shtml - 50k -

www.psicoactiva.com /tests.htm - 34k

www.primenumbersformula.com/ - 55k –

es.wikipedia.org/wiki/ Criptografía

test de primalidad

Documents