Я могу уменьшить вычислительную сложность этого?

Смотрите на http://modular.fas.harvard.edu/ent/ent_py. Функция sqrtmod делает задание, если Вы устанавливаете =-1 и p = n.

Маленькая суть, которую Вы упустили, - то, что время выполнения Вашего улучшенного алгоритма находится все еще в порядке квадратного корня n. Поскольку долго у Вас есть только маленькие начала n (скажем, меньше, чем 2^64), это в порядке, и необходимо, вероятно, предпочесть реализацию более сложной.

Если главный n становится больше, Вам, возможно, придется переключиться на алгоритм с помощью определенной теории чисел. К моему знанию Ваша проблема может быть решена только с вероятностным алгоритмом в хронологическом журнале (n) ^3. Если я помню правильно, предполагая, что Riemann гипотеза содержит (который большинство людей делает), можно показать, что время выполнения следующего алгоритма (в рубине - извините, я не знаю, Python) журнал (журнал (n)) *log (n) ^3:

class Integer
  # calculate b to the power of e modulo self
  def power(b, e)
    raise 'power only defined for integer base' unless b.is_a? Integer
    raise 'power only defined for integer exponent' unless e.is_a? Integer
    raise 'power is implemented only for positive exponent' if e < 0
    return 1 if e.zero?
    x = power(b, e>>1)
    x *= x
    (e & 1).zero? ? x % self : (x*b) % self
  end
  # Fermat test (probabilistic prime number test)
  def prime?(b = 2)
    raise "base must be at least 2 in prime?" if b < 2
    raise "base must be an integer in prime?" unless b.is_a? Integer
    power(b, self >> 1) == 1
  end
  # find square root of -1 modulo prime
  def sqrt_of_minus_one
    return 1 if self == 2
    return false if (self & 3) != 1
    raise 'sqrt_of_minus_one works only for primes' unless prime?
    # now just try all numbers (each succeeds with probability 1/2)
    2.upto(self) do |b|
      e = self >> 1
      e >>= 1 while (e & 1).zero?
      x = power(b, e)
      next if [1, self-1].include? x
      loop do
        y = (x*x) % self
        return x if y == self-1
        raise 'sqrt_of_minus_one works only for primes' if y == 1
        x = y
      end
    end
  end
end

# find a prime
p = loop do
      x = rand(1<<512)
      next if (x & 3) != 1
      break x if x.prime?
    end

puts "%x" % p
puts "%x" % p.sqrt_of_minus_one

Медленная часть теперь находит начало (который берет приблизительно журнал (n) ^4 целочисленная операция); нахождение квадратного корня-1 берет для 512-разрядных начал еще меньше, чем секунда.

Игнорируя алгоритм на мгновение (да, я знаю, плохая идея), время выполнения этого может быть уменьшено чрезвычайно только путем переключения от while кому: for.

for a in range(1, n / 2 + 1)

(Надежда это не имеет ошибки диапазона. Я являюсь склонным для создания их.)

Другая вещь, которую я попробовал бы, состоит в том, чтобы посмотреть, если ширина шага может быть увеличена.

Рассмотрите предварительные вычисления результатов и хранение их в файле. В наше время много платформ имеют огромную емкость диска. Затем получение результата будет O (1) операция.

(Построение на ответе Adam.) Смотрят на страницу Wikipedia на квадратичной взаимности:

x^2 ≡ −1 (модификация p) разрешим если и только если p ≡ 1 (модификация 4).

Затем можно избежать поиска корня точно для тех нечетный главный n's, которые не являются конгруэнтными с 1 4 по модулю:

def table(n):
    if n == 2: return 1
    if n%4 != 1: return None   # or raise exception
    ...

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

Для Вас действительно ли возможно кэшировать результаты?

При вычислении большого n, Вам дают результаты для более низкого n's почти бесплатно.

Редактирование 2: Удивительно, сокращение силы обработка на квадрат уменьшает время много, по крайней мере, на моей установке Python2.5. (Я удивлен, потому что я думал, что интерпретатор наверху брал большую часть времени, и это не уменьшает количество операций во внутреннем цикле.) Уменьшает время с 0,572 с до 0,146 с для таблицы (1234577).

 def table(n):
     n1 = n - 1
     square = 0
     for delta in xrange(1, n, 2):
         square += delta
         if n <= square: square -= n
         if square == n1: return delta // 2 + 1

strager отправил ту же идею, но я думаю менее плотно кодированный. Снова, ответ кувшина является лучшим.

Исходный ответ: Другое тривиальное кодирование настраивает сверху Konrad Rudolph:

def table(n):
    n1 = n - 1
    for a in xrange(1, n // 2 + 1):
          if (a*a) % n == n1: return a

Ускоряет его в известной мере на моем ноутбуке. (Приблизительно 25% для таблицы (1234577).)

Править: Я не заметил тега python3.0; но основное изменение поднимало часть вычисления из цикла, не использования xrange. (Академический с тех пор существует лучший алгоритм.)

Одна вещь, которую Вы делаете, повторяет вычисление-a*a много раз.

Составьте таблицу значений однажды и затем ищите в основном цикле.

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

Я прошел и зафиксировал версию Гарварда, чтобы заставить его работать с python 3. http://modular.fas.harvard.edu/ent/ent_py

Я внес некоторые небольшие изменения для создания результатов точно тем же как функция OP. Существует два возможных ответа, и я вынудил это дать меньший ответ.

import timeit

def table(n):

    if n == 2: return 1
    if n%4 != 1: return

    a1=n-1

    def inversemod(a, p):
        x, y = xgcd(a, p)
        return x%p

    def xgcd(a, b):
        x_sign = 1
        if a < 0: a = -a; x_sign = -1
        x = 1; y = 0; r = 0; s = 1
        while b != 0:
            (c, q) = (a%b, a//b)
            (a, b, r, s, x, y) = (b, c, x-q*r, y-q*s, r, s)
        return (x*x_sign, y)

    def mul(x, y):      
        return ((x[0]*y[0]+a1*y[1]*x[1])%n,(x[0]*y[1]+x[1]*y[0])%n)

    def pow(x, nn):      
        ans = (1,0)
        xpow = x
        while nn != 0:
           if nn%2 != 0:
               ans = mul(ans, xpow)
           xpow = mul(xpow, xpow)
           nn >>= 1
        return ans

    for z in range(2,n) :
        u, v = pow((1,z), a1//2)
        if v != 0:
            vinv = inversemod(v, n)
            if (vinv*vinv)%n == a1:
                vinv %= n
                if vinv <= n//2:
                    return vinv
                else:
                    return n-vinv


tt=0
pri = [ 5,13,17,29,37,41,53,61,73,89,97,1234577,5915587277,3267000013,3628273133,2860486313,5463458053,3367900313 ]
for x in pri:
    t=timeit.Timer('q=table('+str(x)+')','from __main__ import table')
    tt +=t.timeit(number=100)
    print("table(",x,")=",table(x))

print('total time=',tt/100)

Эта версия берет приблизительно 3 мс для пробежки тестовых сценариев выше.

Для сравнения с помощью простого числа 1234577
OP Edit2 745 мс
Принятый ответ 522 мс
Вышеупомянутая функция 0,2 мс