Лекции по синтаксису сложного предложения.

У виразі (крок 11) нарощується, якщо не є простим. Але, разом з тим, треба враховувати обмеження .

У кроці 12 можливість блокується переходом на побудову нового значення . Покажемо, що випадок неможливий.

Позначимо у виразі + (крок 9) перший доданок через , а другий доданок - через . Оцінемо розмір числа . Якщо число не є цілим, то = . Поділимо на з остачею. Це можна записати як , де та - цілі, .

Тоді . Але , звідки , тобто,

.

Оскільки, разом з тим, , а за побудовою, то .

Крім того, . Останнє потрібно, щоб врахувати присвоювання у п. 9.

Таким чином, двійковий запис числа має вигляд і містить серію нулів довжини, що практично дорівнює .

Аналогічно, для оцінки розміру числа запишемо , де та - цілі, . Оскільки , то . Кількість двійкових розрядів числа дорівнює . Якщо всі вони - одиниці, то відповідне значення є максимальним, тобто завжди . Тому , звідки: .

Очевидно, для виразу з п.11, для великого діапазону отримаємо , оскільки .

З цього випливає, що при додаванні чисел одиниця переносу зі старшого розяду суми виникне дуже рідко.

Таким чином, вихід числа на розрядність блокується у кроці 12 безпосередньою перевіркою, а чисел, що проходять перевірку, тобто мають розрядність , достатньо багато.

Тепер обгрунтуємо перевірку простоти числа .

Перепозначимо , де .

За теоремою Димитко, виконання умов кроку 13 достатньо для доведення простоти числа , якщо . Покажемо, що ця умова виконується.

Дійсно, якщо це не так, то , звідки: і . За кроком 12 алгоритма, , до того ж, , де . Тоді = , тобто, залежно від , , або , що є протиріччям.

На завершення приведемо процедуру С для побудови числа порядку за модулем - основи відкритого ключа цифрового підпису: .

1. Вибрати псевдовипадково число : .

2. Обчислити .

3. Якщо , перейти на крок 1, інакше, . Кінець процедури.

 

 

Лекции по синтаксису сложного предложения.