From useless to useful Lecture 10 Number Number theory is regarded as a beautiful but largely useless in the past theoretic Algorithn a Today number-theoretic algorithms are used videly 清华大学 Contents Basic Concepts ers整数 a Divisibility and divisor n Prime and composite numbers mN={0,123.} Natural numbers自然数 rd|a( d divides a)d整除a,存在整数k使得 a Greatest common divisors a=kd a Relative prime integers Divisor:约数 n Euclid algorithm and its complexity analysis a Trivia| divisor:平凡约数【举例】 n Modular arithmetic a Solving modular linear equation m素数【1,2,3,4那个是素数】 ■孙子定理【中国剩余数定理】 m合数【1,2,3,4那个是合数】 手大学想 与算法复杂度相关的概念 除法定理 ■整数的表示: 对任意整数a和正整数n,存在唯一整数q和r使 一进制 得0≤rcn,a=qn+r 二进制【十进制等】的长度作为一个整数的复 Quotient:【q】 杂度度量 a Remainder(residue【r】) s The function of Log*of n a fo(n)=n if i==0 zn={al:0≤a≤n1} fo(n)=f(fo(n) if i>0 [aln=a+kn: k in Z Ig n= mini=0: Ig(n)<=11 【[aJn的代表?】 大学证制1 清华大学 宋斌恒 1 Lecture 10. Number theoretic Algorithm 清华大学 宋斌恒 清华大学 宋斌恒 2 From useless to useful „ Number theory is regarded as a beautiful but largely useless in the past „ Today number-theoretic algorithms are used widely 清华大学 宋斌恒 3 Contents „ Basic concepts „ Divisibility and divisor „ Prime and composite numbers „ Division theorem „ Greatest common divisors „ Relative prime integers „ Unique factorization „ Euclid algorithm and its complexity analysis „ Modular arithmetic „ Solving modular linear equation „ 孙子定理【中国剩余数定理】 „ RSA 清华大学 宋斌恒 4 Basic Concepts „ Z={…,-2,-1,0,1,2,…} Integers 整数 „ N={0,1,2,3…} Natural numbers 自然数 „ d|a (d divides a) d整除a， 存在整数k使得 a=kd „ Divisor: 约数 „ Trivial divisor：平凡约数【举例】 „ 素数【1，2，3，4那个是素数】 „ 合数【1，2，3，4那个是合数】 清华大学 宋斌恒 5 与算法复杂度相关的概念 „ 整数的表示： „ 一进制 „ 二进制【十进制等】的长度作为一个整数的复 杂度度量。 „ The function of “Log * of n” „ f (i)(n)=n if i==0 „ f (i)(n)=f(f(i)(n)) if i>0 „ lg* n = min{i>=0: lg(i)(n)<=1} 清华大学 宋斌恒 6 除法定理 „ 对任意整数a和正整数n，存在唯一整数q和r使 得 0≤r<n, a=qn+r „ Quotient:【q】 „ Remainder (residue 【r】) „ Zn ={[a]n: 0≤a≤n-1} „ [a]n ={a+kn: k in Z} „ 【 [a]n的代表？】