二次对合变换群问题

mathe

难题征解中轨迹是否为圆的帖子中提出一个二次对合变换，也就是给定一个目标二次曲线和一个变换二次曲线，对于目标二次曲线上的任意一个点，沿着某个方向向变换二次曲线做切线，交目标二次曲线于另外一个点为变换结果。
而其中比较有用的是目标曲线和变换曲线确定的二次曲线系中任意一条作为变换曲线构成的二次对合变换相互直接的复合变换还在它们之中，而且这种复合可交换。所以这种变换之间的复合变化运算构成了这个二次曲线系上的一个交换群。
而确定这个群的结构是一个有趣的问题，特别如果我们将问题限制在有限域上，那么群总是有限的，如何计算群的阶就是一个问题了
题目中已经找到一个计算方案，我们假设有俩参数\(a,b\)其中\(a*b\neq1\)
我们设$t_0=0,t_1=1,t_2=4(a-1)(b-1)/(ab-1)^2,t_{n+1}t_{n-1}={(t_n-1)^2}/{(abt_n-1)^2}$
由此在某个域上我们可以这样反复计算值得重新得出某个$t_n=0$从而算出其阶
具体信息请查看13#附件

mathe

比如我们限定在11阶域上，取a=2,b=3,可以算出t数列为1,10,3,6,3,10,1,0所以是8阶群，而如果a=2,b=4,那么是6阶1,9,3,9,1,0
所以群的阶数非常诡异吧。
另外每个数在群里出现两次是因为变换是有向的，其实两次分别代表了不同方向。而0代表恒等变换所以是无向的，另外偶数阶群还会有一个元只出现一次，那就是一个二阶元，其平方是恒等变换，是一个对合变换。
有时候计算中会出现分母为0的情况，其实对应的是无穷远参数对应的变换，其麻烦之处是下一个元用这个公式不好推算，我们还需要进一步分析如何算下去

mathe

找了原始矩阵形式看了一下，无穷大点前后两个数都必然是$1/{ab}$.也就是说无穷大必然只出现一次，它对应一个对合变换，计算到它，整个群正好也枚举了一半。

mathe

现在可以有以下代码计算群的阶

1. get_order(a,b,P)={
   
2.     local(u,v,t1,t2,t3,c);
   
3.     c=2;
   
4.     u=Mod(a,P);v=Mod(b,P);
   
5.     t1=Mod(1,P);t2=4*(u-1)*(v-1)/(u*v-1)^2;
   
6.     while(t2!=0, if(u*v*t2-1==0, c=c+1;c=c*2;break);t3=(t2-1)^2/(u*v*t2-1)^2/t1;c=c+1;t1=t2;t2=t3;if(t2==0, break));
   
7.     c
   
8. }
   

复制代码

mathe

利用这个方法，对于素数P,我们应该可以找到一些阶大概在P/4左右的素数阶群。就是不知道是否有计算群的阶的比较有效的方法。如果对于很大的P都能够有有效计算阶的方法，也许可以将这个群应用于密码学

mathe

1. qcov_num_add_poly(a,b,P, tn, tm)={
   
2.     local(r);r=0;
   
3.     if(tn==P&&tm==P,
   
4.         r=Mod(1,P)*x^2,
   
5.         if(tm==P, tm=tn;tn=P );
   
6.         if(tn==P,
   
7.           if(tm==0, r=Mod(0,P),         
   
8.             r=( Mod(1,P)*x-1/Mod(a*b*tm,P) )^2
   
9.           ),
   
10.           if(tn==0, r=(Mod(1,P)*x-Mod(tm,P))^2,
    
11.             r=Mod((a*b*tm*tn-1),P)^2/Mod(tn,P)^2*x^2+
    
12.               Mod(-2*a*b*tm^2+(-2*a*b*tn^2+4*a*tn+4*b*tn-2)*tm/tn-2,P)/Mod(tn,P)*x
    
13.              +Mod((tm/tn-1)^2,P)
    
14.           )
    
15.         )
    
16.     );
    
17.     r
    
18. }
    
19. 
    
20. get_other_root(r1,r2,P)={
    
21.     local(d1,d2,r,t,t2);
    
22.     r=P+1;
    
23.     d1=poldegree(r1);d2=poldegree(r2);
    
24.     if(d2<1&&r2==0&&d1==1,
    
25.        r=-polcoeff(r1,0)/polcoeff(r1,1);
    
26.        r=component(r,2)
    
27.     );
    
28.     if(d2==2&&d1==1,
    
29.        t=-polcoeff(r1,0)/polcoeff(r1,1);
    
30.        t2=subst(r2,x,t);
    
31.        if(t2==0, r=P)
    
32.     );
    
33.     if(d2==2&&d1==2,
    
34.        r1=r1/polcoeff(r1,2);
    
35.        r2=r2/polcoeff(r2,2);
    
36.        r2=r2-r1;
    
37.        if(poldegree(r2)==1,
    
38.            t=-polcoeff(r2,0)/polcoeff(r2,1);
    
39.            t2=subst(r1,x,t);
    
40.            if(t2==0,
    
41.               r=component(polcoeff(r1,0)/t,2)
    
42.            )
    
43.        )
    
44.     );
    
45.     r
    
46. }
    
47. 
    
48. get_common_root(r1,r2,P)={
    
49.     local(d1,d2,r,t,t2);
    
50.     r=P+1;
    
51.     d1=poldegree(r1);d2=poldegree(r2);
    
52.     if(d1<=1&&d2<=1, r=P,
    
53.         if(d2<=1,t=r2;r2=r1;r1=t;t=d2;d2=d1;d1=t);
    
54.         if(d1==1,
    
55.            t=-polcoeff(r1,0)/polcoeff(r1,1);
    
56.            t2=subst(r2,x,t);
    
57.            if(t2==0, r=component(t,2), r=P+1),
    
58.            if(d1==0, r=P+1,
    
59.                 r1=r1/polcoeff(r1,2);r2=r2/polcoeff(r2,2);
    
60.                 r1=r1-r2;
    
61.                 if(poldegree(r1)<1, if(r1==0, r=P+2,r=P+1),
    
62.                     r1=r1/polcoeff(r1,1);
    
63.                     t=-polcoeff(r1,0)/polcoeff(r1,1);
    
64.                     t2=subst(r2,x,t);
    
65.                     if(t2==0, r=component(t,2), r=P+1)
    
66.                 )
    
67.             )
    
68.         )
    
69.     );
    
70.     r
    
71. }
    
72. 
    
73. qcov_group_add(a,b,P,tn,tn_p,tm,tm_p)={
    
74.     local(tmp1,tmp2,r1,r2);
    
75.     r1=r2=P+1;
    
76.     if(tm==tn&&tn_p==tm_p,
    
77.        r1=tn_p;r2=if(tn_p==P, tn, component(Mod(tn-1,P)^2/Mod(tn*a*b-1,P)^2,2)),
    
78.      tmp1=qcov_num_add_poly(a,b,P, tn, tm_p);
    
79.      tmp2=qcov_num_add_poly(a,b,P,tn_p,tm);
    
80.      r2=get_common_root(tmp1,tmp2,P);
    
81.      if(r2==P+1, print("invalid r2"),
    
82.        tmp1=qcov_num_add_poly(a,b,P, 1, r2);
    
83.        tmp2=qcov_num_add_poly(a,b,P, tn, tm);
    
84.        r1=get_common_root(tmp1,tmp2,P);
    
85.        if(r1==P+2, tmp2=qcov_num_add_poly(a,b,P,tn_p,tm_p);
    
86.              r1=get_other_root(tmp1,tmp2,P));
    
87.        if(r1==P+1, print("invalid r1"))
    
88.      )
    
89.     );
    
90.     [r1,r2]
    
91. }

复制代码

mathe

上面的pari/gp可以实现这种群里两个元的加法。由于每个元可以出现多次，我们需要使用它和紧跟着它后面的元素来表示。比如qcov_group_adf(2,3,11,10,3,1,0)=[1,10]代表参数为2，3模11的群里面第一个10（也就是序号2）和后一个1（序号为7）之和是第一个1（序号为1），也就是序号2+7=1(mod8)

mathe

349: (2,20) 89 347: (2,74) 89 337: (2,18) 89 131: (2,131) 89 317: (2,50) 83 313: (2,17) 83 311: (2,44) 83 307: (2,15) 79 293: (2,22) 79 283: (2,90)  79 281: (2,4) 73 277: (2,2) 139 271: (2,19) 73 269: (2,44) 73 263: (2,2) 131 257: (2,42) 71 251: (2,36) 67利用计算机算了若干个素数对应的群的阶的最大素因子，可以看出对于大部分素数，这个数略大于其1/4，但是少数例外约等于一半。

mathe

如果想实际应用于公钥体系，如同椭圆曲线，我们需要选择256比特的大素数P,然后需要随机选择其中阶接近P/4的素数的一个群。而这部分计算非常费时间都没事，只要能够找到一个，就可以固定使用了。而随机算法中，对于任意一个随机选择的元素，我们可以先计算其12次方，淘汰小因子2,3,4，然后对这个新元素，玫举其n次方，n约在P/4

mathe

我把这个内容简单整理了一下，放在附件中，请大家一起审查一下。如果能够帮忙找一个具有大素数阶的群更加好。另外我现在的word里面没有数学公式编辑器，大家知道要怎么安装吗？