鬼谷算题 解答 ■在鬼谷算题中有这样一个著名的题目:“今有物 m3个一排余2 不知其数,三三数之剩二,五五数之剩三,七 m5个一排余3 七数之剩二,问物几何?” m7个一排余2 ■我国宋代学者对这类题目钻研己颇为精深,总 结出了“三人同行七十稀,五树梅花廿一枝,七 ■【2】×70+【3】×21+【2】×15-105= 子团圆正半月,去百零五便得知。”这样的口 诀,意思是说“以三三数之,余数乘以七十:五 三人同行70稀,五树梅花廿一支,七子团圆正半 五数之,余数乘以二十一:七七数之,余数乘 月,抛五去百便得知 十五。三者相加,如不大于一百零五,即为答 数:否则须减去一百零五或其倍数。 清手大学城想 利用公式求基本解 元素的幂 35×(35-1mod3)=70 a 3 mod 7 21×(21-1mod5)=21 a Eulers theorem 15×(15-1mod7)=15 For any integer n >1 m更多内容参见论文《中国剩余定理》 a≡1(modn) for all a in Z 数学研究所李文林袁向东 a Fermat's theorem .a-1=1(mod p)for all a in zp 如何计算a(modn)?见下页 手大学想 MODULAR EXPONENTIATION(a, b, n) 密码学 c←0 明文m <bk,-.bo> be the binary rep. of b for i+k downto 0 tc←2c 解密函数D ae=Em),要求 d-(d·a)modn a m=Dk(e) return d 【复杂度?】 大学证制4 清华大学 宋斌恒 19 鬼谷算题 „ 在鬼谷算题中有这样一个著名的题目：“今有物 不知其数，三三数之剩二，五五数之剩三，七 七数之剩二，问物几何?” „ 我国宋代学者对这类题目钻研已颇为精深，总 结出了“三人同行七十稀，五树梅花廿一枝，七 子团圆正半月，去百零五便得知。”这样的口 诀，意思是说“以三三数之，余数乘以七十；五 五数之，余数乘以二十一；七七数之，余数乘 十五。三者相加，如不大于一百零五，即为答 数；否则须减去一百零五或其倍数。 清华大学 宋斌恒 20 解答 „ 3个一排余2、 „ 5个一排余3、 „ 7个一排余2、 „ 【2】×70＋【3】×21＋【2】×15－105＝ 128 „ 三人同行70稀, 五树梅花廿一支, 七子团圆正半 月, 抛五去百便得知 。 清华大学 宋斌恒 21 利用公式求基本解 „ 35×（35－1 mod 3）＝70 „ 21×（21－1 mod 5）＝21 „ 15×（15－1 mod 7）＝15 „ 更多内容参见 论文《中国剩余定理》 „ 数学研究所 李文林 袁向东 清华大学 宋斌恒 22 元素的幂 „ 3i mod 7 „ Euler’s theorem: „ For any integer n >1. „ aφ(n) ≡ 1 (mod n) for all a in Z* n . „ Fermat’s theorem: „ ap-1 ≡ 1 (mod p ) for all a in Z* p. „ 如何计算 ab (mod n)？见下页 清华大学 宋斌恒 23 MODULAR￾EXPONENTIATION(a,b,n) 1 c←0 2 d ←1 3 let <bk,…b0> be the binary rep. of b 4 for i ← k downto 0 1 c ← 2c 2 d ← (d • d) mod n 3 if bi = 1 then 1 c ← c + 1 2 d ← (d • a) mod n 5 return d 【复杂度？】 清华大学 宋斌恒 24 密码学 „ 对称加密： „ 明文 m „ 密文 e „ 密钥 k „ 加密函数 Ek： „ 解密函数 Dk： „ e=Ek(m), 要求 „ m=Dk(e) „ Dk Ek=I