Что известно о вычислительной сложности факторизации целых чисел в полях общего числа? Более конкретно: Над целыми числами мы представляем целые числа через их двоичные расширения. Что такое аналогичные представления целых чисел в полях общего числа? Известно ли, что первичность над числовыми...
Напомним число простых чисел - функция подсчета простых чисел . Посредством «PRIMES in P» вычисление находится в #P. Проблема № P-завершена? Или, может быть, есть сложная причина полагать, что эта проблема не является # P-полной? π(n)π(n)\pi(n)≤n≤n\le nπ ( n )π(n)π(n)\pi(n) PS Я понимаю, что это...
Кто-нибудь может мне помочь со следующей проблемой? Я хочу найти некоторые значения a i , b jai,bja_i,b_j (mod NNN ), где i = 1 , 2 , … , K , j = 1 , 2 , … , Ki=1,2,…,K,j=1,2,…,Ki=1,2,…,K, j=1,2,…,K (например, К = 6K=6K=6 ), учитывая список значений К 2K2K^2 которые соответствуют различиям a i - b...
Каковы известные эффективные алгоритмы вычисления определителя целочисленной матрицы с коэффициентами в , кольца вычетов по модулю m . Число m может быть не простым, а составным (поэтому вычисления выполняются в кольце, а не в поле).ZмZм\mathbb{Z}_mммmммm Насколько я знаю (читайте ниже),...
Читая блог Дика Липтона, я наткнулся на следующий факт в конце его поста о факторе Борна : Если для каждого существует отношение вида где , и каждый из , и является по длине в битах, тогда факторинг имеет полином размерные схемы.( 2 n ) ! = m - 1 ∑ k = 0 a k b c k k m = p o l y ( n...
Из комментариев на один из моих вопросов о MathOverflow у меня возникает ощущение, что вопрос о GCD в vs. похож на вопрос о целочисленной факторизации в vs. .N CNС\mathsf{NC}пп\mathsf{P}пп\mathsf{P}Н ПNп\mathsf{NP} Существует ли что-то вроде алгоритма «квант » для GCD, поскольку существует алгоритм...
В чем сложность определения, содержит ли интервал натуральных чисел простое число? Вариант решета Эратосфена дает алгоритм, где L является длина интервала и ~ Шкуры поли-логарифмические факторы в исходной точке интервала; мы можем сделать лучше (с точки зрения L только)?O~(L)O~(L)\tilde...
Функция Мебиуса определяется как μ ( 1 ) = 1 , μ ( n ) = 0, если n имеет квадратный простой множитель, и μ ( p 1 … p k ) = ( - 1 ) k, если все простые числа p 1 , … , p k разные. Можно ли вычислить μ ( n )μ(n)μ(n)\mu(n)μ(1)=1μ(1)=1\mu(1)=1μ(n)=0μ(n)=0\mu(n)=0nnnμ(p1…pk)=(−1)kμ(p1…pk)=(−1)k\mu(p_1...
Я пытаюсь понять, к какому классу сложности относится следующая проблема: Экспонирующая полиномиальная корневая проблема (EPRP) Пусть - многочлен с deg ( p ) ≥ 0 с коэффициентами, взятыми из конечного поля G F ( q ), где q - простое число, а r - примитивный корень для этого поля. Определите...
Шон Андерсон опубликовал немного вертел хаки , содержащие алгоритм Эрика Коула , чтобы найти А.Н. -разрядного целочисленного в операций с умножения и поиска.N v O ( lg ( N ) )⌈log2v⌉⌈log2v⌉\lceil\log_2 v \rceilNNNvvvO(lg(N))O(lg(N))O(\lg(N)) Алгоритм опирается на «магическое» число из...
Есть ли какое-нибудь известное вычислимое трансцендентное число такое, что его NnnЭта цифра вычисляется за полиномиальное время, но не в O ( n
Данный взаимный a,ba,ba, bМожете ли вы быстро вычислить minx,y>0|ax−by|minx,y>0|ax−by| \min_{x, y > 0} |a^x - b^y| Вот x,yx,yx, yцелые числа. Очевидно, принимаяx=y=0x=y=0x = y = 0дает неинтересный ответ; в общем, насколько близки эти силы? Кроме того, как мы можем быстро вычислить...