www.wikidata.uk-ua.nina.az

Сильне просте число англ strong prime це просте число з певними особливими властивостями Визначення сильного простого чи

Сильне просте число

Сильне просте число (англ. strong prime) — це просте число з певними особливими властивостями. Визначення сильного простого числа різниться в криптографії і теорії чисел.

Визначення в криптографії ред.

В криптографії, просте число є сильним, якщо виконуються такі умови.

  1. має великий простий дільник ;
  2. має великий простий дільник ;
  3. має великий простий дільник .

Іноді просте число, яке задовольняє підмножині наведених умов, також називається сильним.

Алгоритм Гордона для генерації сильних простих чисел ред.

Алгоритм генерує сильне просте число.

  1. Утворити два великих простих і приблизно однакової бітової довжини.
  2. Обрати ціле Знайти перше просте в послідовності для Позначити це просте як
  3. Обчислити
  4. Обрати ціле Знайти перше ціле в послідовності для Позначити це просте як
  5. Повернути(p).

Обґрунтування: щоб побачити, що просте повернуте алгоритмом Гордона насправді сильне, зауважимо по-перше (припускаємо, що ), що це випливає з теореми Ферма. Звідси, і Зрештою,

  1. і отже має простий дільник ;
  2. і отже має простий дільник ; і
  3. і отже має простий дільник .

Визначення в теорії чисел ред.

В теорії чисел, просте число є сильним, якщо воно більше ніж середнє арифметичне найближчих простих згори і знизу (інакше кажучи, воно ближче до наступного ніж до попереднього). Або алгебраїчно, дано просте число , де n його індекс у впорядкованій множині простих чисел, . Перші кілька простих чисел такі

Наприклад, 17 — це сьоме просте число. Шосте і восьме, 13 і 19, їхня сума становить 32, половина 16. Тобто 17 — сильне просте.

В двійках простих чисел близнюків (p, p + 2) з p > 5, p завжди сильне просте, бо 3 повинно ділити p − 2, тобто p − 2 не просте.

Примітки ред.

  1. Ron Rivest and Robert Silverman, Are 'Strong' Primes Needed for RSA?, Cryptology ePrint Archive: Report 2001/007. http://eprint.iacr.org/2001/007
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Silne proste chislo angl strong prime ce proste chislo z pevnimi osoblivimi vlastivostyami Viznachennya silnogo prostogo chisla riznitsya v kriptografiyi i teoriyi chisel Zmist 1 Viznachennya v kriptografiyi 1 1 Algoritm Gordona dlya generaciyi silnih prostih chisel 2 Viznachennya v teoriyi chisel 3 PrimitkiViznachennya v kriptografiyi red V kriptografiyi proste chislo p displaystyle p nbsp ye silnim yaksho vikonuyutsya taki umovi 1 p 1 displaystyle p 1 nbsp maye velikij prostij dilnik r displaystyle r nbsp p 1 displaystyle p 1 nbsp maye velikij prostij dilnik s displaystyle s nbsp r 1 displaystyle r 1 nbsp maye velikij prostij dilnik t displaystyle t nbsp Inodi proste chislo yake zadovolnyaye pidmnozhini navedenih umov takozh nazivayetsya silnim Algoritm Gordona dlya generaciyi silnih prostih chisel red Algoritm generuye silne proste chislo Utvoriti dva velikih prostih s displaystyle s nbsp i t displaystyle t nbsp priblizno odnakovoyi bitovoyi dovzhini Obrati cile i 0 displaystyle i 0 nbsp Znajti pershe proste v poslidovnosti 2 i t 1 displaystyle 2it 1 nbsp dlya i i 0 i 0 1 i 0 2 displaystyle i i 0 i 0 1 i 0 2 dots nbsp Poznachiti ce proste yak r 2 i t 1 displaystyle r 2it 1 nbsp Obchisliti p 0 2 s r 2 m o d r s 1 displaystyle p 0 2 s r 2 modr s 1 nbsp Obrati cile j 0 displaystyle j 0 nbsp Znajti pershe cile v poslidovnosti p 0 2 j r s displaystyle p 0 2jrs nbsp dlya j j 0 j 0 1 j 0 2 displaystyle j j 0 j 0 1 j 0 2 dots nbsp Poznachiti ce proste yak p p 0 2 j r s displaystyle p p 0 2jrs nbsp Povernuti p Obgruntuvannya shob pobachiti sho proste p displaystyle p nbsp povernute algoritmom Gordona naspravdi silne zauvazhimo po pershe pripuskayemo sho r s displaystyle r not s nbsp sho s r 1 1 mod r displaystyle s r 1 equiv 1 pmod r nbsp ce viplivaye z teoremi Ferma Zvidsi p 0 1 mod r displaystyle p 0 equiv 1 pmod r nbsp i p 0 mod s displaystyle p 0 equiv pmod s nbsp Zreshtoyu p 1 p 0 2 j r s 1 0 mod r displaystyle p 1 p 0 2jrs 1 equiv 0 pmod r nbsp i otzhe p 1 displaystyle p 1 nbsp maye prostij dilnik r displaystyle r nbsp p 1 p 0 2 j r s 1 0 mod s displaystyle p 1 p 0 2jrs 1 equiv 0 pmod s nbsp i otzhe p 1 displaystyle p 1 nbsp maye prostij dilnik s displaystyle s nbsp i r 1 2 i t 0 mod t displaystyle r 1 2it equiv 0 pmod t nbsp i otzhe r 1 displaystyle r 1 nbsp maye prostij dilnik t displaystyle t nbsp Viznachennya v teoriyi chisel red V teoriyi chisel proste chislo ye silnim yaksho vono bilshe nizh serednye arifmetichne najblizhchih prostih zgori i znizu inakshe kazhuchi vono blizhche do nastupnogo nizh do poperednogo Abo algebrayichno dano proste chislo p n displaystyle p n nbsp de n jogo indeks u vporyadkovanij mnozhini prostih chisel p n gt p n 1 p n 1 2 displaystyle p n gt p n 1 p n 1 over 2 nbsp Pershi kilka prostih chisel taki 11 17 29 37 41 59 67 71 79 97 101 107 127 137 149 163 179 191 197 223 227 239 251 269 277 281 307 311 331 347 367 379 397 419 431 439 457 461 479 487 499 poslidovnist A051634 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Napriklad 17 ce some proste chislo Shoste i vosme 13 i 19 yihnya suma stanovit 32 polovina 16 Tobto 17 silne proste V dvijkah prostih chisel bliznyukiv p p 2 z p gt 5 p zavzhdi silne proste bo 3 povinno diliti p 2 tobto p 2 ne proste Primitki red Ron Rivest and Robert Silverman Are Strong Primes Needed for RSA Cryptology ePrint Archive Report 2001 007 http eprint iacr org 2001 007 Otrimano z https uk wikipedia org w index php title Silne proste chislo amp oldid 20481961