308
правок
Изменения
Нет описания правки
<tex>y \equiv (al+b)</tex> <tex>mod</tex> <tex>p</tex> <tex>mod</tex> <tex>m</tex>
<tex>x \equiv ak+b+im- y = a(k - l)</tex> <tex>mod</tex> <tex>\pmod p</tex> <tex>mod</tex> <tex>m</tex>
Теперь сначала первое домножим на <tex>y \equiv al+b+jml</tex> , и второе на <tex>\pmod pk</tex>,. Вычитаем:
<tex>x lx - y ky \equiv ab(l - k - l)+jm</tex> <tex>mod</tex> <tex>p</tex> <tex>\pmod mp</tex>,
Стоит отметить, что эти равенства мы считаем выполненными, если при данных <tex>lx - ky \equiv a, b(l - k), x</tex> и <tex>mody</tex> и '''каких-либо''' <tex>pi</tex> и <tex>\pmod mj</tex>они будут верными.
<tex>k \ne l</tex>, <tex>p</tex> {{---}} простое, тогда
<tex>a \equiv (k - l)^{-1}(x - y - im)</tex> <tex>\pmod p</tex>
<tex>b \equiv (l - k)^{-1}(lx - ky - jm)</tex> <tex>\pmod p</tex>
Теперь заметим, что <tex>a</tex> принимает <tex>p</tex> различных значений, а <tex>i</tex> {{---}} <tex dpi = "130">\lfloor \frac{p}{m} \rfloor</tex> значений. Понятно, что для заданных <tex>x, y</tex> и <tex>a</tex> с вероятностью лишь <tex dpi = "130"> \frac{1}{m} </tex> найдётся <tex>i</tex>, обращающий равенство в тождество; аналогично и со вторым равенством.
Остаётся подытожить наши выкладки.
<tex>P( [x \equiv (ak+b)</tex> <tex>mod</tex> <tex>p</tex> <tex>mod</tex> <tex>m]</tex> <tex>\wedge</tex> <tex>[y \equiv (al+b)</tex> <tex>mod</tex> <tex>p</tex> <tex>mod</tex> <tex>m])</tex>
<tex>=</tex>
<tex>=</tex>
<tex>P( [a \equiv (k - l)^{-1}(x - y - im)</tex> <tex>\pmod p]</tex> <tex>\wedge</tex> <tex>[a \equiv (k - l)^{-1}(x - y - im)</tex> <tex>\pmod p])</tex>
<tex>=</tex>
<tex>=</tex>
<tex>P( a \equiv (k - l)^{-1}(x - y - im)</tex> <tex>\pmod p)</tex> <tex>\cdot</tex> <tex>P(a \equiv (k - l)^{-1}(x - y - im)</tex> <tex>\pmod p)</tex>
<tex>=</tex>
<tex>=</tex>
<tex dpi = "130">\frac{1}{m} \cdot \frac{1}{m} = \frac{1}{m^2}</tex>
Переход к третьей строчке объясняется тем, что события, объединённые знаком <tex>\wedge</tex>, независимы.
}}
