Pebble Coding

ソフトウェアエンジニアによるIT関連技術の備忘録

python で有限体Fpでの楕円曲線上の有理点の群構造を調べる

ここでは、有限体F_{5}
(p=5)
楕円曲線 y^{2} = x^{3} + x + 1
(a=0,b=1,c=1) の有理点をpythonで調べています。 有理点の数は9です。(無限遠点を含む)
無限遠点はOと出力しています。
加法公式を用いて、有理点{P1, P2, ... P8}を2倍,3倍,...,9倍した点も示しています。
この計算の途中で元の有理点に戻った場合、あとは繰り返しなので、そこで計算を止めています。

P1,P2,P5,P6,P7,P8は9倍したところで無限遠点になるので、位数9の点といいます。 ここで倍々していくと9つ全ての点を通ります。
これを巡回群であるといいます。

P3,P4は3倍したところで無限遠点になるので、位数3の点といいます。

この群は2つの巡回群Z/3ZとZ/9Zの直積と同型であるといいます。

%matplotlib inline 
import numpy as np
import matplotlib.pyplot as plt

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def desc(self):
        if self.x == -1 and self.y == -1:
            return "O"
        return "("+str(self.x)+","+str(self.y)+")"
    
    def is_equal(self, other):
        return self.x == other.x and self.y == other.y

    def is_equal_negative(self, other, prime):
        return self.x == other.x and - self.y == other.y - prime
        
    def iszero(self):
        return self.x == -1 and self.y == -1
    
    @staticmethod
    def zero():
        return Point(-1, -1)

class EC:
    def __init__(self, a, b, c, p):
        self.a = a
        self.b = b
        self.c = c
        self.p = p
        self.calc_order()
    
    def calc_order(self):
        self.points = []
        for x in range(self.p):
            for y in range(self.p):
                pt = Point(x,y)
                if self.oncurve(pt):
                    self.points.append(pt)
        self.points_count = len(self.points)
        self.order = len(self.points)+1

    def oncurve(self, pt):
        l = ((pt.y**2) % self.p)
        r = ((pt.x**3) + self.a*(pt.x**2) + self.b*pt.x + self.c) % self.p
        return l == r

    def d(self):
        return -4*(self.a**3)*self.c \
                + (self.a**2)*(self.b**2) \
                + 18*self.a*self.b*self.c \
                - 4*(self.b**3) \
                - 27 * (self.c**2)
    
    def inverse(self, a):
        assert self.p >= 2
        return a ** (self.p-2)
    
    def plus(self, p1, p2):
        x1 = p1.x
        y1 = p1.y
        x2 = p2.x
        y2 = p2.y
        if (p1.iszero()):
            return p2
        if (p2.iszero()):
            return p1
        
        if p1.is_equal_negative(p2, self.p):
            return Point.zero()
        
        elif p1.is_equal(p2):
            if (y1 == 0):
                return Point.zero()
            else:
                lm = (3 * (x1 **2) + 2 * self.a * x1 + self.b) * self.inverse(2 * y1)
                x3 = (lm ** 2) - self.a - x1 - x2
                y3 = - lm *(x3-x1) - y1
        else:
            lm = (y2-y1) * self.inverse(x2-x1)
            x3 = (lm ** 2) - self.a - x1 - x2
            y3 = -(lm*(x3-x1) + y1)

        q = Point(x3 , y3)
        q2 = Point(x3 % self.p, y3 % self.p)
        if not self.oncurve(q2):
            print("p1 {0} p2 {1} q {2} q2 {3}".format(p1.desc(), p2.desc(), q.desc(), q2.desc()))
            assert False
        return q2

    def mul(self, p, n):
        q = p
        for i in range(n-1):
            q = ec.plus(q, p)
        return q

ec = EC(0, 1, 1, 5)

print "F" + str(ec.p)
print "d:" + str(ec.d())
print "#EC:" + str(ec.order)
print ""

plotx = [p.x for p in ec.points]
ploty = [p.y for p in ec.points]
n = ["P"+str(i+1) for (i, p) in zip(range(len(ec.points)), ec.points)]

for i in range(ec.points_count):
    baseP = ec.points[i]
    print "P"+str(i+1)+":" + baseP.desc()
    for j in range(2, ec.order+1):
        p = ec.mul(baseP, j)
        print str(j)+"*P"+str(i+1)+":"+p.desc()
        if (p == baseP):
            print ""
            break
    print ""
    
fig, ax = plt.subplots()
ax.scatter(plotx, ploty)

for i, txt in enumerate(n):
    ax.annotate(txt, (plotx[i],ploty[i]))
    
F5
d:-31
#EC:9

P1:(0,1)
2*P1:(4,2)
3*P1:(2,1)
4*P1:(3,4)
5*P1:(3,1)
6*P1:(2,4)
7*P1:(4,3)
8*P1:(0,4)
9*P1:O

P2:(0,4)
2*P2:(4,3)
3*P2:(2,4)
4*P2:(3,1)
5*P2:(3,4)
6*P2:(2,1)
7*P2:(4,2)
8*P2:(0,1)
9*P2:O

P3:(2,1)
2*P3:(2,4)
3*P3:O
4*P3:(2,1)


P4:(2,4)
2*P4:(2,1)
3*P4:O
4*P4:(2,4)


P5:(3,1)
2*P5:(0,1)
3*P5:(2,4)
4*P5:(4,2)
5*P5:(4,3)
6*P5:(2,1)
7*P5:(0,4)
8*P5:(3,4)
9*P5:O

P6:(3,4)
2*P6:(0,4)
3*P6:(2,1)
4*P6:(4,3)
5*P6:(4,2)
6*P6:(2,4)
7*P6:(0,1)
8*P6:(3,1)
9*P6:O

P7:(4,2)
2*P7:(3,4)
3*P7:(2,4)
4*P7:(0,4)
5*P7:(0,1)
6*P7:(2,1)
7*P7:(3,1)
8*P7:(4,3)
9*P7:O

P8:(4,3)
2*P8:(3,1)
3*P8:(2,1)
4*P8:(0,1)
5*P8:(0,4)
6*P8:(2,4)
7*P8:(3,4)
8*P8:(4,2)
9*P8:O

f:id:pebble8888:20170909165102p:plain

他の楕円曲線でも試してみましょう。

F_{13}
y^{2}=x^{3}+2 x+4

この場合、全ての点の位数が17となります。こういうのはわりと珍しいです。 この群はZ/17Zと同型であるといいます。

F13
d:-464
#EC:17

P1:(0,2)
2*P1:(10,6)
3*P1:(12,1)
4*P1:(2,9)
5*P1:(7,6)
6*P1:(5,10)
7*P1:(9,7)
8*P1:(8,8)
9*P1:(8,5)
10*P1:(9,6)
11*P1:(5,3)
12*P1:(7,7)
13*P1:(2,4)
14*P1:(12,12)
15*P1:(10,7)
16*P1:(0,11)
17*P1:O

P2:(0,11)
2*P2:(10,7)
3*P2:(12,12)
4*P2:(2,4)
5*P2:(7,7)
6*P2:(5,3)
7*P2:(9,6)
8*P2:(8,5)
9*P2:(8,8)
10*P2:(9,7)
11*P2:(5,10)
12*P2:(7,6)
13*P2:(2,9)
14*P2:(12,1)
15*P2:(10,6)
16*P2:(0,2)
17*P2:O

P3:(2,4)
2*P3:(8,5)
3*P3:(7,6)
4*P3:(0,2)
5*P3:(12,12)
6*P3:(9,6)
7*P3:(5,10)
8*P3:(10,6)
9*P3:(10,7)
10*P3:(5,3)
11*P3:(9,7)
12*P3:(12,1)
13*P3:(0,11)
14*P3:(7,7)
15*P3:(8,8)
16*P3:(2,9)
17*P3:O

P4:(2,9)
2*P4:(8,8)
3*P4:(7,7)
4*P4:(0,11)
5*P4:(12,1)
6*P4:(9,7)
7*P4:(5,3)
8*P4:(10,7)
9*P4:(10,6)
10*P4:(5,10)
11*P4:(9,6)
12*P4:(12,12)
13*P4:(0,2)
14*P4:(7,6)
15*P4:(8,5)
16*P4:(2,4)
17*P4:O

P5:(5,3)
2*P5:(7,6)
3*P5:(0,11)
4*P5:(9,6)
5*P5:(2,9)
6*P5:(10,7)
7*P5:(8,5)
8*P5:(12,1)
9*P5:(12,12)
10*P5:(8,8)
11*P5:(10,6)
12*P5:(2,4)
13*P5:(9,7)
14*P5:(0,2)
15*P5:(7,7)
16*P5:(5,10)
17*P5:O

P6:(5,10)
2*P6:(7,7)
3*P6:(0,2)
4*P6:(9,7)
5*P6:(2,4)
6*P6:(10,6)
7*P6:(8,8)
8*P6:(12,12)
9*P6:(12,1)
10*P6:(8,5)
11*P6:(10,7)
12*P6:(2,9)
13*P6:(9,6)
14*P6:(0,11)
15*P6:(7,6)
16*P6:(5,3)
17*P6:O

P7:(7,6)
2*P7:(9,6)
3*P7:(10,7)
4*P7:(12,1)
5*P7:(8,8)
6*P7:(2,4)
7*P7:(0,2)
8*P7:(5,10)
9*P7:(5,3)
10*P7:(0,11)
11*P7:(2,9)
12*P7:(8,5)
13*P7:(12,12)
14*P7:(10,6)
15*P7:(9,7)
16*P7:(7,7)
17*P7:O

P8:(7,7)
2*P8:(9,7)
3*P8:(10,6)
4*P8:(12,12)
5*P8:(8,5)
6*P8:(2,9)
7*P8:(0,11)
8*P8:(5,3)
9*P8:(5,10)
10*P8:(0,2)
11*P8:(2,4)
12*P8:(8,8)
13*P8:(12,1)
14*P8:(10,7)
15*P8:(9,6)
16*P8:(7,6)
17*P8:O

P9:(8,5)
2*P9:(0,2)
3*P9:(9,6)
4*P9:(10,6)
5*P9:(5,3)
6*P9:(12,1)
7*P9:(7,7)
8*P9:(2,9)
9*P9:(2,4)
10*P9:(7,6)
11*P9:(12,12)
12*P9:(5,10)
13*P9:(10,7)
14*P9:(9,7)
15*P9:(0,11)
16*P9:(8,8)
17*P9:O

P10:(8,8)
2*P10:(0,11)
3*P10:(9,7)
4*P10:(10,7)
5*P10:(5,10)
6*P10:(12,12)
7*P10:(7,6)
8*P10:(2,4)
9*P10:(2,9)
10*P10:(7,7)
11*P10:(12,1)
12*P10:(5,3)
13*P10:(10,6)
14*P10:(9,6)
15*P10:(0,2)
16*P10:(8,5)
17*P10:O

P11:(9,6)
2*P11:(12,1)
3*P11:(2,4)
4*P11:(5,10)
5*P11:(0,11)
6*P11:(8,5)
7*P11:(10,6)
8*P11:(7,7)
9*P11:(7,6)
10*P11:(10,7)
11*P11:(8,8)
12*P11:(0,2)
13*P11:(5,3)
14*P11:(2,9)
15*P11:(12,12)
16*P11:(9,7)
17*P11:O

P12:(9,7)
2*P12:(12,12)
3*P12:(2,9)
4*P12:(5,3)
5*P12:(0,2)
6*P12:(8,8)
7*P12:(10,7)
8*P12:(7,6)
9*P12:(7,7)
10*P12:(10,6)
11*P12:(8,5)
12*P12:(0,11)
13*P12:(5,10)
14*P12:(2,4)
15*P12:(12,1)
16*P12:(9,6)
17*P12:O

P13:(10,6)
2*P13:(2,9)
3*P13:(5,10)
4*P13:(8,8)
5*P13:(9,6)
6*P13:(7,7)
7*P13:(12,12)
8*P13:(0,11)
9*P13:(0,2)
10*P13:(12,1)
11*P13:(7,6)
12*P13:(9,7)
13*P13:(8,5)
14*P13:(5,3)
15*P13:(2,4)
16*P13:(10,7)
17*P13:O

P14:(10,7)
2*P14:(2,4)
3*P14:(5,3)
4*P14:(8,5)
5*P14:(9,7)
6*P14:(7,6)
7*P14:(12,1)
8*P14:(0,2)
9*P14:(0,11)
10*P14:(12,12)
11*P14:(7,7)
12*P14:(9,6)
13*P14:(8,8)
14*P14:(5,10)
15*P14:(2,9)
16*P14:(10,6)
17*P14:O

P15:(12,1)
2*P15:(5,10)
3*P15:(8,5)
4*P15:(7,7)
5*P15:(10,7)
6*P15:(0,2)
7*P15:(2,9)
8*P15:(9,7)
9*P15:(9,6)
10*P15:(2,4)
11*P15:(0,11)
12*P15:(10,6)
13*P15:(7,6)
14*P15:(8,8)
15*P15:(5,3)
16*P15:(12,12)
17*P15:O

P16:(12,12)
2*P16:(5,3)
3*P16:(8,8)
4*P16:(7,6)
5*P16:(10,6)
6*P16:(0,11)
7*P16:(2,4)
8*P16:(9,6)
9*P16:(9,7)
10*P16:(2,9)
11*P16:(0,2)
12*P16:(10,7)
13*P16:(7,7)
14*P16:(8,5)
15*P16:(5,10)
16*P16:(12,1)
17*P16:O

もう一つ試します。無駄に長くなってきたので、点の位数(Pをn倍した時に無限遠点Oになるもっとも小さな値)だけ表示します。
 F_{71}
 y^{2} = x^{3} - x

有理点の数(=群の位数)は72, 有理点の位数は、2, 3, 4, 9, 12, 18, 36で有理点の数の因数が全て出てきているようです。

F71
d:4
#EC:72

P1:(0,0)
order:2


P2:(1,0)
order:2


P3:(2,19)
order:9


P4:(2,52)
order:9


P5:(3,33)
order:18


P6:(3,38)
order:18


P7:(4,29)
order:9


P8:(4,42)
order:9


P9:(5,7)
order:18


P10:(5,64)
order:18


P11:(9,9)
order:6


P12:(9,62)
order:6


P13:(12,15)
order:36


P14:(12,56)
order:36


P15:(13,14)
order:4


P16:(13,57)
order:4


P17:(14,23)
order:18


P18:(14,48)
order:18


P19:(19,33)
order:3


P20:(19,38)
order:3


P21:(21,9)
order:36


P22:(21,62)
order:36


P23:(23,28)
order:18


P24:(23,43)
order:18


P25:(27,29)
order:36


P26:(27,42)
order:36


P27:(32,17)
order:12


P28:(32,54)
order:12


P29:(33,7)
order:36


P30:(33,64)
order:36


P31:(35,13)
order:18


P32:(35,58)
order:18


P33:(37,8)
order:9


P34:(37,63)
order:9


P35:(40,29)
order:12


P36:(40,42)
order:12


P37:(41,9)
order:36


P38:(41,62)
order:36


P39:(42,8)
order:18


P40:(42,63)
order:18


P41:(43,21)
order:36


P42:(43,50)
order:36


P43:(45,22)
order:36


P44:(45,49)
order:36


P45:(46,34)
order:36


P46:(46,37)
order:36


P47:(47,20)
order:18


P48:(47,51)
order:18


P49:(49,33)
order:18


P50:(49,38)
order:18


P51:(51,16)
order:12


P52:(51,55)
order:12


P53:(53,24)
order:18


P54:(53,47)
order:18


P55:(54,28)
order:36


P56:(54,43)
order:36


P57:(55,31)
order:12


P58:(55,40)
order:12


P59:(56,30)
order:6


P60:(56,41)
order:6


P61:(60,10)
order:4


P62:(60,61)
order:4


P63:(61,2)
order:36


P64:(61,69)
order:36


P65:(63,8)
order:6


P66:(63,63)
order:6


P67:(64,27)
order:36


P68:(64,44)
order:36


P69:(65,28)
order:36


P70:(65,43)
order:36


P71:(70,0)
order:2

f:id:pebble8888:20170909172711p:plain

もう一つ試します。

 F_{13}
 y^{2} = x^{3} + 4

F13
#EC:21

P1:(0,2)
2*P1:(0,11)
3*P1:O
order:3

4*P1:(0,2)

P2:(0,11)
2*P2:(0,2)
3*P2:O
order:3

4*P2:(0,11)

P3:(2,5)
2*P3:(12,9)
3*P3:(8,3)
4*P3:(6,5)
5*P3:(5,8)
6*P3:(7,3)
7*P3:(0,2)
8*P3:(10,9)
9*P3:(11,10)
10*P3:(4,4)
11*P3:(4,9)
12*P3:(11,3)
13*P3:(10,4)
14*P3:(0,11)
15*P3:(7,10)
16*P3:(5,5)
17*P3:(6,8)
18*P3:(8,10)
19*P3:(12,4)
20*P3:(2,8)
21*P3:O
order:21

P4:(2,8)
2*P4:(12,4)
3*P4:(8,10)
4*P4:(6,8)
5*P4:(5,5)
6*P4:(7,10)
7*P4:(0,11)
8*P4:(10,4)
9*P4:(11,3)
10*P4:(4,9)
11*P4:(4,4)
12*P4:(11,10)
13*P4:(10,9)
14*P4:(0,2)
15*P4:(7,3)
16*P4:(5,8)
17*P4:(6,5)
18*P4:(8,3)
19*P4:(12,9)
20*P4:(2,5)
21*P4:O
order:21

P5:(4,4)
2*P5:(2,8)
3*P5:(11,10)
4*P5:(12,4)
5*P5:(10,9)
6*P5:(8,10)
7*P5:(0,2)
8*P5:(6,8)
9*P5:(7,3)
10*P5:(5,5)
11*P5:(5,8)
12*P5:(7,10)
13*P5:(6,5)
14*P5:(0,11)
15*P5:(8,3)
16*P5:(10,4)
17*P5:(12,9)
18*P5:(11,3)
19*P5:(2,5)
20*P5:(4,9)
21*P5:O
order:21

P6:(4,9)
2*P6:(2,5)
3*P6:(11,3)
4*P6:(12,9)
5*P6:(10,4)
6*P6:(8,3)
7*P6:(0,11)
8*P6:(6,5)
9*P6:(7,10)
10*P6:(5,8)
11*P6:(5,5)
12*P6:(7,3)
13*P6:(6,8)
14*P6:(0,2)
15*P6:(8,10)
16*P6:(10,9)
17*P6:(12,4)
18*P6:(11,10)
19*P6:(2,8)
20*P6:(4,4)
21*P6:O
order:21

P7:(5,5)
2*P7:(4,9)
3*P7:(7,3)
4*P7:(2,5)
5*P7:(6,8)
6*P7:(11,3)
7*P7:(0,2)
8*P7:(12,9)
9*P7:(8,10)
10*P7:(10,4)
11*P7:(10,9)
12*P7:(8,3)
13*P7:(12,4)
14*P7:(0,11)
15*P7:(11,10)
16*P7:(6,5)
17*P7:(2,8)
18*P7:(7,10)
19*P7:(4,4)
20*P7:(5,8)
21*P7:O
order:21

P8:(5,8)
2*P8:(4,4)
3*P8:(7,10)
4*P8:(2,8)
5*P8:(6,5)
6*P8:(11,10)
7*P8:(0,11)
8*P8:(12,4)
9*P8:(8,3)
10*P8:(10,9)
11*P8:(10,4)
12*P8:(8,10)
13*P8:(12,9)
14*P8:(0,2)
15*P8:(11,3)
16*P8:(6,8)
17*P8:(2,5)
18*P8:(7,3)
19*P8:(4,9)
20*P8:(5,5)
21*P8:O
order:21

P9:(6,5)
2*P9:(10,9)
3*P9:(11,3)
4*P9:(5,5)
5*P9:(2,8)
6*P9:(8,3)
7*P9:(0,2)
8*P9:(4,9)
9*P9:(7,10)
10*P9:(12,4)
11*P9:(12,9)
12*P9:(7,3)
13*P9:(4,4)
14*P9:(0,11)
15*P9:(8,10)
16*P9:(2,5)
17*P9:(5,8)
18*P9:(11,10)
19*P9:(10,4)
20*P9:(6,8)
21*P9:O
order:21

P10:(6,8)
2*P10:(10,4)
3*P10:(11,10)
4*P10:(5,8)
5*P10:(2,5)
6*P10:(8,10)
7*P10:(0,11)
8*P10:(4,4)
9*P10:(7,3)
10*P10:(12,9)
11*P10:(12,4)
12*P10:(7,10)
13*P10:(4,9)
14*P10:(0,2)
15*P10:(8,3)
16*P10:(2,8)
17*P10:(5,5)
18*P10:(11,3)
19*P10:(10,9)
20*P10:(6,5)
21*P10:O
order:21

P11:(7,3)
2*P11:(11,3)
3*P11:(8,10)
4*P11:(8,3)
5*P11:(11,10)
6*P11:(7,10)
7*P11:O
order:7

8*P11:(7,3)

P12:(7,10)
2*P12:(11,10)
3*P12:(8,3)
4*P12:(8,10)
5*P12:(11,3)
6*P12:(7,3)
7*P12:O
order:7

8*P12:(7,10)

P13:(8,3)
2*P13:(7,3)
3*P13:(11,10)
4*P13:(11,3)
5*P13:(7,10)
6*P13:(8,10)
7*P13:O
order:7

8*P13:(8,3)

P14:(8,10)
2*P14:(7,10)
3*P14:(11,3)
4*P14:(11,10)
5*P14:(7,3)
6*P14:(8,3)
7*P14:O
order:7

8*P14:(8,10)

P15:(10,4)
2*P15:(5,8)
3*P15:(8,10)
4*P15:(4,4)
5*P15:(12,9)
6*P15:(7,10)
7*P15:(0,2)
8*P15:(2,8)
9*P15:(11,3)
10*P15:(6,5)
11*P15:(6,8)
12*P15:(11,10)
13*P15:(2,5)
14*P15:(0,11)
15*P15:(7,3)
16*P15:(12,4)
17*P15:(4,9)
18*P15:(8,3)
19*P15:(5,5)
20*P15:(10,9)
21*P15:O
order:21

P16:(10,9)
2*P16:(5,5)
3*P16:(8,3)
4*P16:(4,9)
5*P16:(12,4)
6*P16:(7,3)
7*P16:(0,11)
8*P16:(2,5)
9*P16:(11,10)
10*P16:(6,8)
11*P16:(6,5)
12*P16:(11,3)
13*P16:(2,8)
14*P16:(0,2)
15*P16:(7,10)
16*P16:(12,9)
17*P16:(4,4)
18*P16:(8,10)
19*P16:(5,8)
20*P16:(10,4)
21*P16:O
order:21

P17:(11,3)
2*P17:(8,3)
3*P17:(7,10)
4*P17:(7,3)
5*P17:(8,10)
6*P17:(11,10)
7*P17:O
order:7

8*P17:(11,3)

P18:(11,10)
2*P18:(8,10)
3*P18:(7,3)
4*P18:(7,10)
5*P18:(8,3)
6*P18:(11,3)
7*P18:O
order:7

8*P18:(11,10)

P19:(12,4)
2*P19:(6,8)
3*P19:(7,10)
4*P19:(10,4)
5*P19:(4,9)
6*P19:(11,10)
7*P19:(0,2)
8*P19:(5,8)
9*P19:(8,3)
10*P19:(2,5)
11*P19:(2,8)
12*P19:(8,10)
13*P19:(5,5)
14*P19:(0,11)
15*P19:(11,3)
16*P19:(4,4)
17*P19:(10,9)
18*P19:(7,3)
19*P19:(6,5)
20*P19:(12,9)
21*P19:O
order:21

P20:(12,9)
2*P20:(6,5)
3*P20:(7,3)
4*P20:(10,9)
5*P20:(4,4)
6*P20:(11,3)
7*P20:(0,11)
8*P20:(5,5)
9*P20:(8,10)
10*P20:(2,8)
11*P20:(2,5)
12*P20:(8,3)
13*P20:(5,8)
14*P20:(0,2)
15*P20:(11,10)
16*P20:(4,9)
17*P20:(10,4)
18*P20:(7,10)
19*P20:(6,8)
20*P20:(12,4)
21*P20:O
order:21

f:id:pebble8888:20180817154045p:plain