Cтраница 3
В программе следует применять тест Миллера ( по основанию Ь) ко всем составным нечетным числам до тех пор, пока Вы не получите сообщения о неопределенном ответе. Разумеется, область поиска будет ограничена наибольшим целым числом К, поддерживаемым языком программирования, который Вы выбрали. Ваша программа должна выдавать два возможных результата: наименьшее строго псевдопростое число по основанию b или сообщение: строго псевдопростых чисел по основанию Ь, меньших К, не существует. Чтобы найти все нечетные составные числа, меньшие К, можете использовать решето Эратосфена. [31]
Интересно, что до наших дней находятся энтузиасты, продолжающие ломать голову над такими формулами. Никто из них не доказал, что, во-первых, приведенные формулы позволяют выудить из натурального ряда все простые числа, а во-вторых, что все числа, полученные по этим формулам, простые. Пока этого не будет сделано, остается примириться с фактом, что аналитического решения проблемы не существует, и пользоваться алгоритмами, подобными решету Эратосфена. [32]
Содержание этой главы более явно связано с нашей конечной целью - USA-криптосистемой. В самом деле, для уверенности в безопасности реализации RSA мы должны уметь подбирать большие простые числа: по два для каждого пользователя. В настоящей главе мы приступаем к решению этой задачи. Сначала рассмотрим простые числа, получающиеся из полиномиальных, экспоненциальных и праймориальных формул. Глава заканчивается обсуждением решета Эратосфена - старейшего из известных методов нахождения простых чисел и прародителя всех современных решет. [33]