/*
	Symbole de Jacobi

//// Cours de cryptographie      Gilles Zémor
///////////////////////////////////////////////

	Symbole de Legendre
					p premier et n premier avec p      ( ~ dans Zp*)
					 x    {  1  si x est résidu quadratique modulo p
					(-) = {
					 p    { -1  si x n'est pas résidu quadratique modulo p
	Théorème Euler
					 (p-1)/2     x
					x	  = (-)  mod p
						     p	 

					(x |-> (x/p) morphisme du groupe Xp* sur {1, -1) 

	Symbole de Jacobi  ou Symbole de Legendre étendu
					                                       a1    a2   a3       ak
					n >=2 quelconque,  x \in Zn*  et n = p1    p2   p3   ... pk

					              a1       a2           ak
					(x/n) = (x/p1)   (x/p2)	  ... (x/pk)

	lemmes
					             (n-1)/2
					(-1/n) = (-1)

					             (n^2-1)/8
					(2/n) =  (-1)


					pour s et t impairs
					(s-1)/2 + (t-1)/2 = (st-1)/2 mod2      (s^2-1)/8 + (t^2-1)/8 = (s^2t^2-1)/8  mod 2


					(2/p)(p-1/2)!  =  2^((p-1)/2)  (p-1/2)!  mod p

							= 2 . 4 . 6 ... (p-1) mod p

	loi de réciprocité quadratique (GAUSS)

					                 (n-1)(m-1)/4
					(m/n)(n/m) = (-1)

	lemme (GAUSS)


					(p/q) = Prod_a\in K  eps(a)

////////////////////////////////////
////   Arithmétique     Marc Hindry
////////////////////////////////////

	symbole de Legendre
	--------------------

	a, p \in Z    p != 2  p premier

			 a       {  0   si a = 0 mod p 
			(-)      { +1   si a est un carré non nul   mod p         on dit que a est un résidu quadratique
			 p       { -1   si a n'est pas un carré   mod p                      a n'st pas un résidu quadratique

	Théorème
	i) Pour tout a, b  \in Z

					(ab /p) = (a/p)(b/p)

	ii)Pour tout a \in Z
					 (p-1)/2
					a          = (a/p) mod p

	iii) Pour tout p !=2
					             (p-1)/2                         (p^2 -1)/8
					(-1/p) = (-1)                    (2/p) = (-1)

					+---------+----------------------------------+---------------------------------------+
					|         |   est un  carré modulo p         |    n'est pas un carré modulo p        |
					+---------+----------------------------------+---------------------------------------+
					|   -1    |  p = 1 mod 4                     |    p = 3 mod 4                        |
					+---------+----------------------------------+---------------------------------------+
					|    2    |  p = +/- 1 mod 8                 |    p = +/- 3 mod 8                    |
					+---------+----------------------------------+---------------------------------------+


	iv) (Loi de réciprocité quadratique)
		p, q premiers impairs distincts
					                  (p-1)(q-1)/4
					(p/q) (q/p) = (-1)
						
	symbole de Jacobi   (Généralisation)
	------------------
			N = p1 p2 ... pr  impair
			              a1                ar
			(a/N)  = (a/p1)     ...   (a/pr)


	lemme 
			N, M impairs

			i)	(ab/N) = (a/N)(b/N) et (a/N)=0 ssi (a, N) >1
		
				             (N-1)/2                       ((N^2-1)/8)
			ii)	(-1/N) = (-1)             et   (2/N) = (-1)

				            (N-1)(M-1)/4
			iii)	(M/N) = (-1)               (N/N)

*/

function mod(a, b) {
	var c = a%b;
	return (c<0) ? (a+c) : c;
}


/*
	boucle pour b > 0
*/
function modpower(a, b, c) {
	var x=mod(a,c), y = b, z=1;
	while(y>0) {
		// tant que y est pair
		while(y%2==0) {
			y = y/2;
			x = (xùx)%c;
		}
		// maintenant y est impair
		y = y-1
		z = (z*x)%c
		// y est de nouveau pair, on boucle
	}
	return z;
}

function sgn(u) {
	return (u==1)?"":"-"
}
// sgn(s)

function nettoie(s1) {
	var s=s1, u;
	//do {
		u = s;
		s = s.replace(/[\/\|\\\,\;\:]+/g," ")
		s = s.replace(/^\s*jacobi/gi,"")
		s = s.replace(/^\s*legendre/gi,"")
		s = s.replace(/^\s*kronecker/gi,"")
		s = s.replace(/\s+/g," ");
		s = s.replace(/^[\s\(\[]+/,"");
		s = s.replace(/[\s\)\]]+$/,"");
	//} while(u!=s);
	//alert(s)
	return s;

}

function gcd(a, b) {
	var x = Math.abs(a), y=Math.abs(b);
	while(y != 0) {
		var w= x%y
		x = y
		y = w
	}
	return x
}

function affiche(s) {
	document.getElementById("result").innerHTML = "<pre>"+s+"</pre>"
}

function cherche() {
	com()
	s= nettoie(document.frm.t.value);
	var t=s.split(/\s+/g);
	if(t.length<2 ) {
		affiche(" Erreur d'écriture : "+f.value)
		return
	}
	//alert(t)
	var a=parseInt(t[0]), b=parseInt(t[1]);
	if(a==0 && b==0) {
		affiche(" Erreur : ( "+a+" / "+b+" )");
	}
	document.frm.t.value = "( "+a+" / "+b+" )"
	//alert("("+a+"/"+b+")")
//return
	var obj= jacobi(a, b);
	document.getElementById("result").innerHTML = "<pre>"+obj.expl+"\nResultat : "+obj.v+"\n\n"+obj.ligne+"</pre>"
}

function efface() {
	document.frm.t.value="";
	document.getElementById("result").innerHTML = ""
}

function hasard() {
	var MAXI=5000;
	var a = 1+Math.floor(2*MAXI*Math.random()),
	b = 3+2*Math.floor(MAXI*Math.random());
	efface()
	document.frm.t.value="( "+a+" / "+b+" )"
	cherche();
}

function exple(s) {
	document.frm.t.value = s
	cherche()
}

function pr(s, n, m) {
	return " = "+sgn(s)+ "("+n+"/"+m+")"
}

function is_prime(n) {
	if(n==1) return false
	if(n ==2 || n == 3) return true
	if(n%2==0 || n%3==0) return false
	var u=Math.sqrt(n)+1;
	for(var x=5; x<=u; x+=2)
		if(n%x==0) return false
	return true
}

function jacobi(n,m){
	this.lgl=73;
	this.s = 1
	this.v=1
	this.n=n;
	this.m=m
	this.x=n
	this.y=m

	this.st="( " + this.x+" / "+this.y+" ) = \n";
	this.su="Résumé : (" + this.x+"/"+this.y+")" ;
	this.su0=""
	this.test=true
	this.ok = true;

	this.isresidu = function() {
		// (a+1)^2 = a^2+2*a+1
		
		var  a=1, n = mod(this.n, this.m);
		for(var i=1, a=1; i<this.m ; a = mod((a + 2*i +1 ), this.m), i++)  {
			if(a == n) {
				this.sq = i;
				return true;
			}
		}
		return false
	}
		
	this.aff = function(s) {	
		document.getElementById("result").innerHTML = "<pre>"+s+"</pre>"
	}
	
	this.add = function() {
		//this.comment("--- add ---")
		//this.comment(" "+this.s+" "+this.x+" "+this.y)
		
		this.st +="\t = "+sgn(this.s)+ " ( "+this.x+" / "+this.y+" )\n"
		this.su +=" = "+sgn(this.s)+"("+this.x+"/"+this.y+")"
		if(this.su.length>this.lgl) {
			this.su0 +="\n"+this.su
			this.su=""
		}
	}
	this.prod = function(k) {
		var p;
		for(var i=0, p=1; i<k; p*=2, i++) ;
		this.st +="\t = "+sgn(this.s)+ " ( "+p+" / "+this.y+" ) ( "+(this.x/p)+" / "+this.y+" )\n"
		this.su +=" = "+sgn(this.s)+"("+p+"/"+this.y+")("+(this.x/p)+"/"+this.y+")"
                if(this.su.length>this.lgl) {
                        this.su0 +="\n"+this.su
                        this.su=""
                }
        }

	this.end = function() {
		this.comment("=== fin ===")
		this.v=this.s
		this.st +="\t = "+this.v+"\n"
		this.su +=" = "+this.v
		this.su0 += "\n"+this.su
		this.test=false
	}

	this.comment = function(s) {
		this.st += "\t "+CM+" "+s+"\n"
/*
		if(arguments[1]) {
			//this.st = '<span class="'+arguments[1]+'">'+this.st+'</span>'
		}
*/
	//	this.aff(this.st)
	}
	this.modulo = function() { 
		if( this.test == false) 
			return;
		var v, u = this.x % this.y
		while (u<0 && this.y>0) {
			u += this.y
			this.ok=true
		}
		if(u != this.x) {
			this.comment("=== n   mod m ===")
			this.ok=true
			v = this.x
			this.x = u
			this.comment(v +" = "+u+"  mod "+this.y)
			this.add()
		}
	}
/*
	 / 2 \
	 |---|    = (-1)^((m^2-1)/8)
	 \ m /

         /-1 \
         |---|    = (-1)^((m-1)/2)
         \ m /

         / 1 \
         |---|    = 1
         \ m /

*/
	this.un = function() {
	
		if(this.test && this.x==1) {
			this.comment("=== n = 1 ===", "or")
			this.comment("( 1 / "+this.y+" ) = 1 ")
			this.end();
		}
	}
        this.deux = function() {
                //this.comment("--- deux ---")
                if(this.test && this.x==2) {
			this.comment("=== n = 2  mod m ===", "or")
			var e = ((this.y*this.y -1)/8)%2
			e = 1-2*e
                        this.comment("( 2 / "+this.y+" ) = "+e)
			this.s *= e
			this.x=1
			//this.add()
                        this.end();
                }
        }


	this.moinsun = function() {
		//this.comment("=== n = -1  mod m ===", "or")
        	if(this.test && this.x==(this.y-1)) {
			this.comment("=== n = -1  mod m ===", "or")
			var e = ((this.y-1)/2)%2
			e= 1 -2*e
	                this.comment("( -1 / "+this.y+" ) = (-1)^(("+this.y+"-1)/2) = "+e)
			this.s *= e
                	this.end();
	        }
	}
	this.nul= function() {
		//this.comment("=== n = 0 ===", "or")
		if(this.test && this.x==0) {
			this.comment("=== n nul ===", "or")
			this.ok=false
                	this.comment("( 0 / "+this.y+" ) = 0 ")
			this.s = 0
        	        this.end();
	        }
	}	

	this.pair = function() {
		//this.comment("=== n multiple de 2 ===", "or")
		// assume m impair
		//teste n pair
		var u = this.x % 2
		//this.comment(this.x +" % 2 = "+u)
		if(this.test && (u == 0) ) {
			this.ok=true
			this.comment("=== n est pair ===", "or")
			
			var k, u;
			for(k=0, u=this.x; u%2==0; u/=2, k++);
			var h = ((this.y*this.y-1)/8)%2
			//this.comment("("+this.y+"-1)/2 = "+((this.y-1)/2))
			//this.comment(" k = "+k)
			if(k==1) {
				this.comment("une division par 2 ")
			} else if (k<11) {
				this.comment(nbresf[k]+" divisions successives par 2")
			} else {
				this.comment( k+" divisions successives par 2")
			}
			this.prod(k)

			this.comment("("+this.y+"-1)/2 = "+((this.y-1)/2))
			if(k%2==0 || h==0) {
			} else {
				//this.comment( " * -1")
				this.s = - this.s
			}
			this.x = u
			this.add()
		}
		
		// sinon aucun changement
	}

	this.recipr = function() {
		//this.comment("--- recipr ---")
		if(this.test && this.x < this.y) {
			this.ok=true
			this.comment("=== reciprocité quadratique ===", "or")
			var e = (this.x-1)*(this.y-1)/4
			var r = (e%2==1)?"impair":"pair"
			this.comment("("+this.x+"-1)("+this.y+"-1)/4="+e+" est "+r)
			this.comment("("+this.x+"/"+this.y+") = ("+this.y+"/"+this.x+") * (-1)^"+e)
			if(e%2==1) this.s = -this.s
			var w=this.x
			this.x = this.y
			this.y = w
			this.add();
		}
	}
	this.den = function() {
		//this.comment("--- den ---")
		if(this.test) {
			if( this.y%2 == 0 || this.y==1) {

			this.test=false
			if(this.y%2 == 0 ) this.comment("=== Erreur : dénominateur pair ===", "or")
			else this.comment("=== Erreur : dénominateur 1 ===", "or")

			this.s="erreur"
			this.end()
			}
		}
	}

	this.den()
	//this.comment("test : "+this.test)

	if(this.test && gcd(this.x, this.y) != 1 ) {
		this.test=false
		this.comment("Pgcd ("+this.x+", "+this.y+") = "+gcd(this.x, this.y)+" > 1")
		this.s=0
		this.end();
	}

	for(var z=0;(this.test && this.ok);z++) {
		this.ok=false
		//this.comment("--- while test ---")
		this.modulo()
		this.moinsun()
		this.deux()
		this.pair()
		this.un()
		this.nul()
		this.recipr()
	}
	if(this.m<=1000000) {
	this.isprime = is_prime(this.m);
	//if(this.isprime) this.comment(this.m+" est premier.\n")

	if(this.isprime) {
		this.comment(this.m+" est premier, il y a équivalence  symbol = 1  <==>  résidu quadratique")
	} else {
		this.comment(this.m+" n'est pas premier, il n'y a pas équivalence.")
	}

	if(this.v==1) {
		if(this.isresidu()) {
			this.comment("Après vérification, "+this.n+" est bien un résidu mod "+this.m)
			this.comment("En effet "+this.sq+"^2 = "+this.n+" mod "+this.m)
		} else {
			this.comment("Après vérification, "+this.n+" n'est pas un résidu mod "+this.m+" (contre-exemple)")
		}
	} else if (this.v==-1) {
		if(this.isresidu()) {
                        this.comment("Après vérification, "+this.n+" est un résidu mod "+this.m+" (BUG : ne devrait pas arriver) !")
                        this.comment("En effet "+this.sq+"^2 = "+this.n+" mod "+this.m)
                } else {
                        this.comment("Après vérification, "+this.n+" n'est pas en effet un résidu mod "+this.m)
                }
	}
	}
	//alert(this.st)
	return {v: this.v, expl: this.st, ligne: this.su0}
}


var nbresf=new Array("aucune","un","deux","trois","quatre","cinq","six","sept","huit","neuf","dix")
var nbdivisions = new Array("Est impair"," division par deux"," divisions successives par deux")
var commentaires = new Array("","");

var CM="//"
function com(){
	CM=document.frm.co.value;
}