Блог пользователя samuel.shokry12

Автор samuel.shokry12, история, 6 лет назад, По-английски

Hi, I have been reading this article Discrete log, I believe it relies on trying all the possible answers a^x mod m, where x belongs to [0, m[, but that requires that a^x mod m is cyclic somehow, where a^x mod with x >= m is equal to some a^j mod m, where j < m. I have tried some manual examples, and it seems that's the case. I guess it can be proven when m is prime using Fermat's Little Theorem, but don't know how to prove it for composite m. any suggestion?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

if $$$a$$$ and $$$m$$$ are coprime $$$a^x \equiv a^{x \bmod \phi (m)} \bmod m $$$ holds

Euler's theorem