Вопросы с тегом «primes»

39
Известны ли проблемы PRIMES, FACTORING как P-hard?

Пусть PRIMES (иначе тестирование на примитивность ) будет проблемой: Учитывая натуральное число , является простое число?NNnNNn Пусть FACTORING будет проблемой: Учитывая натуральные числа , с , имеет ли фактор с ?NNnммm1 ≤ m ≤ n1≤м≤N1 \leq m \leq nNNnddd1 < д< м1<d<м1 < d < m Известно...

25
Нахождение простого больше заданной границы

Является ли детерминированный алгоритм за полиномиальное время известным для следующей задачи: Ввод: натуральное число (в двоичной кодировке)Nnn Выход: простое число .р > нp>np > n (Согласно списку открытых проблем Леонарда Адлемана, проблема была открыта в 1995 году.)...

20
Является ли функция подсчета простых чисел # P-полной?

Напомним число простых чисел - функция подсчета простых чисел . Посредством «PRIMES in P» вычисление находится в #P. Проблема № P-завершена? Или, может быть, есть сложная причина полагать, что эта проблема не является # P-полной? π(n)π(n)\pi(n)≤n≤n\le nπ ( n )π(n)π(n)\pi(n) PS Я понимаю, что это...

17
Создает ли PRIMEGAME Конвея все основные силы 2?

На большинстве сайтов, которые я посетил, читая эту интересную тему, говорится что-то вроде «единственные степени двух (кроме 2-х самих), которые встречаются в этой последовательности, - это те, которые имеют простой показатель степени» (MathWorld) или «После 2 эта последовательность содержит...

17
Какие гипотезы TCS были доказаны для простых чисел и малых значений, но затем оказались ложными?

Существуют ли какие-либо предположения в теоретической информатике, которые включают некоторый параметр n и были доказаны для малых значений n AND для простых чисел, но позже оказались ложными? В теории чисел такие проблемы существуют, например. как Аарон Мейеровиц указывает на один из...

13
Почему машинное обучение не может распознавать простые числа?

Скажем, у нас есть векторное представление любого целого числа n, V_n Этот вектор является входом в алгоритм машинного обучения. Первый вопрос: для какого типа представлений можно узнать первичность / составность n, используя нейронную сеть или какое-либо другое ML-отображение векторов в биты. Это...

9
Почему большая часть криптографии зависит от больших пар простых чисел, а не от других проблем?

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