fork download 
  1. /******************************************************************************
  2.  
  3. Welcome to GDB Online.
  4. GDB online is an online compiler and debugger tool for C/C++.
  5. Code, Compile, Run and Debug online from anywhere in world.
  6.  
  7. *******************************************************************************/
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <math.h>
  11. #include <time.h>
  12.  
  13. long modulo(long a, long b)
  14. {
  15.   return a % b;
  16. }
  17.  
  18. long euclides(long a, long b)
  19. {
  20.     while (b != 0)
  21.     {
  22.         long aux = b;
  23.         b = a % b;
  24.         a = aux;
  25.     }
  26.     return a;
  27. }
  28.  
  29. void eratostenes(long p)
  30. {
  31.     int *numeros = (int*) malloc(p * sizeof(int));
  32.     if (numeros == NULL) {
  33.         printf("Error en la asignación de memoria.\n");
  34.         exit(1);
  35.     }
  36.     for (int i = 2; i < p; i++)
  37.     {
  38.         numeros[i] = 1;
  39.     }
  40.  
  41.     for (int i = 2; i * i < p; i++)
  42.     {
  43.         if (numeros[i] == 1)
  44.         {
  45.             for (int j = i * i; j < p; j += i)
  46.             {
  47.                 numeros[j] = 0;
  48.             }
  49.         }
  50.     }
  51.  
  52.     for (int i = 2; i < p; i++)
  53.     {
  54.         if (numeros[i] == 1)
  55.         {
  56.             printf("%d ", i);
  57.         }
  58.     }
  59. 	free(numeros);
  60. }
  61.  
  62. void factorizacion(long p)
  63. {
  64.     printf("Factores primos de %ld: ", p);
  65.     for (long i = 2; i <= sqrt(p); i++)
  66.     {
  67.         while (p % i == 0)
  68.         {
  69.             printf("%ld ", i);
  70.             p /= i;
  71.         }
  72.     }
  73. 	if (p > 1)
  74.     {
  75.         printf("%ld", p);
  76.     }
  77.     printf("\n");
  78. }
  79.  
  80. long entero_menor(long p)
  81. {
  82.     return rand() % p;
  83. }
  84.  
  85. int es_primo(long n)
  86. {
  87.     if (n < 2) return 0;
  88.     for (long i = 2; i <= sqrt(n); i++)
  89.     {
  90.         if (n % i == 0) return 0;
  91.     }
  92.     return 1;
  93. }
  94.  
  95. long primo_menor(long p)
  96. {
  97. 	if (p <= 1)
  98. 	{
  99. 		printf("El número debe ser mayor que 1.\n");
  100. 		exit(1);
  101. 	}
  102.     long n;
  103.     do
  104.     {
  105.         n = entero_menor(p);
  106.     } while (!es_primo(n));
  107.  
  108.     return n;
  109. }
  110.  
  111. void inversa(long a, long b)
  112. {
  113. 	long r0 = b, r1 = a, x0 = 1;
  114. 	long q1 = r0 / r1;
  115. 	long r2 = modulo(r0,r1);
  116. 	long x1 = -q1;
  117. 	long x2;
  118. 	while (r2!=0)
  119. 	{
  120. 		r0 = r1;
  121. 		r1 = r2;
  122. 		q1 = r0 / r1;
  123. 		r2 = modulo(r0,r1);
  124. 		x2 = x0 - (q1*x1);
  125. 		x0 = x1;
  126. 		x1 = x2;
  127. 	}
  128. 	if (r1!=1)
  129. 	{
  130. 		printf("No existe la inversa.\n");
  131. 		exit(0);
  132. 	}
  133. 	if (x0>0)
  134. 	{
  135. 		printf("La inversa es %ld.\n", x0);
  136.  
  137. 	}
  138. 	else
  139. 	{
  140. 		printf("La inversa es %ld.\n", x0 + b);
  141. 	}
  142. }
  143.  
  144. long exponenciacion(long a, long x, long n)
  145. {
  146. 	long y = 1;
  147. 	long u = a % n;
  148. 	while(x!=0)
  149. 	{
  150. 		if((x%2)==1) y = (y*u) % n;
  151. 		x = x/2;
  152. 		u = (u*u) % n;
  153. 	}
  154. 	return y;
  155. }
  156.  
  157. long es_generador(long g, long p)
  158. {
  159.     long p1 = p - 1;
  160.     for (long q = 2; q * q <= p1; q++)
  161.     {
  162.         if (p1 % q == 0)
  163.         {
  164.             // Si g^((p-1)/q) ≡ 1 mod p → no es generador
  165.             if (exponenciacion(g, p1 / q, p) == 1)
  166.                 return 0;
  167.  
  168.             // Eliminar potencias de q para evitar redundancia
  169.             while (p1 % q == 0)
  170.                 p1 /= q;
  171.         }
  172.     }
  173.  
  174.     // Verificar el último factor si quedó uno mayor que sqrt(p1)
  175.     if (p1 > 1)
  176.     {
  177.         if (exponenciacion(g, (p - 1) / p1, p) == 1)
  178.             return 0;
  179.     }
  180.  
  181.     return 1;
  182. }
  183.  
  184. void generadores(long p)
  185. {
  186.     if (!es_primo(p))
  187.     {
  188.         printf("El número %ld no es primo.\n", p);
  189.         return;
  190.     }
  191.  
  192.     for (long g = 2; g < p; g++)
  193.     {
  194.         if (es_generador(g, p))
  195.         {
  196.             printf("%ld es un generador de Z%ld\n", g, p);
  197.         }
  198.     }
  199. }
  200.  
  201. void legendre(long a, long p)
  202. {
  203.     if (euclides(a, p) != 1)
  204. 	{
  205.         printf("El símbolo de Legendre no está definido para estos valores.\n");
  206.         return;
  207.     }
  208.     long resultado = exponenciacion(a, (p - 1) / 2, p);
  209.     if (resultado == p - 1)
  210. 	{
  211.         printf("El símbolo de Legendre (%ld/%ld) es -1.\n", a, p);
  212.     }
  213. 	else
  214. 	{
  215.         printf("El símbolo de Legendre (%ld/%ld) es 1.\n", a, p);
  216.     }
  217. }
  218.  
  219. int jacobi(long a, long n)
  220. {
  221.     if (n <= 1 || n % 2 == 0)
  222. 	{
  223.         printf("El valor de n debe ser un número impar mayor que 1.\n");
  224.         return 0;
  225.     }
  226.  
  227.     int j = 1;
  228.     while (a != 0)
  229. 	{
  230.         while (a % 2 == 0)
  231. 		{
  232.             a /= 2;
  233.             if (n % 8 == 3 || n % 8 == 5)
  234. 			{
  235.                 j = -j;
  236.             }
  237.         }
  238.         long temp = a;
  239.         a = n % a;
  240.         n = temp;
  241.         if (a % 4 == 3 && n % 4 == 3)
  242. 		{
  243.             j = -j;
  244.         }
  245.     }
  246.     if (n == 1)
  247. 	{
  248.         return j;
  249.     }
  250.     return 0;
  251. }
  252.  
  253. int main()
  254. {
  255. 	srand(time(NULL));
  256. 	char letra;
  257. 	long resultado, a, b, c;
  258. 	printf("Pulse una letra:\n");
  259. 	printf("	a) a mod b\n");
  260. 	printf("	b) MCD de a y b usando el algoritmo de Euclides\n");
  261. 	printf("	c) Criba de Eratóstenes dado un número máximo p\n");
  262. 	printf("	d) Factorización de un número p por fuerza bruta\n");
  263. 	printf("	e) Generar un número entero aleatorio x menor que p\n");
  264. 	printf("	f) Generar, por fuerza bruta, un número primo x menor que p\n");
  265. 	printf("	g) Calcular, si existe, la inversa x = a-1 mod b\n");
  266. 	printf("	h) Calcular la exponenciación Y = a^x mod n\n");
  267. 	printf("	i) Calcular por fuerza bruta todos los generadores del grupo Zp con p primo\n");
  268. 	printf("	j) Verificar analiticamente si un número x es generador del grupo Zp\n");
  269. 	printf("	k) Calcular el símbolo de Legendre(a/p)\n");
  270. 	printf("	l) Calcular el símbolo de Jacobi(a/n)\n");
  271. 	printf("	z) Salir\n");
  272. 	scanf("%c",&letra);
  273. 	switch (letra)
  274. 	{
  275. 		case 'a':
  276. 			printf("Introduce el primer número:\n");
  277. 			scanf("%ld",&a);
  278. 			printf("Introduce el segundo número:\n");
  279. 			scanf("%ld",&b);
  280. 			resultado = modulo(a, b);
  281. 			printf("%ld\n", resultado);
  282. 			break;
  283.  
  284. 		case 'b':
  285. 			printf("Introduce el primer número:\n");
  286. 			scanf("%ld",&a);
  287. 			printf("Introduce el segundo número:\n");
  288. 			scanf("%ld",&b);
  289. 			resultado = euclides(a, b);
  290. 			printf("%ld\n", resultado);
  291. 			break;
  292.  
  293. 		case 'c':
  294. 			printf("Introduce un número:\n");
  295. 			scanf("%ld",&a);
  296. 			eratostenes(a);
  297. 			break;
  298.  
  299. 		case 'd':
  300. 			printf("Introduce un número:\n");
  301. 			scanf("%ld",&a);
  302. 			factorizacion(a);
  303. 			break;
  304.  
  305. 		case 'e':
  306. 			printf("Introduce un número:\n");
  307. 			scanf("%ld",&a);
  308. 			resultado = entero_menor(a);
  309. 			printf("%ld\n", resultado);
  310. 			break;
  311.  
  312. 		case 'f':
  313. 			printf("Introduce un número:\n");
  314. 			scanf("%ld",&a);
  315. 			resultado = primo_menor(a);
  316. 			printf("%ld\n", resultado);
  317. 			break;
  318.  
  319. 		case 'g':
  320. 			printf("Introduce el primer número:\n");
  321. 			scanf("%ld",&a);
  322. 			printf("Introduce el segundo número:\n");
  323. 			scanf("%ld",&b);
  324. 			inversa(a, b);
  325. 			break;
  326.  
  327. 		case 'h':
  328. 			printf("Introduce el número a:\n");
  329. 			scanf("%ld",&a);
  330. 			printf("Introduce el número x:\n");
  331. 			scanf("%ld",&b);
  332. 			printf("Introduce el número n:\n");
  333. 			scanf("%ld",&c);
  334. 			resultado = exponenciacion(a,b,c);
  335. 			printf("%ld\n", resultado);
  336. 			break;
  337.  
  338. 		case 'i':
  339. 			printf("Introduce un número:\n");
  340. 			scanf("%ld",&a);
  341. 			generadores(a);
  342. 			break;
  343.  
  344. 		case 'j':
  345. 			printf("Introduce un número x:\n");
  346. 			scanf("%ld",&a);
  347. 			printf("Introduce un número p:\n");
  348. 			scanf("%ld",&b);
  349. 			if(es_generador(a,b))
  350. 			{
  351. 				printf("%ld es un generador de Z%ld\n", a, b);
  352. 			}
  353. 			else
  354. 			{
  355. 				printf("%ld no es un generador de Z%ld\n", a, b);
  356. 			}
  357. 			break;
  358.  
  359. 		case 'k':
  360. 			printf("Introduce el primer número:\n");
  361. 			scanf("%ld",&a);
  362. 			printf("Introduce el segundo número:\n");
  363. 			scanf("%ld",&b);
  364. 			legendre(a, b);
  365. 			break;
  366.  
  367. 		case 'l':
  368. 			printf("Introduce el primer número:\n");
  369. 			scanf("%ld",&a);
  370. 			printf("Introduce el segundo número:\n");
  371. 			scanf("%ld",&b);
  372. 			resultado = jacobi(a, b);
  373. 			if (resultado != 0)
  374. 	        {
  375.                 printf("El símbolo de Jacobi (%ld/%ld) es %ld.\n", a, b, resultado);
  376.             }
  377. 	        else
  378. 	        {
  379.                 printf("Error en el cálculo del símbolo de Jacobi.\n");
  380.             }
  381. 			break;
  382.  
  383. 		case 'z':
  384. 			return 0;
  385.  
  386. 		default:
  387. 			printf("Opción no válida.\n");
  388.             break;
  389. 	}
  390. 	return 0;
  391. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
45
stdout 
Pulse una letra:
	a) a mod b
	b) MCD de a y b usando el algoritmo de Euclides
	c) Criba de Eratóstenes dado un número máximo p
	d) Factorización de un número p por fuerza bruta
	e) Generar un número entero aleatorio x menor que p
	f) Generar, por fuerza bruta, un número primo x menor que p
	g) Calcular, si existe, la inversa x = a-1 mod b
	h) Calcular la exponenciación Y = a^x mod n
	i) Calcular por fuerza bruta todos los generadores del grupo Zp con p primo
	j) Verificar analiticamente si un número x es generador del grupo Zp
	k) Calcular el símbolo de Legendre(a/p)
	l) Calcular el símbolo de Jacobi(a/n)
	z) Salir
Opción no válida.
https://ideone.com/TMWCds
language:
C (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!