Безопасное простое число
Безопасное простое число — это простое число вида 2p + 1, где p также простое (и наоборот, p есть простое число Софи Жермен). Несколько первых безопасных простых чисел:
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, … (A005385)За исключением 7, безопасное простое число q имеет форму 6k − 1 или, что эквивалентно, q ≡ 5 (mod 6) — где p > 3. Таким же образом, за исключением 5, безопасное простое число q представимо в форме 4k − 1 или, что эквивалентно, q ≡ 3 (mod 4) — тривиальное утверждение, поскольку (q − 1) / 2 должно быть нечетным натуральным числом. Комбинируя обе формы с использованием НОК (6,4) мы получим, что безопасное простое число q > 7 также должно быть представимо в виде 12k−1 или, что эквивалентно, q ≡ 11 (mod 12).
Источник: Википедия
Связанные понятия
Евклидово кольцо — общеалгебраическое кольцо, в котором существует аналог алгоритма Евклида.
В теории чисел гладким числом называется целое число, все простые делители которого малы.
Подробнее: Гладкое число
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Праймориал (англ. Primorial, иногда именуется также «примориал») — в теории чисел функция над рядом натуральных чисел, схожая с функцией факториала, с разницей в том, что праймориал является последовательным произведением простых чисел, меньших или равных данному, в то время как факториал является последовательным произведением всех натуральных чисел, меньших или равных данному.
Рациональное решето — это алгоритм общего вида для разложения целых чисел на простые множители. Алгоритм является частным случаем общего метода решета числового поля. Хотя он менее эффективен, чем общий алгоритм, концептуально он проще. Алгоритм может помочь понять, как работает общий метод решета числового поля.
Полукольцо — общеалгебраическая структура, похожая на кольцо, но без требования существования противоположного по сложению элемента.
«Тогда́ и то́лько тогда ́» — логическая связка эквиваленции между утверждениями, применяемая в логике, математике, философии. Чтобы быть эквиваленцией, связка должна быть идентична стандартному материальному условному высказыванию («только тогда» эквивалентно «если … то»), соединённому со своей противоположностью, откуда и название связки. В результате истинность одного утверждения требует такой же истинности другого, то есть либо оба они истинны, либо оба ложны. Можно спорить о том, передаёт ли выражение...
Группа классов идеалов дедекиндова кольца — это, грубо говоря, группа, позволяющая сказать, насколько сильно в данном кольце нарушается свойство факториальности. Эта группа тривиальна тогда и только тогда, когда дедекиндово кольцо является факториальным. Свойства дедекиндова кольца, касающиеся умножения его элементов, тесно связаны с устройством этой группы.
Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов, в которой один элемент (такой как вершина графа) добавляется в задачу на каждом шаге и используется небольшое решение задачи перед добавлением элемента, чтобы найти небольшое решение задачи после добавления.
Криптосистема Уильямса (Williams System) — система шифрования с открытым ключом, созданная Хью Коуи Уильямсом (Hugh Cowie Williams) в 1984 году.
Обра́тный элеме́нт — термин в общей алгебре, обобщающий понятия обратного числа (для умножения) и противоположного числа (для сложения).
Наиме́ньшее о́бщее кра́тное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка. Обозначается одним из следующих способов...
Предобуславливание (также предобусловливание) — процесс преобразования условий задачи для её более корректного численного решения. Предобуславливание обычно связано с уменьшением числа обусловленности задачи. Предобуславливаемая задача обычно затем решается итерационным методом.
Целые
числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.
В математике свободная абелева группа (свободный Z-модуль) — это абелева группа, имеющая базис, то есть такое подмножество элементов группы, что для любого её элемента существует единственное его представление в виде линейной комбинации базисных элементов с целыми коэффициентами, из которых только конечное число являются ненулевыми. Элементы свободной абелевой группы с базисом B называют также формальными суммами над B. Свободные абелевы группы и формальные суммы используются в алгебраической топологии...
Принцип Дирихле нередко применяется при доказательстве теорем, особенно в дискретной математике; в частности, в теории диофантовых приближений при анализе систем линейных неравенств.
Скорость сходимости является основной характеристикой численных методов решения уравнений и оптимизации.
Множество больших тригонометрических сумм — понятие теории чисел — множество индексов, в которых преобразование Фурье характеристической функции заданного подмножества группы принимает достаточно большие значения.
Полный квадрат или квадратное число — число, являющееся квадратом некоторого целого числа. Иными словами, квадратом является целое число, квадратный корень которого тоже целый.
В общей алгебре, термин кручение относится к элементам группы, имеющим конечный порядок, или к элементам модуля, аннулируемым регулярным элементом кольца.
Подробнее: Кручение (алгебра)
Алгоритм распространения доверия (англ. belief propagation, также алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях (таких как байесовские и марковские сети). Предложен Дж. Перлом в 1982 году.
Инволюция (от лат. involutio — свёртывание, завиток) — преобразование, которое является обратным самому себе.
Формальное дифференцирование — операция над элементами кольца многочленов или кольцом формальных степенных рядов, повторяющая форму производных из математического анализа. Алгебраическое преимущество формального дифференцирования состоит в том, что оно не опирается на понятие предела, которое в общем случае невозможно определить для кольца. Многие свойства производной верны для формального дифференцирования, но некоторые, особенно касающиеся утверждений, содержащих числа, не верны. В основном формальное...
В теории информации
теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике (например, метод вероятностного округления) и теории информации.
Метод неопределённых коэффициентов ― метод, используемый в математике для нахождения искомой функции в виде точной или приближённой линейной комбинации конечного или бесконечного набора базовых функций.
Техники спектральной кластеризации используют спектр (собственные значения) матрицы сходства данных для осуществления понижения размерности перед кластеризацией в пространствах меньших размерностей. Матрица сходства подаётся в качестве входа и состоит из количественных оценок относительной схожести каждой пары точек в данных.
Подробнее: Спектральная кластеризация
Псевдопростое число — натуральное число, обладающее некоторыми свойствами простых чисел, являясь тем не менее составным. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел.
Одночлен (также моном) — простое математическое выражение, прежде всего рассматриваемое и используемое в элементарной алгебре, а именно, произведение, состоящее из числового множителя и одной или нескольких переменных, взятых каждая в неотрицательной целой степени .
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...
Точное нахождение первообразной (или интеграла) произвольных функций — процедура более сложная, чем «дифференцирование», то есть нахождение производной. Зачастую, выразить интеграл в элементарных функциях невозможно.
Подробнее: Методы интегрирования
Задача о покрытии множества является классическим вопросом информатики и теории сложности. Данная задача обобщает NP-полную задачу о вершинном покрытии (и потому является NP-сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в приближённом алгоритме, здесь не работает. Вместо этого мы рассмотрим жадный алгоритм. Даваемое им решение будет хуже оптимального в логарифмическое число раз. С ростом размера задачи качество решения ухудшается, но всё же довольно...
В математике централизатор подмножества S группы G — это множество элементов G, которые коммутируют с каждым элементом S, а нормализатор S — это множество элементов G, которые коммутируют с S «в целом». Централизатор и нормализатор S являются подгруппами G и могут пролить свет на структуру G.
Метод итерации — численный метод решения математических задач, приближённый метод решения системы линейных алгебраических уравнений. Суть такого метода заключается в нахождении по приближённому значению величины следующего приближения (являющегося более точным).
Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из множества на евклидовой плоскости.
В теории групп циклическая перестановка — это перестановка элементов некоторого множества X, которая переставляет элементы некоторого подмножества S множества X циклическим образом, сохраняя на месте остальные элементы X (т.е. отображая их в себя). Например, перестановка {1, 2, 3, 4}, переводящая 1 в 3, 3 в 2, 2 в 4 и 4 в 1 является циклической, в то время как перестановка, переводящая 1 в 3, 3 в 1, 2 в 4 и 4 в 2 циклической не является.
Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Её сложность лежит в основе некоторых алгоритмов шифрования с открытым ключом, таких как RSA.
Мультимножество в математике — обобщение понятия множества, допускающее включение одного и того же элемента по нескольку раз. Число элементов в мультимножестве, с учётом повторяющихся элементов, называется его размером или мощностью.
Куб Фибоначчи можно определить в терминах кодов Фибоначчи и расстояния Хэмминга, независимых множеств вершин в путях, или через дистрибутивные решётки.
Дробная раскраска — это тема молодой области теории графов, известной как теория дробных графов. Дробная раскраска является обобщением обычной раскраски. В традиционной раскраске графа каждой вершине назначается некий цвет, и смежным вершинам — тем, что связаны рёбрами, — должны быть назначены разные цвета. В дробной раскраске каждой вершине назначается набор цветов.
Система уравнений — это условие, состоящее в одновременном выполнении нескольких уравнений относительно нескольких (или одной) переменных.
Теоремы об изоморфизме в алгебре — ряд теорем, связывающих понятия фактора, гомоморфизма и вложенного объекта. Утверждением теорем является изоморфизм некоторой пары групп, колец, модулей, линейных пространств, алгебр Ли или прочих алгебраических структур (в зависимости от области применения). Обычно насчитывают три теоремы об изоморфизме, называемые Первой (также основная теорема о гомоморфизме), Второй и Третьей. Хотя подобные теоремы достаточно легко следуют из определения фактора и честь их открытия...
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.