Aritmética Modular Compleja

Aritmética Modular Compleja

Saltar a navegación, búsqueda

La ‘Aritmética Modular Compleja’ (hacia un nuevo test de primalidad)

La ‘Aritmética Modular Compleja’.La ‘semiarcotangente discreta’

La ecuación diofántica $\displaystyle a^2+b^2=1$ no tiene sentido en la aritmética normal, ya que se reduce a las solución trivial que bien a $\displaystyle a=1$ ó $\displaystyle b=1$ pero lo tiene si la llevamos al mundo de la aritmética modular:

$\displaystyle a^2+b^2=1$ (mod M)

Por que podemos encontrar muchas soluciones no triviales que la cumplen. Para ello lo más práctico es usar las relaciones entre la $\displaystyle \tan(x/2)$ y el $\displaystyle \sin(x)$ y el $\displaystyle \cos(x)$ :

$\displaystyle a=\frac{1-t^2}{1+t^2}$

$\displaystyle b=\frac{2\cdot t}{1+t^2}$

Obviamente, una vez visto este paralelismo, esto nos lleva al establecimiento de otro mucho más amplio con la variable compleja, es decir que son factibles las operaciones:

$\displaystyle (x+i\cdot y)=(a+i\cdot b)\cdot(c+i\cdot d)$ (mod M) siendo $\displaystyle i=\sqrt{-1}$

resultado:

$\displaystyle x=a\cdot c-b\cdot d;$ (mod M)

$\displaystyle y=a\cdot d-b\cdot c;$ (mod M)

siendo el caso de $\displaystyle a^2+b^2=1$ (mod M) un subconjunto de otro más general. Esto conviene señalarlo para cuando sea necesario implementar los algoritmos de cálculo, para evitar las operaciones para encontrar el inverso modular (algoritmo extendido de Euclides)de $\displaystyle (1+t^2)$ más veces que las estrictamente necesarias.

O sea que, en el fondo, es lo mismo que las conocidas fórmulas de $\displaystyle \cos(a+b)$ y $\displaystyle \sin(a+b)$ .

Como es natural es posible calcular el $\displaystyle \cos(2\cdot a)$ y el $\displaystyle \sin(2\cdot a)$ y siguiendo un método similar al que se usa para la implementación de la exponencial modular simple (RSA) calcular en tiempo polinomial el equivalente al $\displaystyle \cos(n\cdot a)$ y el $\displaystyle \sin(n\cdot a)$ , lo que en el fondo no deja de ser similar al $\displaystyle e^{i\cdot n\cdot a}$ ,pero usando aritmética modular. La manera más simple es la descomposición del exponente 'n' en la suma de las sucesivas potencias de dos.

Una vez obtenidos el $\displaystyle \cos(n\cdot a)=x$ y el $\displaystyle \sin(n\cdot a)=y$ podemos obtener el valor de $\displaystyle t=\frac{y}{1+x}$ correspondiente, que da origen, salvo singularidades a estos $\displaystyle x$ e $\displaystyle y$, tales que $\displaystyle x^2+y^2=1$(mod M).

A estos valores de $\displaystyle t$ podría llamarse la `semiarcotangente discreta´ por el paralelismo con la ecuación $\displaystyle y=a^x$ (mod M) (exponencial modular simple) donde se le llama `logaritmo discreto´.

El `Indicador imaginario de Euler´: IiE (M)

En el caso de la exponencial modular simple $\displaystyle y=a^x$ (mod M), como ya es conocido existe el `Indicador de Euler´ (IE (M)) (función φ de Euler) que no es otra cosa que un número tal que $\displaystyle a^{IE(M)}=1$ (mod M), para todo $\displaystyle a$. Pues bien, aquí también ocurre lo mismo, es decir que al calcular el $\displaystyle e^{i\cdot n\cdot a}$, existe un valor de $\displaystyle n = IiE(M)$ que nos lleva al $\displaystyle (1+i\cdot0)$, $\displaystyle (t=0)$ el neutro de la variable compleja, y que tiene características similares con el `indicador de Euler´ , pero no iguales.

Vamos por partes, empecemos estudiando el problema para el caso de que $\displaystyle M$ sea un número primo. A excepción del 2 todos los números primos son impares y podemos clasificarlos en dos tipos, unos que son de la forma $\displaystyle (4\cdot n+1)$ y otros que son de la forma $\displaystyle (4\cdot n-1)$. Empíricamente se ha visto que el $\displaystyle IiE(M)$ era en ambos casos $\displaystyle (4\cdot n)$, es decir ,el múltiplo de cuatro más próximo, por exceso o por defecto, a $\displaystyle M$, por ejemplo:

$\displaystyle IiE(13)=12$

$\displaystyle IiE(43)=44$

¿Por qué es esto así?. En el apartado anterior se ha visto que dada una `semiarcotangente discreta´ $\displaystyle (t)$, podemos encontrar un $\displaystyle x$ e $\displaystyle y$ tales que $\displaystyle x^2+y^2=1$ (mod M).

Los valores posibles de $\displaystyle t$, estarán obviamente comprendidos entre el cero y el $\displaystyle M-1$, pero además, salvo excepciones, se agrupan de cuatro en cuatro según que el resultado de $\displaystyle \tan\left(4\cdot\tan^{-1}(t)\right)$ (mod M), sea el mismo valor. Estos valores son:

$\displaystyle t,~\frac{-1}{t},~\frac{t-1}{t+1},~\frac{1+t}{1-t}$

Lo que se deduce fácilmente `sumando´ o `restando´ $\displaystyle \pi/4$ en el paralelismo de las funciones trigonométricas.

Esto es claramente salvo las `excepciones´, que ahí es donde está la clave del asunto: Una `excepción´, que existe siempre, es la que podemos asociar al `neutro´ ya que solo podemos agrupar tres valores:

$\displaystyle t,~\frac{t-1}{t+1},~\frac{1+t}{1-t}$ ya que el otro $\displaystyle\frac{-1}{t}$ no tiene sentido para $\displaystyle t=0$.

La otra `excepción´ solo ocurre para los primos del tipo $\displaystyle (4\cdot n+1)$ en la que existe un grupo de dos soluciones singulares de $\displaystyle t$, tales que $\displaystyle (1+t^2=0)$ (mod M). Esto ya lo sabían Fermat y sus amigos, ya que es consecuencia de que cuando un número primo es de esta forma puede descomponerse en una suma de cuadrados.

Siguiendo con el paralelismo del `indicador de Euler´ en el caso de potencias de un número primo el comportamiento es similar: $\displaystyle IiE(p^n)=p^{n-1}\cdot IiE(p)$.

Pero en el caso del producto de varios primos o de sus potencias, el $\displaystyle IiE(M)$ es el mínimo común múltiplo de los factores (estamos `girando' $\displaystyle e^{i\cdot a}$ ).

El nuevo `test de primalidad´

Parecido al de Euler, mejor dicho de Fermat:

Es condición necesaria, que : $\displaystyle e^{i\cdot n\cdot a}$ (mod M) $\displaystyle =1$ (variable compleja) y para todo $\displaystyle a$ siendo $\displaystyle n$ el múltiplo de cuatro ,más próximo a $\displaystyle M$, para que $\displaystyle M$ sea primo

Los `nuevos números de Carmichael´

En el test de primalidad de Fermat existían los números de Carmichael, que cumplían la condición de primalidad, sin ser primos, como por ejemplo el 561. La propiedad que deben cumplir estos números es que el $\displaystyle IE(M)$ tenga muchos divisores comunes con $\displaystyle M-1$, veamos con el ejemplo:

$\displaystyle 561=3\cdot11\cdot17;$ $\displaystyle IE(561)=2\cdot10\cdot16=320=2\cdot10\cdot8;$ $\displaystyle M-1=560=2\cdot10\cdot7\cdot8;$

En el caso de la aritmética modular compleja, pasa algo parecido, tendremos un `pseudoprimo' cuando el $\displaystyle IiE(M)$ sea divisor de $\displaystyle M\pm1$, por ejemplo:

El $\displaystyle 143$, $\displaystyle M+1=144=12\cdot12;$ El $\displaystyle IiE(143)= IiE(11\cdot13)= 12\cdot12;$

Luego $\displaystyle 143$ será un `pseudoprimo´, Pero ...

La aplicación a la vez de ambos criterios, es una buena forma de eliminar `pseudoprimos´. Lamentablemente no es suficiente ya que existirán números de Carmichael que cumplan ambos criterios, el más pequeño encontrado es el 6601:

En efecto $\displaystyle 6601=7\cdot23\cdot41$, es un número de Carmichael, y su $\displaystyle IiE(6601)$ es $\displaystyle IiE(7\cdot23\cdot41)=IiE(8,24,40)=120;$ 6600 es múltiplo exacto de 120.

`El `nuevo test de Miller-Rabin´

Si podemos encontrar un número $\displaystyle X$ tal que $\displaystyle X^2~(mod~M)=1$, siendo $\displaystyle X$ distinto de $\displaystyle 1$ o de $\displaystyle M-1$, es evidente que $\displaystyle M$ no es un número primo. Esto es precisamente lo que da origen a grandes rasgos al test de primalidad de Miller-Rabin clásico, ya que en un pseudoprimo se cumple la condición: $\displaystyle X^{M-1}(mod~M)=1$

Como $\displaystyle M-1$ es par al ir dividiendo el exponente $\displaystyle (M-1)$ por dos, sucesivamente hasta que quede impar, es posible llegar a conseguir una solución no trivial de un residuo cuadrático igual a la unidad, y deducir que $\displaystyle M$ no es primo.

De similar manera al $\displaystyle IiE(M)$ se le puede ir dividiendo sucesivamente por dos, y llegar a la mismas deducciones. Obviamente este tipo de test son el `talón de Aquiles´ de los números de Carmaichael.

Introducción a las posibles demostraciones asociadas

Sean $\displaystyle a$ y $\displaystyle b$ dos números tales que $\displaystyle a^2+b^2=1~(mod~M)$ podemos decir simbólicamente que:

$\displaystyle a=cos(x);$ $\displaystyle b=sin(x);$

por lo que si desarrollamos por la fórmula del Binomio de Newton:

$\displaystyle \left(cos(x)+i\cdot\sin(x)\right)^{M}=\displaystyle\sum^{k=M}_{k=0}\left( \begin{array}{c} M\\ k \end{array} \right) \cos^{k}(x)\cdot i^{M-k}\cdot \sin^{M-k}(x)$

ahora bien, si $\displaystyle M$ es primo:

$\displaystyle \left( \begin{array}{c} M\\ k \end{array} \right) =0;$ (mod M) para todo $\displaystyle k\neq0$ ó $\displaystyle k\neq M$

entonces:

$\displaystyle \left(cos(x)+i\cdot\sin(x)\right)^{M}=\cos^M(x)+i^M\cdot\sin^M(x)$

pero si $\displaystyle M$ es primo, por el Pequeño teorema de Fermat:

$\displaystyle \cos^M(x)=\cos(x)~(mod~M)$ y $\sin^M(x)=\sin(x)~(mod~M)$ o sea:

$\displaystyle \left(cos(x)+i\cdot\sin(x)\right)^{M}=\cos(x)+i^M\cdot\sin(x)$

entonces como: $\displaystyle i^M$ será igual a $\displaystyle \pm i$ según $\displaystyle M$ (mod 4) sea $\displaystyle \pm 1$, bastará pues con multiplicar por:

$\displaystyle \left(\cos(x)\pm i\cdot \sin(x)\right)$ para obtener el $\displaystyle 1+i\cdot0$

con lo que resumiendo si:

$\displaystyle a^2+b^2=1$ (mod M) siendo $\displaystyle M$ primo se cumplirá que:

$\displaystyle \left(a+i\cdot b\right)^{M\pm1}=(1+i\cdot0)~(mod~M);$ según $\displaystyle M$ (mod 4) sea $\displaystyle \pm1$

Fuentes en lenguaje C

/*****************************************************************
Este programa calcula todos números primos menores a 10000 
sin dar ningun falso primo
por comparación de los resultados de 
(1+a)^n, (1-a)^n ,(1+ia)^n e (1-ia)^n (mod m)
para a=5
aunque descarta antes los multiplos de 5
 
************************************/
#include <stdio.h>
#include <math.h>
 
unsigned long suma_mod(unsigned long x,unsigned long y,unsigned long m){
	unsigned long z;
	__int64 l;
	l=(unsigned long)x;
	l+=y;
	l%=m;	
	z=(unsigned long) l;
return(z);}
 
unsigned long resta_mod(unsigned long x,unsigned long y,unsigned long m){
	unsigned long z;
	__int64 l;
	l=(unsigned long) m;
	l+=x;
	l-=y;
	l%=m;	
	z=(unsigned long) l;
return(z);}
 
unsigned long mult_mod(unsigned long x,unsigned long y,unsigned long m){
	unsigned long z;
	__int64 l;
	l=(unsigned long)x;
	l*=y;
	l%=m;	
	z=(unsigned long) l;
return(z);}
 
 
 
 
unsigned long eleva_mod(unsigned long x,unsigned long e,unsigned long m){
	unsigned long z,ei,p;
	short i;
	ei=e;
	z=1;
	p=x;
	for(i=0;i<32;i++){
		if((ei&0x1l)==1) z=mult_mod(z,p,m);
		p=mult_mod(p,p,m);
		ei>>=1;
		}
return(z);}
 
 
 
char Euclides(unsigned long *y,unsigned long x,unsigned long mod){
	char s=1,ok=0;
	unsigned long n,d,ia,ib,ix,c,r=0;
	if(x!=0){
		ok=1;
		n=mod;
		d=x;
		ia=0;
		ib=1;
		}
	while(ok){
		c=n/d;
		r=n-c*d;
		ix=ib*c+ia;
		if((r==0)||(r==1)) break;
		n=d;
		d=r;
		ia=ib;
		ib=ix;
		s^=0x01;		
		}
	if(r==0){
		ok=0;
		*y=d; 
		}
	if(r==1){
		ok=1;
		if(s) *y=mod-ix;
		else *y=ix;
		}
return(ok);}
 
 
 
 
char x2_y2_1(unsigned long t,unsigned long *c,unsigned long *s,unsigned long mod){
	char ok,okfac;
	unsigned long xx,yy,aa,cc,fac=1,facx1,facx2;
	cc=mult_mod(t,t,mod);
	yy=suma_mod(t,t,mod);
        xx=resta_mod(1,cc,mod);
	cc=suma_mod(1,cc,mod);
	okfac=Euclides(&facx1,xx,cc);
	if(okfac==0) okfac=Euclides(&facx2,yy,cc);
	if(okfac==0) okfac=Euclides(&fac,facx1,facx2);
	if((okfac!=0)||(fac==0)) fac=1;
	xx/=fac;
	yy/=fac;
	cc/=fac;
	if(cc==1){
		ok=1;
		aa=1;
		}
	else	ok=Euclides(&aa,cc,mod);
	if(ok){
		*c=mult_mod(xx,aa,mod);
		*s=mult_mod(yy,aa,mod);
		}
return(ok);}
 
 
 
 
void sc_amasb(unsigned long mod,unsigned long ca,unsigned long sa,
				unsigned long cb,unsigned long sb,
				unsigned long *cx,unsigned long *sx){
	unsigned long x,y;
	x=mult_mod(sa,cb,mod);
	y=mult_mod(sb,ca,mod);
	*sx=suma_mod(x,y,mod);
	x=mult_mod(ca,cb,mod);
	y=mult_mod(sa,sb,mod);
	*cx=resta_mod(x,y,mod);
	}
 
char sc_n_x(unsigned long mod,unsigned long n,unsigned long t,
				unsigned long *cx,unsigned long *sx){
	char ok;
	unsigned long i,c,s,ci,si,c2,s2;
	ok=x2_y2_1(t,&ci,&si,mod);
	c=1;s=0;
	if(ok){
		i=n;
		while(i!=0){
			if((i&1)==1) sc_amasb(mod,c,s,ci,si,&c,&s);
			sc_amasb(mod,ci,si,ci,si,&c2,&s2);
			ci=c2;si=s2;
			i>>=1;
			}
		*cx=c;*sx=s;
		}
	return (ok);}
 
void sc0_n_x(unsigned long mod,unsigned long n,
				unsigned long c0,unsigned long s0,
				unsigned long *cx,unsigned long *sx){
	unsigned long i,c,s,ci,si,c2,s2;
	ci=c0;
	si=s0;
	c=1;
	s=0;
	i=n;
	while(i!=0){
		if((i&1)==1) sc_amasb(mod,c,s,ci,si,&c,&s);
		sc_amasb(mod,ci,si,ci,si,&c2,&s2);
		ci=c2;si=s2;
		i>>=1;
		}
	*cx=c;*sx=s;
	}
 
 
 
char unsigned long t_cs(unsigned long *t,unsigned long c,unsigned long s,unsigned long m){
	unsigned long sf,c1,cf,ic1,f,fac=1;
	char ok,okfac;
	c1=suma_mod(1,c,m);
	okfac=Euclides(&f,s,c1);
	if((okfac==0)&&(f!=0)) fac=f;
	cf=c1/fac;
	sf=s/fac;
	if(cf==1){
		ok=1;
		ic1=1;
		}
	else ok=Euclides(&ic1,cf,m);
	if(ok) *t=mult_mod(sf,ic1,m);
return(ok);}
 
 
 
 
char coef_iie(unsigned long *c1,unsigned long *c2,unsigned long *c3,unsigned long *c4,unsigned long a,unsigned long m){
	unsigned long ia,i2,x1,x2,a1,a2,a3,a4,b1,b2,b3,b4;
	char ok;
	ok=Euclides(&i2,2,m);
	if(ok){
		ok=0;
		if(a>=2) ok=Euclides(&ia,a,m);
		if(a==1) {
			ok=1;
			ia=1;
			}
		}
	if(ok){
		x1=suma_mod(1,a,m); 
		x2=resta_mod(1,a,m);
		x1=eleva_mod(x1,m,m); 
		x2=eleva_mod(x2,m,m);
		a1=suma_mod(x1,x2,m);
		a2=resta_mod(x1,x2,m);
		a1=mult_mod(a1,i2,m);
		a2=mult_mod(a2,i2,m);
		x1=1;
		x2=a;
		sc0_n_x(m,m,x1,x2,&a3,&a4);
		if((m%4)==3) a4=m-a4;
		x1=suma_mod(a1,a3,m); 
		x2=resta_mod(a1,a3,m);
		b1=mult_mod(x1,i2,m);
		b2=mult_mod(x2,i2,m);
		x1=suma_mod(a2,a4,m); 
		x2=resta_mod(a2,a4,m);
		b3=mult_mod(x1,i2,m);
		b4=mult_mod(x2,i2,m);
		*c1=b1;
		*c2=b2;
		b3=mult_mod(b3,ia,m);
		*c3=b3;
		*c4=b4;
		}
return(ok);}
 
char ok_primo(unsigned long m){
	char ok=1;
	unsigned long a,c1,c2,c3,c4;
	a=5;
	if(ok) ok=coef_iie(&c1,&c2,&c3,&c4,a,m);
	if(ok) { if((c1!=1)||(c2!=0)||(c3!=1)||(c4!=0)) ok=0;}
	if(m==2) ok=1;
	if(m==3) ok=1;	
	if(m==5) ok=1;
return(ok);}
 
 
 
main(){
        unsigned long i,n=0,k=10000;
	char ok;
	for(i=2;i<k;i++){
		ok=ok_primo(i);
		if(ok){
			printf("%d,",i);
			n++;
			}
		}
	printf("\nk=%d,n=%d\n",k,n);
return(0);}

Referencia

• ANÁLISIS ALGEBRÁICO POR A.FZ.DE TROCONIZ Y E.BELDA VILLENA. ED. VIZCAINA 1964 (BILBAO) Cap. II y VII

Obtenido de "Aritm%C3%A9tica Modular Compleja"