Python-сообщество

Криптографияеский метод шаг карлика - шаг великана, реализованный на питоне с модулем порядка 10 миллионов работает почти минуту, хотя по идее должен секунду а то и меньше.
Код правильный, полного перебора обоих списков не производится.

def fastpower(base, exponent, mod=1):
  res = 1
  while(exponent > 0):
    if exponent % 2 == 0:
      exponent /= 2
      base = mod > 1 and (base*base)%mod or base*base
    else:
      exponent-=1
      res = mod > 1 and (res*base)%mod or res*base
  return mod > 1 and res%mod or res

# searching X in A^X mod P = Y
def steps(a,p,y):
    
    k = int (math.sqrt(p))
    m = k + 2

    child = [y%p,(y*a)%p]
    for i in range (2, m):
        t = fastpower(a,i)
        t *= y
        t %= p
        child.append (int(t))
    child.sort()

    giant = []
    for i in range (1, k + 1):
        giant.append (int(fastpower(a,i*m,p)))
    giant.sort()
    
    c,g = 0,0
    result = []
    while True:
        if child[c] is giant[g]:
            x = (c+1) * m - (g+1)
            result.append(x)
            c += 1
            g += 1            
        elif child[c] < giant[g]:
            c += 1
        elif child[c] > giant[g]:
            g += 1
            
        if c >= len(child)-1:
            c = len(child)-1
            for gp in range(g,len(giant)):
                if child[c] is giant[gp]:
                    x = (c+1) * m - (gp+1)
                    result.append(x)
            return result
        
        if g >= len(giant)-1:
            g = len(giant)-1
            for cp in range(c,len(child)):
                if child[cp] is giant[g]:
                    x = (cp+1) * m - (g+1)
                    result.append(x)
            return result
        
    return result

Отредактировано (Окт. 16, 2010 13:55:41)

вместо range используй xrange!
и заюзай psyco

Спасибо.
Тогда такой вопрос - а есть pysco для python 2.7 ?
Или можно на комп два питона поставить?

А вы уверены, что ваша fastpower будет быстрее стандартного pow?

Андрей Светлов
А вы уверены, что ваша fastpower будет быстрее стандартного pow?

а может ТС воспользуется модулем corepy? Он позволяет включать ассемблерный код в питонерный скрипт

guranvir, не советуйте лишнего. Ходить нужно ногами, а кушать - руками.

o7412369815963, сами посмотрите - возведение в степень и деление по модулю. Не верите - сравните. Только fastpower неправильно работает на некоторых данных :)

o7412369815963
делает что-то другое…?

Eliont

o7412369815963
делает что-то другое…?

По словам нашего криптографа при больших числах она должна быть быстрее + вычисления сразу по модулю. По-модулю - это, собственно, её основное назначение.

Отредактировано (Окт. 18, 2010 09:24:56)

Ваш криптограф смотрел на реализацию int_pow/long_pow (intobject.c и longobject.c соответственно)?
Вы вдвоем обратили внимание на тот факт, что pow принимает до трех аргументов, при этом третий - как раз модуль, по которому нужно делить?

int_pow несколько похожа на вашу fastpower.

Отредактировано (Окт. 18, 2010 19:16:32)