Итерационный бинарный критерий делимости: Деление без деления. Алгоритм для Big Integers и FPGA

Итерационный бинарный критерий делимости: Деление без деления. Алгоритм для Big Integers и FPGA. Деление — одна из самых ресурсоемких операций для Big Integers в криптографии и для аппаратных ускорителей (FPGA/ASIC). Что, если бы можно было проверять делимость, полностью исключив операцию деления и взятия остатка? Представляем новый детерминированный алгоритм, который заменяет дорогой N mod d на O(logN) итераций, состоящих исключительно из сложения (X+d) и побитового сдвига. Разбираем, как этот подход, обладающий линейно-логарифмической сложностью O(n⋅logN), обеспечивает радикальное снижение константного фактора и становится идеальным решением для многословной арифметики и низкоуровневой оптимизации железа. Экспертный уровень .

https://habr.com/ru/articles/975814/

#алгоритмы #теория_чисел #бинарный_алгоритм #big_integers #многословная_арифметика #оптимизация #fpga #аппаратная_реализация #криптография #деление_без_деления

Головоломка по информатике из университетского квеста

Informatix – одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2013 года. Эта игра представляет собой ежегодный квест, цель которого — первыми обнаружить "сокровища", спрятанные где-то на территории кампуса. Задания игры не содержат инструкций. Вместо этого участникам дается сюжет, который постепенно развивается, и в который встраиваются головоломки. Ответом на задание является слово или словосочетание. Таким образом, если решением головоломки является нечто иное, то должен существовать какой-то способ, как получить из него слова. Сюжет игры в том году был основан на персонажах комиксов про Астерикса и Обеликса, а каждая ее головоломка была связана или с одним из жителей деревни галлов, или с кем-то из римлян. Informatix – один из жителей деревни. Его головоломка была частью второго акта игры. Головоломке предшествовало изображение этого персонажа, а также его краткое описание: «Эксперт в области обработки и извлечения данных, Informatix всегда склонен слишком усложнять проблему».

https://habr.com/ru/articles/960270/

#головоломки #головоломка #квест #квесты #логические_игры #логические_задачи #теория_чисел #информатика

Как превратить математику в игру с шифрами: школьный взгляд на криптографию

Здравствуйте, уважаемые читатели Хабра! Представьте себе мир, где каждое ваше слово, каждая мысль – открытая книга. Жутковато, правда? На протяжении веков человечество стремилось сохранить свои тайны, и криптография всегда была тем мощным инструментом, что помогал это делать. Сегодня мы, команда проекта Большой математической мастерской (БММ) – уникального образовательного события, где школьники, студенты и педагоги работают над общими проектами – хотим поделиться нашим погружением в этот увлекательный мир. Мы не профессиональные криптографы, но наш проект «Как превратить математику в игру с шифрами» доказывает: математика – это не только «сухая наука», но и захватывающая игра, особенно когда дело касается шифров и секретных сообщений. В рамках этого проекта мы создаем сборник криптографических задач для научно-популярной книги, ориентированной на школьников 8-11 классов. Наш подход на БММ основан на непрерывном обучении, умении задавать правильные вопросы и создавать работающие, интересные решения, опираясь на авторитетные источники и консультации специалистов. Именно этим мы и занимались, исследуя мир шифров. Мы надеемся, что статья будет интересна не только тем, кто уже знаком с криптографией, но и преподавателям, методистам, а также просто любопытным читателям, которые хотят взглянуть на математику под другим углом.

https://habr.com/ru/articles/948910/

#криптография #шифры #математика #образование #БММ #задачи #теория_чисел

Теоретико-числовой подход решает проблемы квантовой теории поля

Ученые из МФТИ и Института геохимии и аналитической химии им. В. И. Вернадского предложили модель для квантовой теории поля, которая решает проблему вычисления энергии вакуума. Она открывает огромное поле для новых теоретических исследований и может претендовать на решение множество других важных проблем, в том числе связанных с построением истинной квантовой теории гравитации. Работа была опубликована в p-Adic Numbers, Ultrametric Analysis and Applications.

https://habr.com/ru/articles/937674/

#Квантовая_теория_поля #Теория_чисел #Энергия_вакуума #Флуктуации_вакуума #Перенормировка

Построение графиков простых чисел

Почему простые числа, отображенные в полярных координатах, имеют форму спиралей или линий? Создание сюжета Для начала нам необходимо увидеть, каковы эти шаблоны на самом деле. Давайте начнем наше исследование с импорта базовых модулей. import math
import sympy
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
%config InlineBackend.figure_format='retina'
plt.style.use('dark_background') Один из модулей, который я здесь использую, но который я обычно не использую, — это SymPy, библиотека Python для символьной математики. Хотя SymPy предлагает широкий спектр функций для вычислений, я использую его просто для генерации простых чисел. print(list(sympy.primerange(0, 100))) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] Полярные координаты Сначала давайте напишем функцию, которая принимает некоторое число в качестве входных данных и преобразует его в декартово представление полярных координат. Выходные данные сами по себе являются декартовыми, но координаты, которые они представляют, соответствуют полярным координатам. Мы могли бы понимать эту функцию как преобразованиеС: Р →Р2С:Р→Р2такой что С( х ) = ( х соз( х ) , х грех( х ) ) В Python мы можем реализовать этот перевод следующим образом: def get_coordinate(num):
return num * np.cos(num), num * np.sin(num) Давайте проведем быструю проверку работоспособности и увидим, чтоС( 1 )С(1)возвращает некоторую точку в первом квадранте. get_coordinate(1) (0.5403023058681398, 0.8414709848078965) Отлично! Однако проблема с текущей настройкой заключается в том, что она не векторизована; чтобы сгенерировать координаты, скажем, для десяти чисел, нам понадобится цикл for для генерации координат для каждого из десяти чисел.

https://habr.com/ru/articles/866948/

#спираль_улама #простые_числа #теория_чисел #компьютерная_графика #визуализация_данных

Математическая продлёнка. Изобретаем параболические числа

Курс начальной школы приучает нас к тому, что числа пригодны для счёта. В средней школе, когда к математике подключаются физика и химия, мы узнаём, что числами можно моделировать всевозможные явления от наполнения бассейнов и движения велосипедистов, до количества тепла, которое выделится, если дать соединиться двум молям водорода и одному молю кислорода. А в старших классах на смену числам приходят функции, векторы и другие замечательные математические объекты, которыми можно моделировать ещё более сложные процессы и явления. Однако, если заглянуть в «большую» математику, обитающую в университетах, а также в статьях и книгах, посвящённых специальным разделам математики, то можно обнаружить что числа, вернее числовые системы: кольца, поля, их расширения и модули над ними, сами по себе оказываются способны на многое. Ими можно моделировать целые пространства, геометрические объекты и их преобразования (комплексные числа, кватернионы, алгебры Клиффорда), регулярные структуры, обладающие пространственной симметрией (числа Гаусса, Эйзенштейна) или преобразования специальной теории относительности (дуальные числа, алгебра пространства-времени). В этой статье мы поговорим о том, как с помощью дуальных чисел можно решать задачи, в которых есть величины с погрешностями. Кроме того, добавим к чистой математике немного генеративного искусства и познакомимся с самой простой работающей системой автоматического дифференцирования.

https://habr.com/ru/articles/863068/

#теория_чисел #автоматическое_дифференцирование #вычисления_с_погрешностями #дуальные_числа #рациональные_дроби #теория_расширений #фрактал_Ньютона #julia_language

Математическая продлёнка. Изобретаем гиперболические числа

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

https://habr.com/ru/articles/862852/

#теория_чисел #гиперболические_числа #двойные_числа #формула_бине #теория_представлений

Математическая продлёнка. Изобретаем эллиптические числа

Продолжаем разбираться с числостроительством в серии заметок «Изобретаем числа». В предыдущих статьях этой серии мы последовательно подходили к построению числовых систем (алгебраических структур, которые я неформально называю арифметиками), как модулей над более простыми системами. В прошлый раз мы ввели классификацию таких арифметик, пользуясь их матричными представлениями, и разбили их на классы: эллиптические, гиперболические и параболические. Сегодня я хочу поговорить об эллиптических арифметиках, к которым относятся хорошо всем известные комплексные числа и менее известные, но полезные числа Эйзенштейна. В частности, мы поговорим о том, почему среди многообразия возможных эллиптических арифметик именно комплексные числа в том виде, в котором мы их знаем, являются наиболее удобными и универсальными.

https://habr.com/ru/articles/862012/

#теория_чисел #комплексные_числа #мнимая_единица #числа_Эйезенштейна #числа_Гаусса

Математическая продлёнка. Изобретаем числа по-взрослому

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

https://habr.com/ru/articles/861904/

#теория_чисел #теория_представлений #матрицы #линейность #гауссовы_числа #комплексные_числа

Математическая продлёнка. Изобретаем числа II

Это вторая часть серии статей, посвящённой построению числовых систем, основанных на упорядоченных парах. В предыдущей статье мы рассмотрели как строится кольцо целых чисел из пары натуральных, освоившись с понятиями классов эквивалентности и факторизацией. В этой построим ещё одну знакомую числовую систему: поле рациональных чисел. Материал расчитан на тех, кто учит старшеклассников или младшекурсников

https://habr.com/ru/articles/861614/

#теория_чисел #рациональные_дроби #эквивалентные_классы #факторизация