text: Найдем k ∈ Z {\displaystyle k\in \mathbb {Z} } такое, что p = r i + k ⋅ q {\displaystyle p=r_{i}+k\cdot q} , p {\displaystyle p} - простое P {\displaystyle P} -битовое число и при этом p ≡ 2 mod 3 {\displaystyle p\equiv 2\ {\text{mod}}\ 3} для i ∈ { 1 , 2 } {\displaystyle i\in \{1,2\}} Корректность Алгоритма Б: Как только мы выбираем q ≡ 7 mod 12 {\displaystyle q\equiv 7\ {\text{mod}}\ 12} , автоматически выполняется условие q ≡ 1 mod 3 {\displaystyle q\equiv 1\ {\text{mod}}\ 3} (Так как 7 ≡ 1 mod 3 {\displaystyle 7\equiv 1\ {\text{mod}}\ 3} и 3 ∣ 12 {\displaystyle 3\mid 12} ).