libsnark中BN128 curve twist参数计算依据

通过使用twist，可有效降低pairing时的计算量。 // parameters for Barreto–Naehrig curve E/Fq : y2 = x3 + b // parameters for twisted Barreto–Naehrig curve E’/Fq2 : y2 = x3 + b/xi （xi should be in Fq2 and neither a square nor a cube。见下面运行结果中，求取有限域内的平方根和立方根均应为空。） 以libsnark中的BN128curve为例，可将Fq12 的数据计算压缩到twist Fq2 中。 magma脚本验证：

    clear;
    q:=21888242871839275222246405745257275088696311157297823662689037894645226208583;
    Fq:=GF(q);
    beta:=-1;
    Fq2:=ExtensionField;

    E:=EllipticCurve([Fq|0,3]);
    E;

    a:=Random(Fq2);
    a;
    1/a;
    a in Fq2;

    b:=19485874751759354771024239261021720505790618469301721065564631296452457478373+266929791119991161246907387137283842545076965332900288569378510910307636690*u;
    b in Fq2;
    xi:=3/b;
    xi; //is u+9
    xi in Fq2;

    //xi should be neither a square nor a cube  in Fq2.
    Poly:=PolynomialRing(Fq2);
    f:=x^3;
    y:=u+9;
    Roots(y-f);
    f:=x^2;
    y:=u+9;
    Roots(y-f);
    
   	f:=x^2;
    y:=u+2; // (u+2) is the least quadratic nonresidue in Fq2.
    Roots(y-f);
   	tq2:=(q^2-1)/2^4;//bn128_Fq2_s = 4;
   	tq2;
	z:=(u+2)^29943448501038927652624252826042421299953269783193801402277987640879380855398639840490065738714866998199264519675818766364765977133724184290399563929243;
	z;
	bn128_Fq2_nqr_to_t:=5033503716262624267312492558379982687175200734934877598599011485707452665730+314498342015008975724433667930697407966947188435857772134235984660852259084*u;
	z eq bn128_Fq2_nqr_to_t;

运行结果为：

Elliptic Curve defined by y^2 = x^3 + 3 over
GF(2188824287183927522224640574525727508869631115729782366268903789464522620858\
3)
13001347582890148168573785629988825358653633406992291128800362041164663359735*u
    + 4783115208435455268283727466313913519357002878471347041631987943330746975\
    614
7359893158263440314439242922388117105343590178239087108751394080541658734265*u +
    122500035872534992363235926999453159333177929124139107437639371009777982517\
    92
true
true
u + 9
true
[]
[]
[]
2994344850103892765262425282604242129995326978319380140227798764087938085539863\
9840490065738714866998199264519675818766364765977133724184290399563929243
314498342015008975724433667930697407966947188435857772134235984660852259084*u +
    503350371626262426731249255837998268717520073493487759859901148570745266573\
    0
true

验证bn128_G1::G1_one和bn128_G2::G2_one取值。 对应magma脚本为：

clear;
    q:=21888242871839275222246405745257275088696311157297823662689037894645226208583;
    Fq:=GF(q);
    beta:=-1;
    Fq2:=ExtensionField;
    r:=21888242871839275222246405745257275088548364400416034343698204186575808495617;

    E:=EllipticCurve([Fq|0,3]);
    E;
    P:=E![1,2];
    PointsAtInfinity(E)[1];

   // Order(P); //is r.

    b:=19485874751759354771024239261021720505790618469301721065564631296452457478373+266929791119991161246907387137283842545076965332900288569378510910307636690*u;
    b in Fq2;

    Et:=EllipticCurve([Fq2|0,b]);
    Et;
    tP:=Et![15267802884793550383558706039165621050290089775961208824303765753922461897946+9034493566019742339402378670461897774509967669562610788113215988055021632533*u,644888581738283025171396578091639672120333224302184904896215738366765861164+20532875081203448695448744255224543661959516361327385779878476709582931298750*u];
    //Order(tP);
    r*tP; //tP in twisted curve order is r.
    PointsAtInfinity(Et)[1];

运行结果为：

Elliptic Curve defined by y^2 = x^3 + 3 over
GF(2188824287183927522224640574525727508869631115729782366268903789464522620858\
3)
(0 : 1 : 0)
true
Elliptic Curve defined by y^2 = x^3 + (2669297911199911612469073871372838425450\
    76965332900288569378510910307636690*u +
    194858747517593547710242392610217205057906184693017210655646312964524574783\
    73) over GF(218882428718392752222464057452572750886963111572978236626890378\
94645226208583^2)
(0 : 1 : 0)
(0 : 1 : 0)