Bill Allombert on Tue, 17 Apr 2018 23:11:12 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Reduced Tate pairing in supersingular elliptic curves


On Tue, Apr 17, 2018 at 09:39:11PM +0200, Bill Allombert wrote:
> On Tue, Apr 17, 2018 at 10:10:49PM +0300, Aleksandr Lenin wrote:
> > Hi all,
> > 
> > I have stepped across the case when I get a trivial value 1 for the
> > reduced Tate pairing for seemingly legit inputs. Both inputs belong to
> > the r-torsion, point 1 is defined over the base-field subgroup, point 2
> > does not belong to the base-field subgroup (and it shouldn't, as the
> > reduced Tate pairing is supposed to return 1 if two points belong to the
> > same subgroup). But the result is nevertheless 1, although in theory it
> > looks like it shouldn't.
> > 
> > I attach the C++ code for libPARI with inputs and the code I was using
> > to produce this result.
> 
> Hello Aleksandr,
> 
> Unfortunately, your code does not compile. Please consider sending GP
> code example instead.
> 
> My reading is that you are calling FF_elltatepairing with a parameter p1
> whose coefficients are t_INT and not t_FFELT.
> 
> This is not valid. You need to convert the components of p1 to FFELT or
> use the high-level function elltatepairing.

Maybe I am wrong on this one. At least this does not seem to be the
problem.  I tried to convert your C program to GP (in attachment).
It also gives 1. 

However E(F_q) is isomorphic to (Z/lZ)^2 with r^6 dividing l,
and p2 is of order r, so p2 can be written as [r].q for some point q,
so the Tate pairing (p1,p2) is trivial.

Cheers,
Bill.
r = 115792089237316195423570985008687907853269984665640564039457584007913130327851;
p = 729995325678669359612263452605506580733004427132673582314497567805014278041635994590090082180502116143263532359048738406597239443318640672711245526346238092246683746134657288054890921912991126239130697620428047828998444390759826609224613037843714024073696709708567493436988013034917053907792300971937911565720840872897751218935438210856450629634873555502858190089546937212523125070225588545551391707034179535007705558338179039614684525084857725397040972387874272971448091159792452744469591;
p1 = [416866340151231144999071547104363552860995592342107617914079000324381628161252265155645646854917176101609645586710923664886999924176044846510900094872811821512999385612906577590788149280356319811591000347648102887159624329635123286323730839020460834613075504904339611008560087599883844273800883881168320111158488361278933397816853937934926779232014231202042266788881007785375396656800844388723109494478629332994684564657346416564422982075930877830457781120143476348463212228485913738818378, 332617282081743765958457595331209402426543969823409409920211593987172038898954201278875792928497905587381429484928180618013398755967181957508337582717533897724873379440281463870584527916994925025070333137982197591362084522892577435310917767393712302706039550334126677727240346450052996401195274561866971151644056816349514618325673949647197767156490279473407609178487581825885626398304873791614461472577390168158829970346191915053707382080614765449833113137839636705734751352621516743726381];
p =[323835096672091128109519914566785095547699666695964334770724989155913496620293120337354058374930769954669940899969219387554719328257359458694798778402657621168324676375937875283168007232503735955552269877916079662046089679497781438420526238043055627372609457292555529361293689880121259497378515059917784373024675650018604892937621023989959813453649239377792409026313473481431097062900458413710095621691098110439012225036374236170080882525581730564537966637105841683438706003865158334361879, 96995708969082174029386372192146598856582423767391084007802154833605167125565120086193266518810107953218158243787512290935368962360366938408600464516374396487143688894851855808206836903352887290635476739165504596690182400273250031906505481976985386408091703095585683044627711755143903867142203095362609317948954191252558670513895497284388066199500635347784010694984498336131022426955975086103409966851132198916955647772119315622637951174020723482166760611028951847777953307999952433119298];
gen = ffgen(x^2+x+1*Mod(1, p));
curve = ellinit([0,124077955980], gen);
p2 = [gen*p[1],p[2]];
ellisoncurve(curve,p1)
ellisoncurve(curve,p2)
ellmul(curve,p1,r)
ellmul(curve,p2,r)
q = gen.p^gen.f;
fforder(ellweilpairing(curve,p1,p2,r),r)==r
elltatepairing(curve,p1,p2,r)^((q-1)/r)