165
правок
Изменения
→Доказательство теоремы
*Обозначим за <tex>x^{(1)} \ldots x^{(D)}</tex> все выполняющие наборы формулы <tex>\phi</tex>. Заметим, что их число, обозначенное как <tex>D</tex>, нам неизвестно (но не превосходит 2<sup>''n''</sup>).
*Равенство <tex>i = \lceil \log_2 D \rceil</tex> выполняется с вероятностью 1/(<tex>n</tex>+1), так как <tex>i</tex> было выбрано из [0..<tex>n</tex>]. Предположим, что это соотношение верно.
*Для некоторых <tex>x^{(j)}</tex> и <tex>x^{(h)}</tex> при условии несовпадения <tex>j</tex> и <tex>h</tex> имеется не более <tex>n</tex> простых делителей разности <tex>x^{(j)} - x^{(h)}</tex>, так как <tex>x^{(j)}</tex> и <tex>x^{(h)}</tex> не превосходят 2<sup>''n''</sup>.
==Внешние ссылки==
