Используется ли кофактор для поиска базовой точки только из соображений производительности?

Для криптографии на эллиптических кривых процедура поиска базовой точки, которая генерирует подгруппу с порядком $n$ является:

1. Рассчитать заказ $N$ эллиптической кривой (с использованием Schoof's)
2. выберите $n$. $n$ должно быть простым числом и делителем $N$
3. Вычислить кофактор $h = \frac{N}{n}$
4. Выбрать случайную точку $P$ на кривой
5. Вычислить $G = hP$
6. Если $G$ равно 0, то вернитесь к шагу 4. В противном случае вы нашли генератор с порядком $n$ и кофактор $ч$

Источник

Является ли целью кофактора здесь исключительно повышение эффективности поиска большой подгруппы?

Я полагаю, что если бы вы не использовали кофактор и вместо этого попытались вычислить методом грубой силы, является ли случайная точка, $P$, был генератором для подгруппы размера $n$ вам придется сделать $n$ итераций, что было бы невозможно на современных компьютерах. Но я хочу подтвердить.

Редактировать: Мой последний абзац неверен, потому что мы можем использовать повторное возведение в квадрат для вычисления $G = nP$

Это эмпирический результат, дополняющий ответ Пончо;

Возьмем Curve25519, у которого есть кофактор $8$ как заказ $n$ групповых факторов как

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

• $ч = 8$
• $q = n/8$

Мы используем SageMath и SageMath случайный_элемент функция, в которой он может вернуть элемент идентификации $\mathcal{O}$ кривой (шанс получить незначителен) , на Curve25519 $\mathcal{O} = (0:1:0)$ на форме Вейерштрасса.

время импорта

def randomBasePointByCofactor(E,identity,cofactor):
    
    с = время.время()
    си = 0
    n = E.порядок ()
    для я в диапазоне (1,10000):
        P = E.random_element()
        если кофактор*P != тождество:
            ци = ци +1
    е = время.время()
    print("время, прошедшее с randomBasePointByCofactor", e-s)
    возврат (ки)
        
def randomBasePointByOrder(E,identity,cofactor):
    
    с = время.время()
    си = 0
    n = целое число (E.order () / кофактор)
    для я в диапазоне (1,10000):
        P = E.random_element()
        если n*P == тождество:
            ци = ци +1

    е = время.время()
    print("время, прошедшее с randomBasePointByOrder", e-s)
    возврат (ки)    

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

ИП = Е((0,1,0))
Граница = 10000

print(" количество найденных генераторов =" , randomBasePointByCofactor(E,IP,8), "/", Bound)

print(" количество найденных генераторов =", randomBasePointByOrder(E,IP,8),"/", Bound)

Примерный результат

время, прошедшее с randomBasePointByCofactor 1,9164307117462158
 количество найденных генераторов = 9999/10000
время, прошедшее с randomBasePointByOrder 64,77565383911133
 количество найденных генераторов = 1267/10000

Следовательно

• метод кофактора быстрее в ~32 раза быстрее в экспериментах.

  Мы можем объяснить это простыми словами, как; $8$ требует 4 удвоения и 1 сложения, тогда как $n$ требуется 251 удвоение и 125 сложений с наивным двойной алгоритм. Это дает примерно в 75 раз больше вычислений, если мы предположим, что удвоение и сложения имеют ту же скорость, которой они не являются.

• метод кофакторов производит больше генераторов, чем метод порядка, поскольку $1/8$ случайных элементов из $8\cdotq$ попадает в большой прайм $q$ Кривая25519.

Поэтому кофакторный метод предпочтительнее.