Вычислительная система для тестирования чисел на простоту

Вычислительная система для тестирования чисел па простоту относится к области цифровых вычислений. Система включает в себя запоминающее устройство, инкрементор, блок вычисления N, блок деления, блок проверки числа на целость-дробность, блок проверки числа на четность-нечетность и устройство управления. Запоминающее устройство выполнено с возможностью хранения тестируемого числа. Блок вычисления N выполнен с возможностью вычисления выражения N_n=(n²-n)/2, где n - тестируемое число. Вход вычислительной системы связан с входом запоминающего устройства. Выход запоминающего устройства связан с входом инкрементора. Блока вычисления N и блока проверки числа на четность-нечетность. Выход инкрементора связан с входом блока вычисления N. Выход блока вычисления N связан с входом блока проверки числа на целость-дробность через блок деления и с входом блока проверки числа на четность-нечетность. Выходы блока проверки числа на целость-дробность и блока проверки числа на четность-нечетность связаны с информационным входом устройства управления. Повышена достоверность и производительности при тестировании чисел на простоту. 2 ил.

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

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

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

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

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

Технический результат достигается благодаря тому, что вычислительная система для тестирования чисел на простоту характеризуется тем, что включает в себя запоминающее устройство, инкрементор, блок вычисления N, блок деления, блок проверки числа на цел ость-дробность, блок проверки числа на четность-нечетность и устройство управления. При этом запоминающее устройство выполнено с возможностью хранения тестируемого числа, а блок вычисления N выполнен с возможностью вычисления выражения N_n=(n²-n)/2, где n - тестируемое число. Вход вычислительной системы связан с входом запоминающего устройства, выход запоминающего устройства связан с входом инкрементора, блока вычисления N и блока проверки числа на четность-нечетность, выход инкремептора связан с входом блока вычисления N, выход блока вычисления N связан с входом блока проверки числа на целость-дробность через блок деления и с входом блока проверки числа на четность-нечетность, выходы блока проверки числа на целость-дробность и блока проверки числа на четность-нечетность связаны с информационным входом устройства управления.

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

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

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

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

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

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

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

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

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

Запоминающее устройство 2 выполнено с возможностью хранения тестируемого числа, а блок 4 вычисления N выполнен с возможностью вычисления выражения N _n-(n₂-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. К вычислению N _n переходят, если проверка тестируемого числа в блоке 7 показала нечетность данного числа, в противном случае делают вывод, что тестируемое число является составным и устанавливают выходной логический уровень вычислительной системы 1 в состояние «0» при помощи устройства управления 8.

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

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

Вычислительная система для тестирования чисел на простоту характеризуется тем, что включает в себя запоминающее устройство, инкрементор, блок вычисления N, блок деления, блок проверки числа на целость-дробность, блок проверки числа на четность-нечетность и устройство управления, при этом запоминающее устройство выполнено с возможностью хранения тестируемого числа, а блок вычисления N выполнен с возможностью вычисления выражения N_n=(n ²-n)/2, где n - тестируемое число, а вход вычислительной системы связан с входом запоминающего устройства, выход запоминающего устройства связан с входом инкрементора, блока вычисления N и блока проверки числа на четность-нечетность, выход инкрементора связан с входом блока вычисления , выход блока вычисления N связан с входом блока проверки числа на целость-дробность через блок деления и с входом блока проверки числа на четность-нечетность, выходы блока проверки числа на целость-дробность и блока проверки числа на четность-нечетность связаны с информационным входом устройства управления.

РИСУНКИ