Уведомления

Группа в Telegram: @pythonsu

#1 Май 23, 2016 14:59:40

PaRUS
Зарегистрирован: 2016-05-23
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Оптимизация времени работы

Всем здравствуйте! В процессе реализации алгоритма электронной подписи по ГОСТ 34.10-2012 возникла необходимость умножать точки эллиптической кривой на целые числа, иными словами складывать их друг с другом определенное количество раз. Проблема в том, что целые числа в данном алгоритме близки к 2^256 и 2^512. По сути имеется цикл while, который выполняется немыслимое количество раз, близкое как раз к 2^256. Я понимаю, что за разумные промежутки времени этот цикл не закончится.

def MultiPointEK(num, point, a, mod):
	x1 = point[0]
	y1 = point[1]
	newpoint = TwicePointEK(point, a, mod)
	counter = 2
	[b]while counter < num:
		newpoint = AdditivePointsEK(point, newpoint, mod, a)
		counter += 1[/b]
	finpoint = [newpoint[0], newpoint[1]]
	return finpoint

Это функция умножения точки на число, вот функция сложения точек, которая вызывается здесь.

def AdditivePointsEK(point1, point2, mod, a):
	if point1[0] == point2[0] and point1[1] == point2[1]:
		x = point1[0]
		y = point1[1]
		p = [x, y]
		finpoint = TwicePointEK(p, a, mod)
	else:
		x1 = point1[0]
		x2 = point2[0]
		y1 = point1[1]
		y2 = point2[1]
		promezh = (x2 - x1) % mod
		promezh = evqlid(mod, promezh)
		h = ((y2 - y1) * promezh) % mod
		x3 = (h**2 - x1 - x2) % mod
		while x3 < 0:
			x3 += mod
		y3 = (h * (x1 - x3) - y1) % mod
		while y3 < 0:
			y3 += mod
		finpoint = [x3, y3]
	return finpoint

Так вот интересуют какие-либо методы оптимизации, при которых этот цикл будет выполняться быстро. Или может, возможно, как-то перестроить код и обойтись без цикла. Мне советовали написать эти части программы на С и уже подключить как модуль. Но времени очень мало, я посмотрел простейший пример такого модуля, и там очень много непонятного для меня. Может кто-то что-то посоветовать? Я знаю, что можно реализовать на классах, но тоже, к сожалению, с классами никогда не работал и за неделю не успею. Заранее спасибо!

Отредактировано PaRUS (Май 23, 2016 15:00:09)

Офлайн

#2 Май 23, 2016 15:17:35

Shaman
Зарегистрирован: 2013-03-15
Сообщения: 1369
Репутация: +  88  -
Профиль   Отправить e-mail  

Оптимизация времени работы

Офлайн

#3 Май 23, 2016 18:18:39

PaRUS
Зарегистрирован: 2016-05-23
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Оптимизация времени работы

Shaman
https://habrahabr.ru/company/virgilsecurity/blog/301048/

Да, спасибо, видел. Там на классах реализовано, я, если честно, не особо с этим. Точнее код то я понимаю, но там где описана функция, которая мне нужна, все равно цикл вызывается очень много раз. И я не вижу за счет чего он будет работать быстро. Я хотел спросить, но возможности комментировать у меня нет.

Офлайн

#4 Май 23, 2016 18:46:24

Shaman
Зарегистрирован: 2013-03-15
Сообщения: 1369
Репутация: +  88  -
Профиль   Отправить e-mail  

Оптимизация времени работы

Самый простой способ ускориться - запустить на pypy.

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version