Вопросы с тегом «nt.number-theory»

11
Используя последовательность де Брюйна, чтобы найти целого числа

Шон Андерсон опубликовал немного вертел хаки , содержащие алгоритм Эрика Коула , чтобы найти А.Н. -разрядного целочисленного в операций с умножения и поиска.N v O ( lg ( N ) )⌈log2v⌉⌈log2⁡v⌉\lceil\log_2 v \rceilNNNvvvO(lg(N))O(lg⁡(N))O(\lg(N)) Алгоритм опирается на «магическое» число из...

11
Может ли Мерлин убедить Артура в определенной сумме?

Мерлин, имеющий неограниченные вычислительные ресурсы, хочет убедить Артура, что для с и Простое вычисление этой суммы (модульное возведение в степень и сложение) занимает время с умножением на основе БПФ. * Но Артур может выполнять только операций.m|∑p≤N, p primepkm|∑p≤N, p primepkm|\sum_{p\le N,\...

11
«Переполнение» в расширенном евклидовом алгоритме

Извините, если я ошибаюсь с местом, чтобы задать вопрос (может быть, я должен пойти на stackoverflow.com/mathoverflow.net?). Интересно, есть ли доказательство того, что при оценке расширенного евклидова алгоритма коэффициенты Безу ( т. Е. S и t в тождестве как + bt = gcd ( a , b )) не будут...

11
Эффективно получать биты N! ?

Учитывая и M , возможно ли получить M -й бит (или цифру любого небольшого основания) из N ! во времени / пространстве O ( p ( l n ( N ) , l n ( M ) ) ) , где p ( x , y ) - некоторая полиномиальная функция от x и y ?NNNMMMMMMN!N!N!O ( p ( l n ( N) , л н ( М) ) )O(p(ln(N),ln(M)))O( p( ln(N), ln(M) )...

10
Сокращение факторинга основных продуктов до факторизации целочисленных продуктов (в среднем случае)

Мой вопрос касается эквивалентности безопасности различных односторонних функций-кандидатов, которые могут быть построены на основе сложности факторинга. Предполагая проблему ФАКТОРИНГ: [Дано для случайных простых чисел , найти , ]P , Q < 2 n P QN=PQN=PQN = PQP,Q<2nP,Q<2nP, Q < 2^nPPPQQQ...

10
Сравнивая два произведения списков целых чисел?

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

10
Нумерация подмножеств

Исправить . Для любого достаточно большого мы хотели бы пометить все подмножества размера точно натуральными числами из . Нам бы хотелось, чтобы эта маркировка удовлетворяла следующему свойству: есть множество целых чисел, stk≥5k≥5k\ge5nnn{1..n}{1..n}\{1..n\}n/kn/kn/k{1...T}{1...T}\{1...T\}SSS Если...

9
Алгоритм вычисления расстояния между степенями

Данный взаимный 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дает неинтересный ответ; в общем, насколько близки эти силы? Кроме того, как мы можем быстро вычислить...