LIP Algunos de los programas utilizan el paquete LIP (Large Integer Package) de Arjen K. Lenstra para operar con enteros de tamaño arbitrario. Es el más fácil de usar que conozco, funciona a la primera y tiene una buena documentación, incluyendo como compilar los programas aquí incluídos. Esta es la versión que uso: LIP v1.1 (200 K)

GMP Otros de los programas más recientes usan GMP la librería aritmética multiprecisión de GNU. http://www.gnu.org

    En todo caso tenemos una página que explica cómo compilar los programas.

Números enteros
Máximo común divisor y factores primos
Congruencias
Aplicaciones de las congruencias
Algunas congruencias especiales
Funciones multiplicativas
Sin clasificar

  Números enteros

ulam.c cálculo de los n primeros números de Ulam

1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26 ...

LIP factrial.c factorial de un entero de tamaño arbitrario. Por ejemplo:

150!=
571338395644585459047893286526105400318955357
860112641825483758331798291248453983931265744
886753111453771078787468542041626662501986845
044663559491959220665749425920957357789293253
572904449624724054167907221184454371222696755
20000000000000000000000000000000000000

Cuando comprobaba este programa utilizé una vez más el libro de Spiegel (en la Serie Schaum de McGraw Hill) "Manual de fórmulas y tablas matemáticas" que incluye los factoriales hasta 30! con todas sus cifras. Los factoriales desde 22! hasta 30! son incorrectos :-o

sergeom.c suma de una serie geométrica.

LIP fibnacci.c escribe los n primeros términos de la sucesión de Fibonacci. Por ejemplo:

F300 =
3595793252065835609617656651721
89099052367214309267232255589801

LIP combin.c calcula números combinatorios realmente grandes, como:

100 sobre 50 = 100891344545564193334812497256

LIP binomio.c desarrollo de (x+y)ⁿ mediante el binomio de Newton. Ejemplo:

(x+y)²⁰ = x²⁰ + 20x¹⁹.y¹ + 190x¹⁸.y² + 1140x¹⁷.y³ + 4845x¹⁶.y⁴ + 15504x¹⁵.y⁵ + 38760x¹⁴.y⁶ + 77520x¹³.y⁷ + 125970x¹².y⁸ + 167960x¹¹.y⁹ + 184756x¹⁰.y¹⁰ + 167960x⁹.y¹¹ + 125970x⁸.y¹² + 77520x⁷.y¹³ + 38760x⁶.y¹⁴ + 15504x⁵.y¹⁵ + 4845x⁴.y¹⁶ + 1140x³.y¹⁷ + 190x².y¹⁸ + 20x¹.y¹⁹ + y²⁰

collatz.c comprueba la conjetura de Collatz. Por ejemplo:

79, 119, 179, 269, 404, 202, 101, 152, 76, 38, 19, 29, 44, 22, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1

Número de iteraciones: 24

goldbach.c comprueba para los números del 1 al 10000 la conjetura de Goldbach. ...

340 = 3 + 337 342 = 5 + 337 344 = 7 + 337 346 = 29 + 317 348 = 11 + 337 350 = 3 + 347 352 = 3 + 349 ...

LIP gemelos.c calcula el primer par de números gemelos a partir de uno dado. Por ejemplo en mi sistema (PII 400Mhz bajo Linux) descubre en menos de un segundo que:

100000000000000000391 y 100000000000000000393 son primos gemelos.

  Máximo comun divisor y factores primos

euclides.c usa el algoritmo de Euclides para calcular el m.c.d. de dos enteros.

mcd.c calcula el m.c.d de dos enteros sin divisiones.

bezout.c aplicación del teorema de Bezout al cálculo del inverso de un entero módulo un segundo entero. También expresa el mcd de dos enteros como combinación lineal de ellos.

mcd(100,37)= 1 = 100*10 + 37*(-27)
El inverso de 100 modulo 37 es 10

bezgen.c calcula de forma iterativa el mcd de n enteros y lo expresa como combinación lineal de ellos. Por ejemplo:

(195,330,540,420) = 15 = +1*195 -6*330 -90*540 +120*420

LIP fcfermat.c factoriza un entero por el método de Fermat, útil para enteros producto de dos primos de tamaño similar. Calculado en dos minutos en mi sistema:

369203783376518439036223 = 610347000407 . 604908000089

LIP nfermat.c calcula el n-simo número de Fermat y busca posibles factores. (¡Ojo! estos números crecen muy deprisa, ver mi página (números primos)

F6 = 18446744073709551617
Un factor es 274177

diofant.c encuentra las soluciones de una ecuación diofántica en dos variables, señalando la menor positiva cuando exista.

Las soluciones de 8x+11y=54 son:

x= -216 + 11 .n
y= 162 + -8 .n

donde n es cualquier número entero.
Mínima solución positiva: x=4 y=2 (para n=20)

diofgen.c una generalización del programa anterior para encontrar las soluciones de una ecuación diofántica con n variables. Por ejemplo resolvamos 15x+35y+77z=3

Soluciones de la forma:
x0 = 3 + 2695.n
x1 = 12 + 1155.n
x3 = -6 + -1050.n donde n es cualquier entero.

  Congruencias

congline.c permite resolver congruencias lineales con una incógnita. Por ejemplo al resolver 3x = 6 (mod 18) obtenemos:

Hay 3 soluciones no congruentes entre sí:
x=2 x=8 x=14

conglin2.c otro método de resolver congruencias lineales con una incognita, ax=b (mod m) en el caso mcd(a,m)=1.

congxy.c resuelve ecuaciones diofánticas del tipo ax+by=c (mod m). La solución de 12x+35y = 3 (mod 16) es: x= 9 y= -3

cong2x2.c resuelve sistemas de congruencias lineales de dos ecuaciones con dos incógnitas. Por ejemplo el sistema formado por:

x + 2y = 3 (mod 7)
4x + 5y = 6 (mod 7)
tiene como solución: x=6 y=2

invmatmd.c inverso de una matriz 2x2 módulo un número. Por ejemplo la matriz formada por los números del 1 al 4 tiene un inverso módulo 7 que es:

| 5 -6 |
| -2 3 |

  Aplicaciones de las congruencias

max2y5.c calcula la máxima potencia de 2 y de 5 que divide a un entero dado.

calgreg.c día de la semana de la fecha que se desee según el calendario gregoriano.

calen.c escribe un calendario del mes y año que se desee.

Febrero 2000 L M M J V S D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

tchino.c aplica el teorema chino del resto para resolver un sistema de ecuaciones modulares. Por ejemplo ¿cual es el menor número que divido por 2 da resto 1, por 3 da resto 2 y por 5 resto 4?

Este programa resuelve sistemas de congruencias.
del tipo x=a1 mod m1;... x=an mod mn.

Número de ecuaciones n= 3

a1=1
m1=2

a2=2
m2=3

a3=4
m3=5

La solución es 29

rndrobin.c aplicación de las congruencias al cálculo de los emparejamientos en un torneo round-robin (n equipos todos contra todos en n ó n-1 rondas). Por ejemplo para n=11 el resultado es:

 Equipo --   1   2   3   4   5   6   7   8   9  10  11
 Ronda  1:  11  10   9   8   7   -   5   4   3   2   1
 Ronda  2:   -  11  10   9   8   7   6   5   4   3   2
 Ronda  3:   2   1  11  10   9   8   -   6   5   4   3
 Ronda  4:   3   -   1  11  10   9   8   7   6   5   4
 Ronda  5:   4   3   2   1  11  10   9   -   7   6   5
 Ronda  6:   5   4   -   2   1  11  10   9   8   7   6
 Ronda  7:   6   5   4   3   2   1  11  10   -   8   7
 Ronda  8:   7   6   5   -   3   2   1  11  10   9   8
 Ronda  9:   8   7   6   5   4   3   2   1  11   -   9
 Ronda 10:   9   8   7   6   -   4   3   2   1  11  10
 Ronda 11:  10   9   8   7   6   5   4   3   2   1   -

  Algunas congruencias especiales

LIP wilsprm.c busca primos de Wilson (p-1)! = -1 (mod p^2) de tamaño arbitrario.

cngfermt.c resuelve congruencias lineales utilizando el pequeño teorema de Fermat.

Este programa resuelve congruencias del tipo
ax = b a,b enteros positivos, p primo y p no divide a 'a'.
a= 35
b= 17
p= 97

35x = 17 mod 97; x= 67

  Funciones multiplicativas

fieuler.c calculo de la función fi de Euler, cantidad de números menores que un entero y primos con él.

fieuler 10 20 23
fi(10)= 4
fi(20)= 8
fi(23)= 22

divisor.c calcula las funciones sigma (suma de los divisores) y tau (número de divisores) de un entero dado.

divisor 10 28 30
10 tiene 4 divisores que suman 18.
28 tiene 6 divisores que suman 56.
30 tiene 8 divisores que suman 72.

depeab.c clasifica los enteros en deficientes, perfectos y abundantes.

depeab 10 28 30
10 es deficiente
28 es perfecto
30 es abundante

cngeuler.c resuelve congruencias lineales utilizando el teorema de Euler.

Este programa resuelve congruencias del tipo
ax = b (mod m) siendo a y m primos entre si.

a=15
b=7
m=13

15x = 7 mod 13 ; x= 10 (mod 13)

scngeulr.c resuelve sistemas de congruencias con ayuda del teorema de Euler. Por ejemplo ¿qué multiplos de 4 dan resto 2 al dividirse entre 3 y entre 5?

Este programa resuelve sistemas de congruencias.
del tipo x=a1 mod m1;... x=an mod mn.
siendo los mi primos entre si dos a dos.

Número de ecuaciones
n=3
a1=2
m1=3
a2=2
m2=5
a3=0
m3=4

La solución es x= 32 (mod 60)

GMP mersdiv.c busca posibles divisores de un número de Mersenne Mp=2^p-1 siendo p un primo impar. Por ejemplo:

mersdiv 53
M53 = 9007199254740991 es divisible por 6361

O también

mersdiv 61
M61 = 2305843009213693951 es primo.

GMP lucasleh.c implementación del test de Lucas-Lehmer para estudiar la primalidad de un número de Mersenne.

lucasleh 4253
M4253 es primo.

(Este es el 19º primo de Mersenne descubierto en 1961 y tiene más de 1200 dígitos, en mi sistema el programa contesta que es primo en 5 segundos.)

  Raíces primitivas

ordenmod.c orden de un entero módulo un segundo entero.

raizprim.c raíces primitivas de un entero.

./raizprim 193

Raices primitivas de 193 { 5 10 15 17 19 22 26 30 34 37 38 40 41 44 45 47 51 52 53 57 58 61 66 70 73 77 78 79 80 82 90 91 102 103 111 113 114 115 116 120 123 127 132 135 136 140 141 142 146 148 149 152 153 155 156 159 163 167 171 174 176 178 183 188 }

  Aún sin clasificar

GMP bbs.c generación de números pseudoaleatorios con el algoritmo de Blum-Blum-Shub.

Aviso: la secuencia generada no cumple los tests de aleatoriedad FIPS p.ej. aún estoy revisando si tiene algún error. Ejemplo de ejecución:

bbs 200 unacadenacualquiera

d2 30 5c 82 74 b0 0e 42 10 02 f8 1e b2 ce c4 b4 24 2c 5e 60 c2 6c 04 16 28 f8 8c 40 9c 74 66 68 94 dc 78 d6 46 f4 6c 74 de 8e f6 b0 da 30 76 da be 26 e8 8c c4 9e 62 e6 dc e4 2c d0 08 00 be 2c 54 8c b0 42 9a 00 c8 12 40 7c d0 b6 7c da a0 d0 18 84 40 5e 38 d8 4c ec 16 5a ee ba 26 0a ce 38 9a f4 c0 e6 a6 88 08 4a 8c 82 2e 98 2c 70 08 08 62 18 48 34 36 ce d0 10 92 8a fc 2a a6 0c 80 ee a6 da 94 cc f8 f6 22 9a 70 10 ac 1e ca c8 ac c4 ec fe 40 c8 98 02 28 70 34 48 10 44 aa 74 16 ec 78 88 72 98 9e d4 8e 52 68 d8 80 54 88 26 7a 0a d8 f4 a2 ea c6 b8 80 14 2e d6 ba c2 34 f2 e8 ba 2e ee b2 68 70 82 a6 b2

lispri.c permite calcular la lista de primos comprendidos entre dos enteros.

exp_mod.c calculo de potencias módulo un entero.

Volver a la sección Criptotaller