CoCalc -- KSS16results.sagews

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

Views: ⁴⁵

R.<u>=QQ['u']
p=(1/980)*(u^10+2*u^9+5*u^8+48*u^6+152*u^5+240*u^4+625*u^2+2398*u+3125)
l=((u^8+48*u^4+625)/61250)
d=14*(p^8+1)/l
B=(u+1)^2+4;
A=u^3*B+56;

#Development presented by Zhang et al.-----------
c0=-11*u^9-22*u^8-55*u^7-278*u^5-1172*u^4-1390*u^3+1372;
c1=15*u^8+30*u^7+75*u^6+220*u^4+1280*u^3+1100*u^2;
c2=25*u^7+50*u^6+125*u^5+950*u^3+3300*u^2+4750*u;
c3=-125*u^6-250*u^5-625*u^4-3000*u^2-1300*u-15000;
c4=-2*u^9-4*u^8-10*u^7+29*u^5-54*u^4+145*u^3+4704;
c5=-20*u^8-40*u^7-100*u^6-585*u^4-2290*u^3-2925*u^2;
c6=50*u^7+100*u^6+250*u^5+1025*u^3+4850*u^2+5125*u;
c7=875*u^2+1750*u+4375;


#Development presented by Zhang et al. to simplify the first equations:
c00=-11*(u^4*A+27*u^3*B+28)+19*A;
c11=5*(3*u^3*A+44*u^2*B);
c22=25*(u^2*A+38*u*B);
c33=-125*(u*A+24*B);
c44=-(2*u^4*A+55*u^3*B)+84*A;
c55=-5*(4*u^3*A+117*u^2*B);
c66=25*(2*u^2*A+41*u*B);
c77=125*7*B;

c0==c00; c1==c11; c2==c22; c3==c33; c4==c44; c5==c55; c6==c66; c7==c77

False
True
True
False
True
True
True
True


#correction in the expression of c3 (13000 instead of 1300)-
s0=-11*u^9-22*u^8-55*u^7-278*u^5-1172*u^4-1390*u^3+1372;
s1=15*u^8+30*u^7+75*u^6+220*u^4+1280*u^3+1100*u^2;
s2=25*u^7+50*u^6+125*u^5+950*u^3+3300*u^2+4750*u;
s3=-125*u^6-250*u^5-625*u^4-3000*u^2-13000*u-15000;
s4=-2*u^9-4*u^8-10*u^7+29*u^5-54*u^4+145*u^3+4704;
s5=-20*u^8-40*u^7-100*u^6-585*u^4-2290*u^3-2925*u^2;
s6=50*u^7+100*u^6+250*u^5+1025*u^3+4850*u^2+5125*u;
s7=875*u^2+1750*u+4375;

dd=s0+s1*p+s2*p^2+s3*p^3+s4*p^4+s5*p^5+s6*p^6+s7*p^7;

dd==d

True

#Correction in the expression of l0 (a missing term 616)
l0=-11*(u^4*A+27*u^3*B+28)+19*A+616;
l1=5*(3*u^3*A+44*u^2*B);
l2=25*(u^2*A+38*u*B);
l3=-125*(u*A+24*B);
l4=-(2*u^4*A+55*u^3*B)+84*A;
l5=-5*(4*u^3*A+117*u^2*B);
l6=25*(2*u^2*A+41*u*B);
l7=125*7*B;
dd=l0+l1*p+l2*p^2+l3*p^3+l4*p^4+l5*p^5+l6*p^6+l7*p^7;

s0==l0; s1==l1; s2==l2; s3==l3; s4==l4; s5==l5; s6==l6; s7==l7

True
True
True
True
True
True
True
True


#Notre nouveau vecteur---------
m0=2*u^8+4*u^7+10*u^6+55*u^4+222*u^3+275*u^2
m1=-4*u^7-8*u^6-20*u^5-75*u^3-374*u^2-375*u
m2=-2*u^6-4*u^5-10*u^4-125*u^2-362*u-625
m3=-u^9-2*u^8-5*u^7-24*u^5-104*u^4-120*u^3+196
m4=u^8+2*u^7+5*u^6+10*u^4+76*u^3+50*u^2
m5=3*u^7+6*u^6+15*u^5+100*u^3+368*u^2+500*u
m6=-11*u^6-22*u^5-55*u^4-250*u^2-1116*u-1250
m7=7*u^5+14*u^4+35*u^3+392

#Our development of the new vector m ----------
m00=2*u^3*A+55*u^2*B
m11=-4*u^2*A-75*u*B
m22=-2*u*A-125*B
m33=-u^4*A-24*u^3*B+196
m44=u^3*A+10*u^2*B
m55=3*u^2*A+100*u*B
m66=-11*u*A-250*B
m77=7*A

m0==m00; m1==m11; m2==m22; m3==m33; m4==m44; m5==m55; m6=m66; m7==m77

True
True
True
True
True
True
True

vect=m0+m1*p+m2*p^2+m3*p^3+m4*p^4+m5*p^5+m6*p^6+m7*p^7

vect==(14*u^3*(p^8+1))/(125*l)

True

u=2^49+2^26+2^15-2^7-1

p=(1/980)*(u^10+2*u^9+5*u^8+48*u^6+152*u^5+240*u^4+625*u^2+2398*u+3125)
l=(u^8+48*u^4+625)/61250

#-------------- Fp--------------
Fp=GF(p)
#-------------------------------

#--------------Fp^4--------------
K4.<i>=PolynomialRing(Fp)
Fp4.<i>=FiniteField(p^4,modulus=i^4+3)
#------------------------------------
#-------------Fp^8---------------------
K8.<v>=PolynomialRing(Fp4)
Fp8.<v>=Fp4.extension(v^4-i)
#-------------------------------------

#---------------Fp^16-------------------

K16.<z>=PolynomialRing(Fp8)
Fp16.<z>=Fp8.extension(z^2-v)
Fp16.is_field=lambda:True
#---------------------------------------

Fp4.is_field(); Fp8.is_field(); Fp16.is_field()

True
True
True

f=Fp16.random_element()

e2=f^(p^8-1)

#Algorithm presented by Zhang et al.
def algoKSS16(f,u):

    t1=e2^4
    t2=t1^8
    t3=t2^2
    f1=t2*t1^(-1)
    f2=f1^2
    f3=e2^(u+1)
    f4=f3^(u+1)
    f5=f4*t1
    
    t4=f5^8
    f6=f5^(u)
    f7=f5^(-1)*t4
    f8=t4^3
    t5=f6^8
    f9=f6^(u)
    f10=t5*f6^(-1)
    f11=f10^2
    t6=f9^8
    f12=f9^(u)
    f13=t6*f9^(-1)
    
    f14=f13^2
    f15=f12*f2
    t7=f15^2
    t8=t7^4
    t9=t8^4
    f16=f15^(u)
    f17=t9*t7
    f18=f17*f15
    f19=f18^2
    f20=f19^2
    f21=f20*t8
    f22=f16*f8
    f23=f22^(u)
    f24=f23*f11
    t10=f23^2
    
    f25=f23^(u)
    f26=t10*f10^(-1)
    t11=f25^4
    f27=f25^(u)
    f28=t11*f25^(-1)
    
    f29=t11*f25
    
    f30=f13*f14
    f31=f28*f30^(-1)
    f32=f12^2
    f33=f32*f12
    f34=f27*f33
    f35=f34^2
    f36=f35*f12
    f37=f36^(-1)*f21
    
    f38=f34*f1
    f39=f38^2
    f40=f39^2
    f41=f40^2
    f42=f39*f38
    f43=f41*f42
    f44=f43^(-1)*f18
    h1=f7^(p^7)
    h2=f22^(p^3)
    h3=f24^(p^2)
    h4=f26^(p^6)
    h5=f29^(p^5)
    h6=f31^p
    h7=f37^(p^4)
    h8=h1*h2^(-1)
    h9=h8^2
    h10=h9^2
    h11=h10*h8
    h12=h11*h3
    h13=h12*h4
    h14=h13^2
    h15=h14^2
    h16=h15*h13
    h17=h16*h6
    h18=h17*h5^(-1)
    h19=h18^2
    h20=h19^2
    h21=h20*h18
    h22=h21*h7
    h23=h22*f44
    
    return h23

#Corrected version of Zhang et al. work-----------------
def algo1KSS16(f,u):

    t1=e2^4
    t2=t1^8
    t3=t2^2
    
    a0=t3^8
    a1=a0*t3
    a2=a1*t2
    a3=t1^2
    a2=a3*a2
    
    
    
    
    f1=t2*t1^(-1)
    f2=f1^2
    f3=e2^(u+1)
    f4=f3^(u+1)
    f5=f4*t1
    
    t4=f5^8
    f6=f5^(u)
    f7=f5^(-1)*t4
    f8=t4^3
    t5=f6^8
    f9=f6^(u)
    f10=t5*f6^(-1)
    f11=f10^2
    t6=f9^8
    f12=f9^(u)
    f13=t6*f9^(-1)
    
    f14=f13^2
    f15=f12*f2
    t7=f15^2
    s1=t7^2
    t8=s1^2
    
    s2=t8^2
    s2=s2*t8
    s3=s2*s1^(-1)
    s4=s3^2
    s5=s4^2
    s6=s5*s1
    
    
    
    f16=f15^(u)
    f22=f16*f8
    f23=f22^(u)
    f24=f23*f11
    t10=f23^2
    
    f25=f23^(u)
    f26=t10*f10^(-1)
    t11=f25^4
    f27=f25^(u)
    f28=t11*f25^(-1)
    
    f30=f13*f14
    f29=t11*f30
    
    
    f31=f28*f30^(-1)
    f31=f31*(f13)^(-1)
    
    f32=f12^2
    f33=f32*f12
    f34=f27*f33
    f35=f34^2
    f36=f35*f12
    f37=f36^(-1)*s6
    
    f38=f34*f1
    f39=f38^2
    f40=f39^2
    f41=f40^2
    f42=f39*f38
    f43=f41*f42
    f44=f43^(-1)*s3
    f44=f44*a2
    
    h1=f7^(p^7)
    h2=f22^(p^3)
    h3=f24^(p^2)
    h4=f26^(p^6)
    h5=f29^(p^5)
    h6=f31^p
    h7=f37^(p^4)
    h8=h1*h2^(-1)
    h9=h8^2
    h10=h9^2
    h11=h10*h8
    h12=h11*h3
    h13=h12*h4
    h14=h13^2
    h15=h14^2
    h16=h15*h13
    h17=h16*h6
    h18=h17*h5^(-1)
    h19=h18^2
    h20=h19^2
    h21=h20*h18
    h22=h21*h7
    h23=h22*f44
    
    
    return h23

#Our new algorithm (a new vector for computing the hard part of the final exponentiation)

def algo2KSS16(f,u):
    t0=e2^2
    t1=t0^2
    t2=e2^(u+1)
    t3=t2^(u+1)
    t4=t3*t1
    
    t5=t4^(u)
    t6=t4^5
    t7=t1^8
    t8=t7^2
    t9=t7*t1^(-1)
    t10=t9^2
    t11=t5^(u)
    t12=t11^(u)
    
    t01=t12*t10
    t14=t01^(u)
    t13=t14^(-2)
    t00=t6^5
    t15=t00^5
    
    t0=t13*t15^(-1)
    t16=t0^2
    t17=t13^4
    t18=t17*t14
    t2=t16*t18
    t19=t14^(u)
    t20=t19^(u)
    t21=t20^(u)
    t22=t19^2
    
    t23=t5^5
    t24=t23^5
    t25=t24^3
    t26=t24*t25
    t27=t22^2
    t37=(t27*t25)^(-1)
    
    t28=t27*t19^(-1)
    t3=t28*t26
    t29=t11^5
    t30=t29^2
    t4=t20*t30
    s0=t20^2
    s1=t30^5
    s2=s1*t29
    s3=s0*s2
    t31=t12^(24)
    t5=t21^(-1)*t31^(-1)
    
    t6=t8^3*t1
    t7=t5*t6
    t8=t1^7
    t32=t37^p*t7^(p^3)
    t32=t32*t3^(p^5)
    t32=t32*t8^(p^7)
    t33=t0^(p^2)*t2^(p^6)
    t=t32*t33
    t=t*t4^(p^4)
    t=t*s3
    
    return t

def verif(f,u):
    
    t0=e2^2
    t1=t0^2
    t2=e2^(u+1)
    t3=t2^(u+1)
    t4=t3*t1
    
    t5=t4^(u)
    t6=t4^5
    t=t1^8
    
    
    return t

verif(e2,u)

((774666048175822437287147683465263050806207073392681182027686841501398299199611619460929429563599460445153518194100734177142857239467098254522437*i^3 + 1500190307399025881089151694717429151571380240823522047690405044428006671824387328154461538444026435939708681146048900308712010132218109001633096*i^2 + 518933903875478018675990341724701409748920572930935882637524723334675629381796375509636832315047261236912280564551038877803417982036126366890126*i + 2129868083468869195998156190159927378473322461479722251964012872517114121831421023436266520049135345657865126516229074218130747084078522391103088)*v^3 + (1929094609532817418368249948683033615530843704410934698217015969022286407660775756358381046337332621087974342255522554141074284264419754300189841*i^3 + 2976593582397352021311040568383037405824722426712690240017184290808048759318129775232927553065212855087668116762950164603859154125207534575550187*i^2 + 105632697379447922009994307188359329216313190356927066851849992042543891744122533121610214230990739473807265981100395459982569171492133049561099*i + 546554735011673608479784636768013952802448926683038665309064962520104038121738883419562104551685193952105042824902410294767608027175633394684866)*v^2 + (1378253444858292611173644204977426334770659987165917937001727467171208120574719925735366149519659054599377628993240823766655068487958533485196926*i^3 + 1029217736742493585078790989419320487121583950379351234147845740631904556833914144702046652874752510003437129224275756902296708558401903703379961*i^2 + 539316290099615395032197505128815495728104174054024000985147914046511052071387626524987126382612020937547558601840263288300395889966661781195236*i + 2004114503129738225498166022774866907025027672232053555054472837304275181700704433869596916092680254255212679386445525793240191088348842835612441)*v + 1638925278842268453236754844055633537848713920143083631139422623130598603577395865900559642591969236411733945690891643038700632810018419451763954*i^3 + 1330215183607538520607812615248085604338055747921260469800993434192330951766287188844932531814371975441745733345804888862246344131538824930089296*i^2 + 2395057434553631158438032848439320280175183946747822160991589394072696582943819559434168983559610279740286512233047103596332275812205197032344959*i + 1170282422790740817291845595795100563101218692975425140726868653851263787730145197575393494455842130004015618017805388340192628949375224507402589)*z + (661560581303425852708317464644532756054438430454669058671811599656730873698864982399618179300668452786775338275522806467611130809990768841468216*i^3 + 110525183569374395461408701754464362268332570754277482347258279196322310245019091418451805907347200513599074701945201438590624780124973117285490*i^2 + 2676396194342688360278164399957152918491754639675971861438746124636634760359256487765692124240375314770861563024618618468369934382003477159012948*i + 599002408310706334010531371318225178771158085969082917799561689032055744773942239207327363275593978176019140660290394704307654035023565327812082)*v^3 + (1944860622239912442055565954405642229285811337890037163249453875359630617330716704483222711302936528684653253789010675819704021201661775297772268*i^3 + 852508503490317247340997552532237627463723408362893844613987040771863446494420062171026630409210386423908871426920080248843688002471393001703543*i^2 + 2175845989408331084515748616293201932629554712280064675968297161092153180726750105333428096882563070712429984633468196233098256442081485845836893*i + 973766941356006616733210057023462845091798835901189453881897916864630850564164842454201318046739711236914851401450562230748571891339134506850196)*v^2 + (1927045153403021710195161239102352917188082007441698550608974330532252012173542200012678686480164996361704396681615953111672839157153017878695822*i^3 + 2634968128469727091183321308766120023773511505111455773088894354736444689616597844840439054460191954038585544306656012095594846300363374715647651*i^2 + 2579287052355767135577949150368475204492394097115756394894756515413963637994267821546790327620271419184555532406496091581376630621976670816109622*i + 3022679658637625982357639224124912463149111341577217891517502064636053013012422956586351544132949378771968305212589537044374276493439375173211102)*v + 187159521876473736086896928958749627411847842861818446175363723638172686788927348285677065166252548524567075902129501055770130678789494069758862*i^3 + 885667401682225976776572752358813069448851697690033635048976824269674362317912334909370812024392225622601470008572529941592001058349350297986658*i^2 + 1794646552273790397332398690786019401716680109567140449808926284440610778137068832423685882735647009923011843582127464342682930551276709106527346*i + 1228263562730887301813909530183310615801332031205535005431808841324203701685372180569204800488507739488702417481425247675074639657162884422067366

m33

-u^9 - 2*u^8 - 5*u^7 - 24*u^5 - 104*u^4 - 120*u^3 + 196

e2^m33

Error in lines 1-1
Traceback (most recent call last):
  File "/usr/local/lib/python2.7/dist-packages/smc_sagews/sage_server.py", line 995, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "sage/structure/element.pyx", line 2431, in sage.structure.element.RingElement.__pow__ (/projects/sage/sage-7.6/src/build/cythonized/sage/structure/element.c:17331)
    return generic_power_c(self,n,None)
  File "sage/structure/element.pyx", line 4124, in sage.structure.element.generic_power_c (/projects/sage/sage-7.6/src/build/cythonized/sage/structure/element.c:28160)
    raise NotImplementedError("non-integral exponents not supported")
NotImplementedError: non-integral exponents not supported




u=2^49+2^26+2^15-2^7-1
p=(1/980)*(u^10+2*u^9+5*u^8+48*u^6+152*u^5+240*u^4+625*u^2+2398*u+3125)
p-1/16

52190601275220023231697647741702631268191176898059196715999260492437989264626813617438828148076937322045837166143485169405262035644291816800165903/16

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

Product

Resources

Company

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more, all in one place. Commercial Alternative to JupyterHub.

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.