Có phải việc sử dụng đồng sáng lập để tìm điểm cơ sở chỉ vì lý do hiệu suất không?

Đối với mật mã đường cong elip, quy trình tìm điểm cơ sở tạo ra nhóm con có thứ tự $n$ Là:

1. Tính thứ tự $N$ của đường cong elip (sử dụng Schoof's)
2. Chọn $n$. $n$ phải là số nguyên tố và là ước của $N$
3. Đồng sáng lập điện toán $h = \frac{N}{n}$
4. Chọn một điểm ngẫu nhiên $P$ trên đường cong
5. tính toán $G = hP$
6. Nếu $G$ là 0, sau đó quay lại bước 4. Nếu không, bạn đã tìm thấy trình tạo có thứ tự $n$ và đồng sáng lập $h$

Nguồn

Có phải mục đích của đồng sáng lập ở đây chỉ để tăng hiệu quả trong việc tìm kiếm một nhóm phụ lớn?

Tôi cho rằng nếu bạn không sử dụng đồng yếu tố và thay vào đó cố gắng tính toán một cách thô bạo xem điểm ngẫu nhiên, $P$, là một trình tạo cho một nhóm con có kích thước $n$ bạn sẽ phải làm $n$ lặp đi lặp lại, điều không thể thực hiện được trên các máy tính hiện đại. Nhưng, tôi muốn khẳng định.

Chỉnh sửa: Đoạn cuối cùng của tôi là sai b/c chúng ta có thể sử dụng bình phương lặp đi lặp lại để tính toán $G = nP$

Đây là một kết quả thực nghiệm để bổ sung cho câu trả lời của Poncho;

Lấy Curve25519 có đồng sáng lập $8$ như đơn đặt hàng $n$ của các yếu tố nhóm như

$\small{n = 2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989}$

• $h = 8 $
• $q = n/8$

Chúng tôi sử dụng SageMath và SageMath random_element chức năng trong đó nó có thể trả lại phần tử nhận dạng $\mathcal{O}$ của đường cong (cơ hội nhận được nó là không đáng kể), trên Curve25519 $\mathcal{O} = (0:1:0)$ trên mẫu Weierstrass.

thời gian nhập khẩu

def RandomBasePointByCofactor(E,identity,cofactor):
    
    s = thời gian.thời gian()
    ci = 0
    n = E.order()
    cho tôi trong phạm vi (1,10000):
        P = E.random_element()
        nếu đồng sáng lập*P != danh tính:
            ci = ci +1
    e = thời gian.thời gian()
    print("thời gian trôi qua trên RandomBasePointByCofactor", e-s)
    trả lại (ci)
        
def RandomBasePointByOrder(E,identity,cofactor):
    
    s = thời gian.thời gian()
    ci = 0
    n = Số nguyên(E.order() / cofactor)
    cho tôi trong phạm vi (1,10000):
        P = E.random_element()
        nếu n*P == danh tính:
            ci = ci +1

    e = thời gian.thời gian()
    print("thời gian trôi qua trên RandomBasePointByOrder", e-s)
    trả lại (ci)    

p = 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
K = GF(p)
A = K(0x76d06)
B = K(0x01)
E = EllipticCurve(K, ((3 - A^2)/(3 * B^2), (2 * A^3 - 9 * A)/(27 * B^3)))

IP = E((0,1,0))
Giới hạn = 10000

print(" số lượng trình tạo được tìm thấy = ", randomBasePointByCofactor(E,IP,8), "/", Giới hạn)

print("số lượng trình tạo được tìm thấy =",randomBasePointByOrder(E,IP,8),"/", Giới hạn)

Một kết quả mẫu là

thời gian đã trôi qua trên RandomBasePointByCofactor 1.9164307117462158
 số lượng máy phát điện được tìm thấy = 9999/10000
thời gian đã trôi qua trên RandomBasePointByOrder 64.77565383911133
 số lượng máy phát điện được tìm thấy = 1267/10000

Vì vậy

• phương pháp đồng sáng lập nhanh hơn ~32 lần trong các thử nghiệm.

  Chúng ta có thể giải thích điều này một cách đơn giản như; $8$ yêu cầu 4 lần nhân đôi và 1 lần bổ sung, trong khi $n$ yêu cầu nhân đôi 251 và bổ sung 125 với ngây thơ thuật toán nhân đôi. Điều này cho phép tính toán nhiều hơn ~75 lần nếu chúng ta giả sử nhân đôi và bổ sung có cùng tốc độ mà chúng không có.

• phương thức cofactor tạo ra nhiều trình tạo hơn so với phương thức đặt hàng vì $1/8$ của các yếu tố ngẫu nhiên từ $8\cdot q$ rơi vào số nguyên tố lớn $q$ của Curve25519.

Do đó, phương pháp đồng sáng lập là thích hợp hơn.