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

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

1. Утворити два великих простих ${\displaystyle s}$ і ${\displaystyle t}$ приблизно однакової бітової довжини.
2. Обрати ціле ${\displaystyle i_{0}.}$ Знайти перше просте в послідовності ${\displaystyle 2it+1,}$ для ${\displaystyle i=i_{0},i_{0}+1,i_{0}+2,\dots .}$ Позначити це просте як ${\displaystyle r=2it+1.}$
3. Обчислити ${\displaystyle p_{0}=2(s^{r-2}modr)s-1.}$
4. Обрати ціле ${\displaystyle j_{0}.}$ Знайти перше ціле в послідовності ${\displaystyle p_{0}+2jrs,}$ для ${\displaystyle j=j_{0},j_{0}+1,j_{0}+2,\dots .}$ Позначити це просте як ${\displaystyle p=p_{0}+2jrs.}$
5. Повернути(p).

Обґрунтування: щоб побачити, що просте ${\displaystyle p}$ повернуте алгоритмом Гордона насправді сильне, зауважимо по-перше (припускаємо, що ${\displaystyle r\not =s}$), що ${\displaystyle s^{r-1}\equiv 1{\pmod {r}};}$ це випливає з теореми Ферма. Звідси, ${\displaystyle p_{0}\equiv 1{\pmod {r}}}$ і ${\displaystyle p_{0}\equiv {\pmod {s}}.}$ Зрештою,

1. ${\displaystyle p-1=p_{0}+2jrs-1\equiv 0{\pmod {r}},}$ і отже ${\displaystyle p-1}$ має простий дільник ${\displaystyle r}$;
2. ${\displaystyle p+1=p_{0}+2jrs+1\equiv 0{\pmod {s}},}$ і отже ${\displaystyle p+1}$ має простий дільник ${\displaystyle s}$; і
3. ${\displaystyle r-1=2it\equiv 0{\pmod {t}},}$ і отже ${\displaystyle r-1}$ має простий дільник ${\displaystyle t}$.