Темы

Алгоритмы теории чисел

Number Theory Algorithms · 54 статей

  1. Алгоритм Евклида для вычисления наибольшего общего делителя

    Евклидов алгоритм: эффективный метод вычисления наибольшего общего делителя (НОД) двух чисел. Основан на принципе замены большего числа разностью с меньшим.

    #2442 · 16 мин чтения

  2. Поиск простых чисел Мерсенна: Коллективный проект GIMPS

    GIMPS: поиск простых чисел Мерсенна с помощью распределённых вычислений. Бесплатное ПО, волонтёры, научные исследования и крупнейший проект подобного рода.

    #3077 · 7 мин чтения

  3. Разложение числа на множители

    Разложение чисел на множители: определение, простые и составные числа, теорема о единственности разложения на простые множители. Теория чисел.

    #3700 · 6 мин чтения

  4. Алгоритмы умножения чисел: от решеток до двоичного метода

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

    #13397 · 7 мин чтения

  5. Обобщение символа Лежандра и символ Якоби в теории чисел

    Символ Лежандра и обобщение – символ Якоби в теории чисел. Свойства, применение в теории модулярной арифметики, криптографии и тестировании простоты.

    #22626 · 4 мин чтения

  6. Расширенный алгоритм Евклида и вычисление наибольшего общего делителя

    Расширенный алгоритм Евклида: вычисление НОД, коэффициентов Безу и обратных по модулю. Применение в арифметике и программировании. Полезен для взаимно простых чисел.

    #23057 · 1 мин чтения

  7. Общий решето числового поля: алгоритм факторизации больших чисел

    Общий решето числового поля (GNFS): самый эффективный алгоритм факторизации больших чисел (>10^100). Теория чисел, сложность, гладкие числа.

    #48173 · 5 мин чтения

  8. Алгоритм факторизации методом эллиптических кривых Ленстры

    Разложение чисел на множители: алгоритм Ленстры (ECM) – быстрый метод факторизации, особенно эффективный для поиска малых множителей. Обзор и сравнение с другими алгоритмами.

    #48502 · 6 мин чтения

  9. Алгоритмы проверки простоты чисел

    Проверка чисел на простоту: алгоритмы, тесты (Миллера-Рабина), применение в криптографии. Определение, является ли число простым, без разложения на множители.

    #55137 · 4 мин чтения

  10. Тест простоты Миллера — Рабина

    Тест Миллера-Рабина: вероятностный алгоритм проверки чисел на простоту. Быстрый и простой метод, широко используемый в криптографии и математике.

    #56112 · 3 мин чтения

  11. Интерполяционные полиномы Лагранжа: теория и применение

    Интерполяционный многочлен Лагранжа: уникальный полином для аппроксимации данных. История, формула, применение в численном анализе, криптографии и кодировании.

    #61476 · 1 мин чтения

  12. Быстрое преобразование Фурье для простых размеров: Алгоритм Радера

    Быстрое преобразование Фурье (FFT) для простых размеров: алгоритм Радера, его применение и связь с другими методами (Блюстейна, Винограда). DFT, числотеоретические преобразования.

    #65702 · 3 мин чтения

  13. Алгоритм Бруна: Быстрое преобразование Фурье и альтернативные подходы.

    Алгоритм Бруна: быстрый алгоритм Фурье для эффективного вычисления ДПФ реальных данных. Альтернатива Cooley-Tukey, рекурсивный подход, точность и обобщения FFT.

    #70899 · 2 мин чтения

  14. Тест Люка — Лемера для чисел Мерсенна

    Тест Люка — Лемера: проверка чисел Мерсенна на простоту. Эффективный алгоритм для определения, является ли число Мерсенна простым. Математика, простота чисел.

    #79311 · 2 мин чтения

  15. Алгоритм умножения больших чисел Тума-Кука

    Алгоритм Тума-Кука: быстрое умножение больших чисел. Разделение на части, рекурсия и снижение сложности вычислений. Toom 3 – частный случай.

    #80313 · 3 мин чтения

  16. Алгоритм вычисления корня n-й степени с использованием сдвига разрядов.

    Алгоритм извлечения корня n-й степени: итеративный метод, похожий на деление в столбик. Описание процесса, обозначения и формулы для вычисления.

    #81631 · 3 мин чтения

  17. Алгоритм быстрого преобразования Фурье: от Гаусса до Кули-Тьюки

    Алгоритм быстрого преобразования Фурье (FFT) Cooley-Tukey: принцип работы, снижение вычислительной сложности до O(N log N). Оптимизация DFT и комбинации с другими алгоритмами.

    #84069 · 2 мин чтения

  18. Prime95: Поиск простых чисел и тестирование стабильности системы.

    Prime95: бесплатная программа для поиска простых чисел. Тестирует числа на простоту (Fermat, Lucas-Lehmer). GIMPS получает награды за найденные простые числа.

    #89749 · 2 мин чтения

  19. Тест простоты AKS: полиномиальный алгоритм доказательства простоты числа

    Тест простоты AKS: алгоритм для определения, является ли число простым, за полиномиальное время без гипотез. Признан за вклад в математику и IT.

    #92541 · 3 мин чтения

  20. GNU Multi Precision Library: Обзор и Применение

    Бесплатная библиотека GMP для работы с большими числами: криптография, безопасность, компьютерная алгебра. Высокая скорость и оптимизация для разных процессоров.

    #105845 · 2 мин чтения

  21. Метод пробного деления в факторизации целых чисел

    Метод пробного деления: простой, но трудоёмкий алгоритм факторизации целых чисел. Описание, история (Фибоначчи, 1202) и оценка сложности алгоритма.

    #116287 · 3 мин чтения

  22. Гиперэллиптическая криптография: основы и особенности реализации

    Гиперэллиптическая криптография: математические основы, сравнение с ECC, использование якобианов и дивизоров. Безопасность и применение в криптосистемах.

    #116844 · 6 мин чтения

  23. Алгоритм "Метод младенческих шагов и гигантских шагов" для решения дискретного логарифма

    Дискретное логарифмирование: алгоритм "baby-step giant-step" Шенкса для вычисления порядка элемента в группах. Важно для криптографии и безопасности данных.

    #117153 · 1 мин чтения

  24. Соответствия квадратов в факторизации целых чисел

    Конгруэнция квадратов в теории чисел: метод факторизации целых чисел. Построение на основе фактор-базы для поиска гладких чисел и разложения на простые множители.

    #118914 · 2 мин чтения

  25. Цепи сложений и проблема их минимальной длины.

    Цепи сложения в математике: вычисление чисел через последовательность сумм. Поиск оптимальной цепи – сложная NP-полная задача, алгоритмов нет.

    #119172 · 2 мин чтения

  26. Алгоритм факторизации Полларда-ро

    Алгоритм факторизации Полларда: быстрый метод разложения чисел на простые множители. Эффективен для поиска малых простых делителей, требует мало памяти.

    #119424 · 3 мин чтения

  27. Квадратичное решето: алгоритм факторизации целых чисел

    Квадратичное решето: быстрый алгоритм факторизации целых чисел до 100 цифр. Принцип работы, этапы и преимущества перед другими методами. Факторизация чисел.

    #119650 · 7 мин чтения

  28. Специальное решето числового поля: алгоритм факторизации целых чисел.

    Специальное решето числового поля (SNFS): алгоритм факторизации целых чисел вида re ± s. Эффективно для чисел Мерсенна и проектов Cunningham.

    #120541 · 3 мин чтения

  29. Арифметика произвольной точности: вычисления без ограничений по размеру чисел

    Арифметика произвольной точности: вычисления с числами, ограниченными только объемом памяти. Bignum, библиотеки, языки программирования, точные результаты.

    #122239 · 7 мин чтения

  30. Волькер Штрассен: Математик и пионер алгоритмов

    Волькер Штрассен – немецкий математик, известный своими работами в области алгоритмов и анализа матриц. Разработал алгоритм Штрассена для быстрого умножения матриц.

    #144038 · 2 мин чтения

  31. ТВИНКЛ: Оптический процессор для факторизации целых чисел.

    TWINKLE: гипотетическое устройство для факторизации чисел до 512 бит, предложенное Ади Шамиром. Основано на алгоритме Number Field Sieve. Низкая стоимость.

    #149114 · 3 мин чтения

  32. Оптимальное возведение в степень с помощью цепных сложений

    Оптимальное возведение в степень: эффективный метод с минимальным числом умножений. Алгоритмы построения цепей сложений для быстрого вычисления степени числа.

    #151440 · 3 мин чтения

  33. Операции модульной арифметики и возведение в степень

    Модульное возведение в степень: вычисление остатка от деления b^e на m. Применение в криптографии (RSA, Diffie-Hellman). Алгоритм и отрицательные степени.

    #157710 · 3 мин чтения

  34. Алгоритм быстрого модулярного умножения Монтгомери

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

    #157876 · 5 мин чтения

  35. Фабрис Белар: Французский программист и его разработки

    Фабрис Беллар – французский программист, создатель FFmpeg, QEMU и Tiny C Compiler. Разработал формулу Беллара для вычисления цифр числа Пи. 🇫🇷💻

    #160723 · 3 мин чтения

  36. Алгоритм шифрования Cayley–Purser: история и анализ

    Алгоритм шифрования Cayley-Purser: история, разработка и недостатки криптографической системы, предложенной школьницей Сарой Фланнери в 1999 году.

    #171115 · 3 мин чтения

  37. Метод факторизации Диксона

    Метод факторизации Диксона: алгоритм целочисленной факторизации, не зависящий от гипотез о гладкости. Разработан в 1981 году, основан на сравнении квадратов по модулю N.

    #173263 · 2 мин чтения

  38. Числа с малыми простыми делителями

    Гладкие числа в теории чисел: определение, свойства и важность для криптографии. Числа, факторизация которых состоит только из малых простых множителей.

    #173439 · 3 мин чтения

  39. Представление чисел со знаковой системой счисления и свойством "не смежности"

    Представление чисел со знаком (NAF): уникальный способ записи, минимизирующий вес Хэмминга. Каноническая форма для эффективных вычислений и сжатия данных.

    #190755 · 2 мин чтения

  40. Алгоритм Шёнхаге — Штрассена для быстрого умножения больших чисел

    Алгоритм Шёнхаге-Страссена: быстрое умножение больших чисел. Основан на БПФ и превосходит Карацубу/Toom-Cook для чисел от 10 тыс. знаков. История и сложность.

    #209017 · 3 мин чтения

  41. Алгоритм индексного исчисления для вычисления дискретных логарифмов

    Вычисление дискретных логарифмов: алгоритм индексного исчисления в теории чисел. Применение к простым числам и эллиптическим кривым. Эффективное решение!

    #227757 · 4 мин чтения

  42. Лемма Хенселя: Подъем решений в модульной арифметике

    Лемма Гензеля: подъем корней многочленов в модульной арифметике. Обобщения для коммутативных колец и p-адических чисел. Алгоритм Гензеля для факторизации.

    #236403 · 4 мин чтения

  43. Алгоритм ЛЛЛ: Основы и применения в теории чисел и криптографии.

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

    #246517 · 2 мин чтения

  44. Псевдопростые числа Фробениуса: теория и тесты на простоту.

    Псевдопростые числа Фробениуса: определение, свойства и применение в тестах на простоту. Оптимизация параметров для снижения ложных срабатываний.

    #294107 · 2 мин чтения

  45. Алгоритмы генерации простых чисел

    Генерация простых чисел: эффективные алгоритмы для криптографии, хеширования и факторизации. Решето Эратосфена – быстрый способ поиска простых чисел.

    #317386 · 4 мин чтения

  46. FFTW: Быстрая библиотека для вычисления дискретного преобразования Фурье

    FFTW: быстрая библиотека для вычисления дискретных преобразований Фурье (ДПФ). Оптимизация FFT алгоритмов для скорости и эффективности. Бесплатное ПО.

    #351807 · 1 мин чтения

  47. Super PI: История, Проблемы и Альтернативы Бенчмаркинга

    Super PI: программа для вычисления числа Пи до 32 млн знаков. Бенчмарк и стресс-тест для разгона ПК. Обнаружение и борьба с подделкой результатов.

    #367622 · 1 мин чтения

  48. Алгоритм Шоофа для подсчета точек на эллиптических кривых над конечными полями.

    Алгоритм Шуфа: эффективный подсчет точек на эллиптических кривых над конечными полями. Применение в криптографии, безопасность, сложность дискретного логарифмирования.

    #394441 · 5 мин чтения

  49. Алгоритм Tonelli–Shanks для извлечения квадратных корней по модулю простого числа.

    Алгоритм Tonelli-Shanks: извлечение квадратного корня по модулю простого числа p. Решение сравнений r² ≡ n (mod p). Оптимизация, сравнение с другими алгоритмами.

    #399416 · 2 мин чтения

  50. Метод разделяющих окружностей для факторизации многочленов.

    Метод разделяющих окружностей: численный алгоритм факторизации полиномов и нахождения комплексных корней. Разработан Шёнхаге, усовершенствован Паном.

    #400409 · 4 мин чтения

  51. Алгоритм Шоофа — Элкиса — Аткина для вычисления порядка эллиптической кривой

    Алгоритм Шуфа-Элкиса-Аткина (SEA): быстрый способ вычисления порядка эллиптической кривой над конечным полем для криптографии. Оптимизация алгоритма Шуфа.

    #402103 · 2 мин чтения

  52. Freivalds' algorithm

    #460091 · 2 мин чтения

  53. Fermat (computer algebra system)

    #470165 · 3 мин чтения

  54. LCS35

    #474008 · 1 мин чтения