#!/usr/bin/python
from array import array
from cons2 import rads, lrads, linvs, lcms, rngs, mxms, logss
from operator import mod, sub
import sys
import os

hed='dif,rut,exp,vlg,num'

def prnfct(inum):
	fct=fact(inum)
	str=''
	for tup in fct:
		if tup[1]==1:
			str+='%d'%tup[0]
		else:
			str+="%d^%d"%(tup[0], tup[1])
		str+='*'
	return str[:-1]	

def eea(a,b):
	v1 = [a,1,0]
	v2 = [b,0,1]
	while v2[0]<>0:
	   p = v1[0]//v2[0]
	   v2, v1 = map(sub,v1,[p*vi for vi in v2]), v2
	return v1

def minv(m,k):
	v = eea(m,k)
	if v[1]>=0:
		return v[1]
	else:
		return k+v[1]
		
def mdiv(dor, dend, rad):
    inv=minv(dend, rad)
    return mod(inv*dor, rad)

def dusqrs():
	tot=2
	lst=[]
	bits=len(bin(xmxm))-1
	for ind in range(1, bits):
		lst.append(tot)
		tot=(tot**2)%xmxm
	return lst
	
def dexp(lind):
	str=bin(lind)[2:]
	dat=str[::-1]
	lim=len(dat)
	tot=1
	for ind in range( lim):
		if(dat[ind]=='1'):
			tot=(tot*sqrs[ind])%xmxm
	return tot

def lres2dec(ires):
	lim=len(ires)
	tot=ires[0]
	ind=1
	while ind<lim:
		lrad=lrads[ind]
		cry=mod(tot, lrad)
		dig=mod((ires[ind]-cry)*linvs[ind], lrad)
		tot+=dig*lcms[ind]
		ind+=1
	return tot
	
def durut(res):
	rut=[]
	ind=0
	lim=len(res)
	while ind<lim:
		lrad=lrads[ind]
		logs=logss[ind]
		rut.append(logs[res[ind]]%lrad)
		ind+=1
	return rut
	
def dec2res(numd):
	ar=[]
	for rad in rads:
		ar.append(numd%rad)
	return ar

def euc(ar0, ar1):
    while ar0>0:
        rx=ar1%ar0
        ar1=ar0
        ar0=rx
    return ar1

def ilgr(pres):
	rut=durut(pres)
	return lres2dec(rut)
	
def ilg(val):
	pres=dec2res(val)
	return ilgr(pres)
	
def dudif(trg):
	trgr=dec2res(trg)
	lim=len(trgr)
	clog=ilg(trg)%xlcm
	trg1=trg<<1
	if trg1>xmxm:
		trg1-xmxm
	clog1=ilg(trg1)%xlcm
	dif=(clog1-clog)%xlcm
	return (clog, dif)
	
def fnd(loc):
	trg=loc[0]
	stp=loc[1]
	gcd=euc(stp, rng)
	if gcd>1:
		stp/=gcd
		trg/=gcd
	inv=minv(stp, rng)
	return (((inv*trg)%rng))
	
def duof(strt, nu):
	return mdiv(strt, (dexp(nu)), xmxm)

class clog:
	def __init__(self, num):
		self.num=num
		loc=dudif(num)
		self.dif=loc[1]
		self.vlg=loc[0]
		self.exp=fnd(loc)
		self.rut=duof(self.num, self.exp)
		if self.rut>xmxm2:
			self.rut=xmxm-self.rut
			self.exp=(self.exp+xlcm)%rng
	def chk(self):
		val=(dexp(self.exp)*self.rut)%xmxm
		if val==self.num:
			return 1
		return 0
	def chk1(self):
		if self.dif==1:
			val=(self.rut**2)%xmxm
			if val==1:
				return 1
			else:
				return -1
		return 0
	def dat(self):
		return self.dif, self.rut, self.exp, self.vlg, self.num
	def __str__(self):
		str='%d,%d,%d,%d,%d'%(self.dif, self.rut, self.exp, self.vlg, self.num)
		return str
		
def cmul(clg0, clg1):
	nur=(clg0.rut*clg1.rut)%xmxm
	nux=(clg0.exp+clg1.exp)
	if nux>xlcm:
		nux-=xlcm
	nuv=(nur*dexp(nux))%xmxm
	if nuv>xmxm2:
		nuv=xmxm-nuv
	return nuv
	
def cdiv(dend, sor):
	nur=mdiv(dend.rut, sor.rut, xmxm)
	nux=(dend.exp-sor.exp)
	if nux<0:
		nux+=xlcm
	nuv=(nur*dexp(nux))%xmxm
	if nuv>xmxm2:
		nuv=xmxm-nuv
	return nuv
	
def odrut(strt, trg):
	if trg&1==0:
		print 'need odd number'
		return
	print 'odrut'
	print 'start', strt
	ind=strt
	while ind<xmxm:
		clg=clog(ind)
		if clg.dif==1 and clg.exp%trg==0:
			rut=(clg.rut*dexp(clg.exp/trg))%xmxm
			chk=(rut**trg)%xmxm
			if chk==clg.num:
				print '%d=(%d^%d)mod(%d)'%(clg.num, rut,trg, xmxm)
				break
		ind+=1
		
def sqrut(strt):
	print 'sqrut'
	print 'start', strt
	ind=strt
	while ind<xmxm:
		clg=clog(ind)
		if clg.dif==1 and clg.rut==1 and clg.exp&1==0:
			exp2=clg.exp>>1
			rut=dexp(exp2)
			chk=(rut*rut)%xmxm
			if chk==clg.num:
				print '%d=(%d^2)mod(%d)'%(clg.num, rut, xmxm )
				break
		ind+=1
		
def man():
	print list(rads)
	print
	strt=xmxm>>2
	odrut(strt, 41)
	print
	sqrut(strt)

radcnt=6
rads=rads[:radcnt]
lrads=lrads[:radcnt]
xmxm=mxms[radcnt]
xmxm2=xmxm>>1
rng=rngs[radcnt-1]
xlcm=lcms[radcnt]
sqrs=dusqrs()
man();