Есть ли способ генерации больших простых чисел на C# без использования внешней библиотеки?

Question

Мне нужно создать большие простые числа для криптографического проекта. Я заметил, что .NET 4.0 имеет встроенный криптографический примитив (например, RSA), который использует случайные генерируемые большие простые числа (p, q для RSA). Все ли они используют общую встроенную библиотеку, которая является общедоступной и может быть доступна извне их классов, или мне нужно использовать внешнюю библиотеку (я знаю, что существуют простые алгоритмы для тестов на первичность, я просто не хочу реализовать больше, чем я должен.).

Answer 1

В .NET v4 (и позже) Microsoft предоставляет новую сборку, System.Numerics.dll, которая включает в себя тип BigInteger. Однако он не предоставляет никакого способа проверки простых чисел.

Моно (начиная с версии 1.0) также предоставляет [BigInteger][3] тип, расположенный в нем Mono.Security.dll сборка. Вы можете либо использовать его , либо, либо перенести методы проверки правильности (существует несколько методов) на новый тип Microsoft BigInteger.

ли все они используют общую встроенную библиотеку, которая является общественной и могут быть доступны из-за пределы их класс областей

Да, как RSACryptoServiceProvider и DSACryptoServiceProvider вызовов в CryptoAPI, чтобы сделать это. Однако CAPI не предоставляет собственный код BigInteger (даже для собственного кода), поэтому он вам не поможет.

Answer 2

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

Для тестирования просто используйте пробное деление с простыми числами до, скажем, 1500, а затем переключитесь на Миллер-Рабин. С правильно реализованным Миллером-Рабином шансы на аппаратный сбой больше, чем ошибочно отмечая составной как простой.