Реализации алгоритмов/P-метод Полларда дискретного логарифмирования: различия между версиями
Содержимое удалено Содержимое добавлено
м Ivan Shmakov переименовал страницу Программные реализации p-метода Полларда дискретного логарифмирования в [[Реализации алгоритмов/P-метод… |
Использован {{BookCat}}; пробелы; →К переименованию: снят шаблон после переименования. |
||
Строка 1:
== Python ==
=== Модифицированный интерфейс mod ===
Это делать не нужно, но многие формулы после этого выглядят более естественно
<source lang="Python">
def mod(a ,b):
'''
Строка 12 ⟶ 10 :
'''
return a % b
</source>
=== [[w:Расширенный алгоритм Евклида|Расширенный алгоритм Евклида]] ===
<source lang="Python">
## ExtendedGCD
# *********************************************************
def ExtendedGCD(a, b):
'''
Строка 28 ⟶ 26 :
d, x, y = d1, y1, x1 - (a/b)*y1
return d, x, y
▲</source>
=== [[w:Функция Эйлера|Функция Эйлера]] ===
<source lang="Python">
## EulerPhi
# *********************************************************
Строка 40 ⟶ 36 :
'''
Функция Эйлера
varphi(n), где n — натуральное число,
равна количеству натуральных чисел,
не больших n и взаимно простых с ним.
'''
res = 1
Строка 67 ⟶ 63 :
# но число раз = 1
return n * res
</source>
=== <math>\rho</math>-метод Полларда ===
<source lang="Python">
## SOLVE
# *********************************************************
def solve(g,a,p):
# g**x = a mod p
n = EulerPhi(p)
'''
использование Функции Эйлера дает возможность
работать не только для простых p
'''
a1 = 0
a2 = 0
b1 = 0
b2 = 0
Строка 91 ⟶ 87 :
x1 = 1
x2 = 1
if(a == g):
return (True , 1)
start = True
while(x1 != x2 or start):
start = False
'''
Поиск совпадающих xi и x2i
использован алгоритм
похожий на этот
Строка 110 ⟶ 106 :
'''
xi ← f(xi-1),
ai ← g(xi-1,ai-1),
bi ← h(xi-1,bi-1)
'''
if(x1 < p/3):
x1 = mod(a * x1, p)
a1 = a1
b1 = mod(b1 + 1, p)
if( x1 >= p/3 and x1 < 2*p/3):
x1 = mod(x1 * x1, p)
a1 = mod(2 * a1, p)
b1 = mod(2 * b1, p)
if(x1 >= 2*p/3):
x1 = mod(g * x1, p)
a1 = mod(a1 + 1, p)
b1 = b1
for i in xrange(2):
'''
x2i ← f(f(x2i-2)),
a2i ← g(f(x2i-2),g(x2i-2,a2i-2)),
b2i ← h(f(x2i-2),h(x2i-2,b2i-2))
'''
if(x2 < p/3):
x2 = mod(a * x2, p)
a2 = a2
b2 = mod(b2 + 1, p)
if( x2 >= p/3 and x2 < 2*p/3):
x2 = mod(x2 * x2, p)
a2 = mod(2 * a2, p)
b2 = mod(2 * b2, p)
if(x2 >= 2*p/3):
x2 = mod(g * x2, p)
Строка 157 ⟶ 153 :
u = mod(a1 - a2, n)
v = mod(b2 - b1, n)
if( mod(v , n) == 0 ):
return (False, None)
'''
В питоне можно возвращать
не одно значение,
а несколько
'''
d, nu, mu = ExtendedGCD(v , n)
'''
nu = v^(-1) mod n
'''
Строка 175 ⟶ 171 :
'''
Это наименее эффективная реализация
алгоритма Полларда,
(в таком виде предложена самим Поллардом)
g^u == a^v mod p
g^(u*nu) = a^(v*nu) = a ^(d - n*nu) = a^(d) = g(x*d) mod p
xd = u * nu + w * n
далее использован перебор,
правда значительно меньшего размера
чем в premutive_log
Проблема в том, что нужно правильно подобрать w
'''
Строка 195 ⟶ 191 :
return (True, x)
i += 1
return (False, x)
</source>
=== Наивный Алгоритм ===
<source lang="Python">
## PREMUTIVE_LOG
# *********************************************************
Строка 216 ⟶ 212 :
x += 1
return None
</source>
Строка 222 ⟶ 218 :
=== Проверка ===
<source lang="Python">
## TEST
# *********************************************************
Строка 236 ⟶ 232 :
</source>
{{BookCat}}
| |||