「Cryptography-MIT6875」: Lecture 6 - Number Theory

In this series, I will learn MIT 6.875, Foundations of Cryptography, lectured by Vinod Vaikuntanathan.
Any corrections and advice are welcome. ^ - ^
The motif of this blog is Number Theory, including the second half of Lecture 5 and the Lecture 6.

It’s an excellent opportunity to learn Number Theory in manner of English.

An important point in this blog is that we focus more on the statements, which is useful in later lectures, rather than the proof.

About 70% of the content in this blog is originally and literally from the lecture notes. I just organize and refine it according to the logic of the professor’s narration since the lecture note is awesome.

The rest is my own understanding and derivation of some theorems. And I will be learning Number Theory and completing the omitted proof.

So this blog will be updated continuously.

Topics covered:

  • Groups, Order of a group and the Order of an element, Cyclic Groups.
  • The Multiplicative Group $\mathbb{Z}_N^*$ and $\mathbb{Z}_P^*$ for a prime $P$.
  • Generators of $\mathbb{Z}_P^*$.
  • Primes, Primality Testing.
  • The Discrete Logarithm (DLOG) problem and a candidate OWF.
  • Diffie-Hellman assumptions: DDH and CDH.

「Math」:Mersenne Prime

在密码学中,有限域中的运算性能极大影响密码协议的实现。

如果有限域选择梅森素数,得益于它的优良性质,可以极大提高运算效率,特别是有限域下的模运算、乘法操作。

于是近日学习了梅森素数的相关性质,以及如何约减梅森素数域下模运算和乘法运算。