Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Топ:
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2017-05-14 | 414 |
5.00
из
|
Заказать работу |
|
|
Простые числа
Простое число — это натуральное число, большее единицы, имеющее ровно два натуральных делителя: 1 и само себя.
Натуральное число, имеющее больше двух делителей, называют составным.
Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом.
Представление натурального числа в виде произведения простых чисел называется разложением на простые или факторизацией числа. На настоящий момент неизвестно полиномиальных алгоритмов факторизации чисел, хотя и не доказано, что таких алгоритмов не существует и поэтому на алгоритмической сложности задачи факторизации базируется многие криптосистемы.
Алгоритм «Решето Эратосфена» и его представление в FLINT\C
Алгоритм “Решето Эратосфена” является самым простым способом нахождения списка простых чисел до некоторого значения. Если необходимо составить таблицу всех простых чисел среди чисел 2, 3,..., N, то нужно вначале вычеркнуть все числа, делящиеся на 2, кроме 2. Затем взять число 3 и вычеркнуть все последующие числа, делящиеся на 3. Затем взять следующее невычеркнутое число (т. е. 5) и вычеркнуть все последующие делящиеся на него числа, и так далее. В итоге останутся лишь простые числа.
Генератор простых чисел (решето Эратосфена)
Синтаксис: ULONG * genprimes (ULONG N);
Вход: N (верхняя граница поиска)
Возврат: Указатель на вектор значений типа ULONG. содержащий простые числа, меньшие либо равные N. (На нулевой позиции - число найденных простых чисел) или
NULL,при ошибке процедуры выделения динамической памяти.
Вероятностный тест простоты (тест Миллера-Рабина)
|
На практике обычно возникает необходимость проверить, является ли число простым, а не получать список простых чисел.
Алгоритмы такого рода называются тестами простоты. Существует множество полиномиальных тестов простоты. Большинство таких алгоритмов являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии.
Вероятностный тест на простоту проводится следующим образом. Выбирается случайное a є N, 1 ≤ a <n, и для него проверяется выполнение некоторых условий. Если какое-то из условий не выполнено, то число п — составное, поскольку для простых чисел эти условия являются необходимыми. Если же все условия выполнены, то из этого еще не следует простота п. Однако можно будет считать, что «п — простое число с некоторой вероятностью». Чем больше значений a протестировано, тем ближе эта вероятность к единице.
Вероятностный тест Миллера-Рабина
Синтаксис: int prime_l (CLINT n, unsigned int a, unsigned int iter);
Вход: n (тестируемое число)
a >2 ((число простых чисел, на которое проверяется число n)
iter (число итераций теста)
Возврат: 1, если тестируемое число «вероятно» простое или
0, если тестируемое число составное или равно 1.
Пример реализации «Решета Эратосфена» и теста Миллера-Рабина
#include <FLINT.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>
#define ClintToStr xclint2str_l // Переопределение функции xclint2str_l
int main(int argc, char* argv[ ])
{
CLINT a; // Обьявление объекта CLINT
// Вероятностный тест Миллера-Рабина
char *sa =new char;sa="445";
str2clint_l (a,sa,10);//Инициализация строкой
printf("a= %s",ClintToStr(a,10,0));
ULONG N=1445;
int Test= prime_l (a, N, 1000); // тест
if(Test==1)printf(" -> Yes ");
else printf(" -> No ");
// Генератор простых чисел (решето Эратосфена)
ULONG M=3445;
ULONG * k= genprimes (M);// Генератор
int m= k[0];
printf("\n Search = %d\n",m);
for(int i=1;i<=m;i++) printf(" %d ",*(k+i));
getch(); return 0
Теоретико-числовые функции
Наибольший общий делитель
Наибольшим общим делителем (НОД) целых чисел а и b называется положительный делитель чисел а и b, делящийся на любой другой общий делитель этих чисел. Числа а и b называются взаимно-простыми, если НОД(a,b)=1. Классический алгоритм Евклида для вычисления наибольшего общего делителя, «дедушка» всех алгоритмов [Knut], использует повторное деление с остатком: вычисляется вычет a mod b, затем b mod (a mod b) и так далее, пока остаток не будет равен нулю. Например: НОД(21,12) =Н0Д(21 (mod 12), 12) = НОД (9,12) = НОД(12 (mod 9), 9) = НОД (3,9) = НОД (9 (mod3),3) = НОД (0,3) = 3.
|
Модифицированный, т.н. бинарный алгоритм Евклида вычисления НОД(а,b ) для a, b >0 реализован в виде следующей функции
Наибольший общий делитель (НОД)
Синтаксис: void gcd_l (CLINT a, CLINT b, CLINT c);
Вход: a, b (операнды)
Выход: c (наибольший общий делитель)
Таким образом, получаем представление наибольшего общего делителя g= НОД(a, b) =u×a+v×b ввиде линейной комбинации чисел а и b с целыми коэффициентами и и v, причем u по модулю ag и v по модулю bg определены однозначно. Если же для элемента выполняется условие НОД(а, n)= 1 = и× а + v× п, то отсюда сразу же следует и× a mod п или, что то же самое. В этом случае вычет и mod n определен однозначно.
Расширенный алгоритм Евклида вычисления линейного представления НОД(а, b ) = u • а + v • b для натуральных чисел a, b
Синтаксис void xgcd_l (CLINT a, CLINT b, CLINT g,CLINT u, int *sign_u, CLINT v, int *sign_v);
Вход: a, b (операнды)
Выход: g (наибольший общий делитель чисел а и b)
u, v (коэффициенты при а и b)
sign_u (знак коэффициента u)
sign_v (знак коэффициента v)
Наименьшее общее кратное
Наименьшее общее кратное (НОК) двух целых чисел a и b есть наименьшее целое число, которое делится на m и n. Обычно обозначается [a,b], а иногда НОК(a,b).
Наименьшее общее кратное двух чисел a, b равно частному от деления абсолютной величины произведения на наибольший общий делитель:
НОК(a,b ) НОД(a,b ) =|ab|. Это соотношением используется для вычисления НОК в следующей функции
|
|
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!