Способ тестирования чисел на простоту



Способ тестирования чисел на простоту
Способ тестирования чисел на простоту
Способ тестирования чисел на простоту

 


Владельцы патента RU 2549129:

Анохин Виктор Александрович (RU)
Шихаев Кирилл Николаевич (RU)

Изобретение относится к области цифровых вычислений и может быть использовано в криптографии. Техническим результатом является повышение достоверности и производительности. Способ содержит этапы, на которых: подают тестируемое число n на вход вычислительной системы, вычисляют Nn=(n2-n)/2. Передают данные в блок деления и вычисляют величину Nn/n. Затем подают численный результат на вход блока проверки числа на целость-дробность. Если число является дробным, то делают вывод, что тестируемое число является составным. В противном случае вычисляют Nn+1. В блоке деления вычисляют Nn+1/n и Nn+1/5. После чего проверяют Nn+1 и Nn+1/5 в блоке проверки числа на целость-дробность. Nn+1 проверяют в блоке проверки числа на четность-нечетность. Если Nn+1/n является целым числом, а Nn+1 является четным или Nn+1/5 является целым числом, то делают вывод, что тестируемое число является простым. 1 з.п. ф-лы, 2 ил, 1 табл.

 

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

Из международной патентной заявки WO 2004/001595 A1 известен способ для тестирования чисел на простоту в криптографии, включающий предварительный тест с малыми простыми числами. Однако известный способ тестирования чисел на простоту оказывается недостаточно эффективным в случае необходимости получения однозначного ответа относительно простоты числа, проходящего простые проверки.

Наиболее близким аналогом настоящего изобретения является способ, известный из патента US 7346637 B2, включающий в себя ряд вычислительных операций и проверок, связанных с тестируемым числом. Однако данный известный способ требует больших вычислительных мощностей, что ограничивает производительность реализующей его вычислительной системы.

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

Обеспечиваемый настоящим изобретением технический результат заключается в повышении достоверности и производительности при тестировании чисел на простоту.

Технический результат достигается благодаря тому, что в способе тестирования чисел на простоту делают вывод относительно простоты тестируемого числа исходя из критериев: а) числа Nn=(n2-n)/2, где n - тестируемое число, от тестируемого простого числа и Nn+1 от последующего составного числа всегда нацело делятся на тестируемые числа, если они простые; б) все числа N, получаемые от составных чисел, кроме составных, следующих за простыми, неделимы нацело тестируемыми числами, если они простые; в) число Nn+1, следующее за тестируемым числом, является всегда четным или делящимся на число 5. Для чего подают данные, характеризующие тестируемое число, на вход вычислительной системы, связанный с входом блока вычисления N, и вычисляют Nn. После чего передают данные в блок деления и вычисляют величину Nn/n. Затем подают данные, характеризующие численный результат, на вход блока проверки числа на целость-дробность, причем если число является дробным, то делают вывод, что тестируемое число является составным, и устанавливают выходной логический уровень вычислительной системы в состояние «0», в противном случае в блоке вычисления N вычисляют Nn+1, а в блоке деления вычисляют Nn+1/n и Nn+1/5. После чего проверяют Nn+1/n и Nn+1/5 в блоке проверки числа на целость-дробность, a Nn+1 проверяют в блоке проверки числа на четность-нечетность. Если Nn+1/n является целым числом, а Nn+1 является четным или Nn+1/5 является целым числом, то делают вывод, что тестируемое число является простым, и устанавливают выходной логический уровень вычислительной системы в состояние «1». В противном случае делают вывод, что тестируемое число является составным, и устанавливают выходной логический уровень вычислительной системы в состояние «0».

В частном случае вход вычислительной системы связывают с входом блока проверки числа на четность-нечетность, причем к вычислению Nn переходят, если проверка тестируемого числа показала нечетность данного числа. В противном случае делают вывод, что тестируемое число является составным и устанавливают выходной логический уровень вычислительной системы в состояние «0».

Изобретение поясняется следующими графическими материалами.

Фиг.1 - блок-схема алгоритма тестирования чисел на простоту.

Фиг.2 - структурная схема вычислительной системы.

Способ тестирования чисел на простоту (фиг.1) основан на закономерности Шихаева-Анохина, согласно которой: а) числа, получаемые по формуле Nn=(n2-n)/2, где n - тестируемое число, от тестируемого простого числа (и от составного числа, следующего за ним), всегда нацело делятся на тестируемые числа, если они простые; б) все числа N получаемые от составных чисел, кроме составных, следующих за простыми, неделимы нацело тестируемыми числами, если они простые;

в) число Nn+1, следующее за тестируемым числом, является всегда четным или делящимся без остатка на число 5.

Закономерность Шихаева-Апохина иллюстрируется на примере нескольких малых простых чисел, отмеченных в таблице знаком «*».

Так, при проверке является ли число 3 простым числом, исходят из следующего: n=3, N3=(32-3)/2=3, N4=(42-4)/2=6. При этом N3/n=3/3=1, a N4/n=6/3=2, то есть производные от тестируемого числа 3 числа N3 и N4 делятся на тестируемое число без остатка. Причем N4 является четным числом. Следовательно, число 3 является простым числом.

Закономерность Шихаева-Анохина справедлива и для больших чисел, что позволяет строить на ее основе производительные технические решения, обеспечивающие высокую достоверность тестирования чисел на простоту.

Тестирование чисел большой разрядности на простоту проводят при помощи вычислительной системы 1, содержащей технические средства для реализации проверки условий закономерности Шихаева-Анохина. На вход вычислительной системы 1 подают тестируемое число в виде цифровых данных. Выход вычислительной системы 1 способен принимать одно из двух возможных состояний в виде логической «1» или «0», соответствующих тому, является ли тестируемое число простым или нет.

Вычислительная система 1 включает в себя запоминающее устройство 2, инкрементор 3, блок 4 вычисления N, блок 5 деления, блок 6 проверки числа на целость-дробность, блок 7 проверки числа на четность-нечетность и устройство управления 8.

Запоминающее устройство 2 выполнено с возможностью хранения тестируемого числа, а блок 4 вычисления N выполнен с возможностью вычисления выражения Nn=(n2-n)/2, где n - тестируемое число. Устройство управления 8 выполнено с возможностью управления работой элементов вычислительной системы 1 для осуществления вычислительного процесса.

Вход вычислительной системы 1 связан с входом запоминающего устройства 2. Выход запоминающего устройства 2 связан с входом инкрементора 3, блока 4 вычисления N и блока 7 проверки числа на четность-нечетность. Выход инкрементора 3 связан с входом блока 4 вычисления N. Выход блока 4 вычисления N связан с входом блока 6 проверки числа на целость-дробность через блок 5 деления и с входом блока 7 проверки числа на четность-нечетность. Выходы блока 6 проверки числа на целость-дробность и блока 7 проверки числа на четность-нечетность связаны с информационным входом устройства управления 8, выполненного с возможностью установки выходного сигнала вычислительной системы 1 в логическое состояние «1» или «0». Управляющие выходы устройства управления 8 связаны с цепями коммутации, задающими поступление данных на вход блока 4 вычисления N и блока 7 проверки числа на четность-нечетность.

Все блоки вычислительной системы 1 являются аппаратными и выполнены на основе элементной базы цифровой микроэлектроники.

Вычислительная система 1 работает следующим образом.

На вход вычислительной системы 1 подают число для тестирования в виде цифровых данных, записываемых в запоминающее устройство 2.

Если в процессе работы допускается возможность поступления на вход вычислительной системы 1 чисел малой разрядности, то сначала производят предварительный отсев путем сравнения тестируемых чисел с рядом известных простых чисел малой разрядности для исключения основных проверок, что дополнительно повышает производительность системы.

Тестирование случайных чисел на простоту предпочтительно начинают с проверки их нечетности, для чего вход вычислительной системы 1 связывают через запоминающее устройство 2 с входом блока 7 проверки числа на четность-нечетность, связанного в свою очередь с устройством управления 8. К вычислению Nn переходят, если проверка тестируемого числа в блоке 7 показала нечетность данного числа, в противном случае делают вывод, что тестируемое число является составным, и устанавливают выходной логический уровень вычислительной системы 1 в состояние «0» при помощи устройства управления 8.

Для проведения проверки условий закономерности Шихаева-Анохина извлекают данные, характеризующие тестируемое число n, из запоминающего устройства 2 и подают их на вход блока вычисления N для вычисления текущего значения Nn, после чего передают данные в блок 5 деления и вычисляют величину Nn/n. Затем подают данные, характеризующие данный промежуточный результат, на вход блока 6 проверки числа на целость-дробность. Если число является дробным, то делают вывод, что тестируемое число n является составным, и устанавливают выходной логический уровень вычислительной системы в состояние «0». В противном случае увеличивают тестируемое число на единицу посредством инкрементора 3 и вычисляют Nn+1 в блоке 4. Затем в блоке 5 деления вычисляют Nn+1/n и Nn+1/5. После чего проверяют Nn+1 и Nn+1/5 в блоке 6 проверки числа на целость-дробность, а Nn+1 проверяют в блоке 7 проверки числа на четность-нечетность. Если Nn+1/n является целым числом, а Nn+1 является четным или Nn+1/5 является целым числом, то делают вывод, что тестируемое число является простым, и устанавливают выходной логический уровень вычислительной системы 1 в состояние «1», в противном случае делают вывод, что тестируемое число является составным, и устанавливают выходной логический уровень вычислительной системы 1 в состояние «0».

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

1. Способ тестирования чисел на простоту, характеризующийся тем, что делают вывод относительно простоты тестируемого числа исходя из критериев: а) числа Nn=(n2-n)/2, где n - тестируемое число, от тестируемого простого числа и Nn+1 от последующего составного числа всегда нацело делятся на тестируемые числа, если они простые; б) все числа N, получаемые от составных чисел, кроме составных, следующих за простыми, неделимы нацело тестируемыми числами, если они простые; в) число Nn+1, следующее за тестируемым числом, является всегда четным или делящимся на число 5; для чего подают данные, характеризующие тестируемое число, на вход вычислительной системы, связанный с входом блока вычисления N, и вычисляют Nn, после чего передают данные в блок деления и вычисляют величину Nn/n, затем подают данные, характеризующие численный результат, на вход блока проверки числа на целость-дробность, причем если число является дробным, то делают вывод, что тестируемое число является составным, и устанавливают выходной логический уровень вычислительной системы в состояние «0», в противном случае в блоке вычисления N вычисляют Nn+1, а в блоке деления вычисляют Nn+1/n и Nn+1/5, после чего проверяют данные числа в блоке проверки числа на целость-дробность, a Nn+1 проверяют в блоке проверки числа на четность-нечетность, и если Nn+1/n является целым числом, a Nn+1 является четным или Nn+1/5 является целым числом, то делают вывод, что тестируемое число является простым, и устанавливают выходной логический уровень вычислительной системы в состояние «1», в противном случае делают вывод, что тестируемое число является составным, и устанавливают выходной логический уровень вычислительной системы в состояние «0».

2. Способ по п.1, в котором вход вычислительной системы связывают с входом проверки числа на четность-нечетность, а к вычислению Nn переходят, если проверка тестируемого числа показала нечетность данного числа, в противном случае делают вывод, что тестируемое число является составным, и устанавливают выходной логический уровень вычислительной системы в состояние «0».



 

Похожие патенты:

Изобретение относится к использованию цифровой вычислительной техники при моделировании боевых действий разнородных группировок. Техническим результатом является повышение уровня достоверности компьютерного моделирования боевых действий.

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

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

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

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

Изобретение относится к средствам моделирования сетей связи. .

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

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

Изобретение относится к способам аппроксимации, используемым в обработке аппаратным обеспечением и программным обеспечением. .

Изобретение относится к области радиотехники и может быть использовано для прогнозирования данных в системах различного назначения. .

Изобретение относится к информационно-измерительной и вычислительной технике и может быть использовано в системах и устройствах для обработки результатов векторной регистрации параметров, получаемых регистраторами параметров электрического режима на отдельных объектах (узлах) энергосистемы. Техническим результатом является расширение функциональных возможностей за счет обеспечения оценки уровня колебаний напряжения в произвольных узлах электроэнергетической системы. Система содержит блок памяти данных от цифровых регистраторов, блок памяти координат цифровых регистраторов, блок памяти границ энергосистемы, блок формирования графа электрической сети энергосистемы, блок построения координатной сетки, блок формирования триангуляции конечного множества маркированных узлов графа, блок присвоения значений данных маркированным узлам, блок расчета интерполированных данных, блок пересчета данных в относительные величины и фильтрации верхних частот, блок памяти значений напряжения и блок оценки параметров колебания напряжения. 2 ил.

Изобретение относится к области геофизики и может быть использовано при обработке сейсмических данных при поиске месторождений углеводородов. Заявленный способ идентификации геологических особенностей из геофизических или атрибутивных данных предполагает использование выполняемого в окне анализа главных компонент или анализа независимых компонент, либо диффузионного картирования. Едва уловимые особенности становятся идентифицируемыми в частичных или остаточных массивах данных. Остаточные массивы данных создаются путем исключения данных, не захваченных самыми заметными главными компонентами. Частичные массивы данных создаются путем проецирования данных на выбранные главные компоненты. Геологические особенности также можно идентифицировать из анализа образов или массивов аномалий, сформированных с помощью матрицы подобия данных с переменным масштабом . Технический результат - повышение точности данных прогноза нефтегазоносности исследуемого участка. 4 н. и 27 з.п. ф-лы, 11 ил.

Изобретение относится к области геофизики и может быть использовано при обработке данных сейсмических исследований. Заявлен способ перестроения моделей (110) Q геологической среды на основании сейсмических данных (10) путем осуществления лучевой Q томографии сдвига центроидных частот. Амплитудный спектр волнового сигнала сейсмического источника аппроксимируют (40) частотно-взвешенной экспоненциальной функцией частоты, имеющей два подбираемых параметра для приведения в соответствие данным о сдвиге частот. В результате чего обеспечивают лучшее соответствие различным асимметричным амплитудным спектрам источника. Боксовые ограничения могут использоваться при выполнении процедуры оптимизации, а многоиндексный способ активных множеств, используемый при томографии скорости, является предпочтительным способом для реализации (100) боксовых ограничений. Технический результат - повышение точности данных сейсмических исследований. 2 н. и 18 з.п. ф-лы, 12 ил.

Изобретение относится к области сейсмической разведки и может быть использовано при поиске нефтяных и газовых месторождений со сложно построенными кавернозно-трещиновато-пористыми коллекторами. Заявлен способ реконструкции тонкой структуры геологического объекта и прогноза его флюидонасыщения на основе выделения и специализированной обработки рассеянной компоненты сейсмического волнового поля с привлечением метода декомпозиции эмпирических мод и полномасштабного численного моделирования в целях формирования высокоточных и достоверных поисковых признаков флюидонасыщения карбонатного коллектора. Технический результат - повышение точности и достоверности получаемых данных. 7 ил.

Изобретение относится к области геофизики и может быть использовано в процессе обработки геофизических данных. Заявлен способ для одновременной инверсии полного волнового поля сейсмограмм кодированных из источников (или приемников) геофизических данных, чтобы определять модель физических свойств для области геологической среды. Во-первых, околоповерхностное временное окно данных (202), в котором удовлетворяется условие стационарных приемников, инвертируется посредством инверсии (205) одновременных кодированных (203) источников. Затем, более глубокое временное окно данных (208) инвертируется посредством разреженной инверсии (209) последовательных источников с использованием модели физических свойств от околоповерхностного временного окна (206) в качестве начальной модели (207). Альтернативно, модель околоповерхностных временных окон используется для того, чтобы моделировать отсутствующие данные (211) максимальных выносов, формирующие набор данных, удовлетворяющий предположению о стационарных приемниках, после чего этот набор данных кодируется из источников (212) и инвертируется посредством инверсии (214) одновременных источников. Технический результат - повышение точности получаемых данных. 5 н. и 16 з.п. ф-лы, 17 ил., 1 пр.

Изобретение относится к области проектирования нефтяного коллектора управления им и его отдачей. Технический результат - более точная оценка фактических условий в существующем коллекторе, разработка и реализация разумного плана мероприятий для увеличения краткосрочных рабочих дебитов и долгосрочной нефтеотдачи коллектора. Информацию собирают с использованием уникальных комплексных методик сбора и анализа системы показателей и информации в адресном режиме с помощью весовой обработки данных в контексте конкретного коллектора и целей производителя. Рейтинг коллектора генерируют с использованием асимметричного анализа системы показателей и последующего использования для формирования плана мероприятий. Архитектура добычи (например, число, местоположение и способ строительства нефтяных и нагнетательных скважин) затем строится согласно плану мероприятий. Может осуществляться непрерывный мониторинг показателей работы коллектора и использоваться для подтверждения целевых показателей добычи и нефтеотдачи и/или обеспечения срабатывания пусковых или тревожных схем для замены оборудования добычи. 7 н. и 19 з.п. ф-лы, 35 ил., 5 прим., 24 табл.

Изобретение относится к цифровой вычислительной технике. Технический результат - повышение точности обработки информации для выбора рациональной стратегии (PC) при неполноте разведывательной информации о координатах боевых средств (БСр) группировок сторон. В способе коммутируют информацию о данных своих БСр и средств каждой группировки противника, записывают ее в блоки памяти, определяют однородность БСр группировок, фиксируют уровни неполноты информации о координатах БСр группировок, в зависимости от исходных данных формируют рекомендации по выбору PC, вызывают информацию из исходных блоков памяти для нахождения остатков своих БСр и противника, которую записывают в четвертый блок памяти, посредством команды от блока управления в блоке визуализации высвечивается информация о PC, о победителе в боевых действиях и остатках своих БСр и противника. Устройство, реализующее способ, содержит коммутатор, четыре блока памяти, блок управления, блок определения однородности БСр, блок логики, блок определения остатков БСр и блок визуализации. 2 н.п. ф-лы, 3 ил., 4 табл.

Изобретение относится к области автоматизированного управления и может быть использовано в автоматизированных системах управления (АСУ) войсками противовоздушной обороны (ПВО). Техническим результатом является обеспечение расчета минимального требуемого количества воздействий огневых средств группировки ПВО и такого их распределения по целям, при котором эффективность боевых действий группировки ПВО не меньше заданной. Устройство содержит блок задания исходных данных, три блока умножения, два блока деления, два сумматора и вычитатель. 2 ил.

Изобретение относится к способу и устройству оценки связей или отображений сигналов. Технический результат заключается в повышении эффективности оценки свойств сигналов. Устройство содержит средства оценки связи или нескольких связей двух или нескольких сигналов или их передаточных функций, представляемых на вещественной или соответственно комплексной числовой плоскости, средства оценки произвольно определяемого отображения или отображений сигнала или нескольких сигналов, представляемых на вещественной или комплексной числовой плоскости, средства определения инвариантов отображения или нескольких отображений связи или связей для одного или нескольких отрезков сигнала или средства определения инвариантов отображения или нескольких отображений произвольно определяемого отображения или произвольно определяемых отображений для одного или нескольких отрезков сигнала. 2 н. и 22 з.п. ф-лы, 29 ил.

Изобретение относится к области геофизики и может быть использовано для обработки сейсмических данных. Предложен способ повышения скорости итерационной инверсии сейсмических данных для получения модели геологической среды с использованием локальной оптимизации функции стоимости. Частотный спектр обновленной модели при каждой итерации регулируют до соответствия известному или расчетному частотному спектру для области геологической среды, предпочтительно среднему амплитудному спектру импеданса геологической среды для продольных волн. Регулирование выполняют применением формирующего спектр фильтра к сейсмическому импульсу источника и к данным или применением фильтра, который можно изменять во времени, к градиенту функции стоимости. Технический результат - повышение точности получаемых данных. 2 н. и 21 з.п. ф-лы, 15 ил.
Наверх