Chapter 8-Number Theory

数论基础总结，密码理论与技术中的“Chapter 8-Number Theory”指的是数论入门，它是密码学中的核心概念之一。

Chapter 8-Number Theory

• Prime number
  • prime numbers only have divisors of 1 and self
  • factor
    • factoring a number is relatively hard compared to multiplying the factors
  • prime factorisation
    • is when its written as a product of primes
  • relatively Prime Numbers (coprime)
    • if the have no common divisors apart from 1
    • Conversely, can determine the GCD by comparing their prime factorizations and using least powers
• Fermat's Theorem
  • 
  • • 注意
      • 1. 这里的a是一个与p互质的数，所以乘a后再mod p会得到一个新的关于1~p-1的序列，可能不是顺序的
      • 2.(p-1)!与p户为指数是因为1~p-1都与p互为质数
      • 3.(p-1)!与p互为质数所以可以约掉是因为
        • 模p运算中可以“约去”一个与p互质的数
        • ie 这个数与p互质说明它在模p运算中必定有一个逆元，在mod p运算中可以同时乘以这个逆元在模p中结果为1
• Chinese Remainder Theorem(CRT)
  • 用来加速模运算
• Euler
  • Euler Totient Function
    • def
      • complete set of residues
        • 0....n-1
      • reduced set of residues
        • is numbers(residues) which are relatively prime to n
      • Euler Totient Function 
        • number of elements in reduced set of residues
        • 上面的例子里 
    • computation
      • 
  • Euler's Theorem
    • def
      • 
• Prime Distribution
  • 每隔ln(n)出现一次
  • 想找到一个大小为n的素数，只需要测试大约0.5ln(n)个数字，因为素数在技术中的分布要比在所有整数中更密集，可以忽略偶数
• Primality Testing(素数测试)
  • Trial Division(试除法)
    • 通过将一个数与所有小于它的平方根的素数进行除法运算来检验它是否为素数。
    • 只适用于较小的数
  • Statistical Primality test(统计素性检验)
    • based on properties that all prime numbers satisfy property
    • but some composit number(合数), called pseudo-prmes(伪素数), also satisfy the property
    • 适用于大数
    • example
      • Miller Rabin Algorithm
        • 基于费马小定理和素数性质
        • 
        • 
        • 如果多次测试中n都没有被判定为荷属，那可以对n是素数越来越有信心，但不能确定
  • slower Deterministic Primality Test(慢速的确定性素性检验)
  • AKS也是确定性素性检验