信息安全数学基础第一阶段知识总结.pdf

"信息安全数学基础第一阶段知识总结" 以下是根据提供的文件信息生成的相关知识点： 整除的概念与欧几里得除法 * 整除的概念：设 a、b 是两个整数，其中 b≠0，如果存在一个整数 q 使得等式 a=bq 成立，就称 b 整除 a 或者 a 被 b 整除，记作 b|a，并把 b 叫作 a 的因数，把 a 叫作 b 的倍数。 * 整除的基本性质： 1. 当 b 遍历整数 a 的所有因数时，-b 也遍历整数 a 的所有因数。 2. 当 b 遍历整数 a 的所有因数时，a/b 也遍历整数 a 的所有因数。 3. 设 b,c 都是非零整数，(i)若 b|a，则 |b|≤|a|，(ii)若 b|a，则 bc|ac，(iii)若 b|a，则 1<|b|≤|a|。 整除的相关定理 * 设 a,b,c 是三个整数，若 c|b,b|a，则 c|a。 * 设 a,b,c 是三个整数，若 c|a,c|b，则 c|a±b。 * 设 a,b,c 是三个整数，若 c|a,c|b，则对任意整数 s,t，有 c|sa+tb。 * 若整数 a1,…,an 都是整数 c≠0 的倍数，则对任意 n 个整数s1,…,sn，整数Σns ai 是 c 的倍数。 最大公因数 * 最大公因数的概念定义：设 a,b 是两个整数，不存在一个整数 d，使得 d|a,d|b，且 d>=max(|a|,|b|)，则 d 叫做 a,b 的最大公因数，记作 (a,b)。 * 最大公因数的存在性： 1. 若 a,b 不都是零，则 a,b 有最大公因数。 2. 若 a,b 都是零，则任何整数都是它们的公因数。这时，它们没有最大公因数。 * 求两个正整数的最大公因数： + 定理 1：设 a,b 是两个正整数，则 exists q,r，使得 a=bq+r，0≤r<b。 + 定理 2： 任意两个正整数，存在整数 q，使得 a=bq+r，0≤r<b。 + 定理 3：任意两个正整数，存在整数 q，使得 a=bq+r，0≤r<b。 * 求两个以上正整数的最大公因数： + 定理 6：若只需证 a 是中最大一个例子。 最小公倍数 * 最小公倍数的定义：设 a,b 是两个整数，如果对于整数 c，存在整数 k,m，使得 c=ka=mb，则 c 叫做 a,b 的公倍数。在公倍数中最小的一个正整数，叫做最小公倍数，记作 [a,b]。 * 最小公倍数的性质： + 定理 1：设 a,b 是两个正整数，则 [a,b] 是 a,b 的最小公倍数。 + 定理 2：设 a,b 是两个正整数，则 [a,b] 是 a,b 的最小公倍数。 * 求两个以上整数的最小公倍数： + 定理 3：设 a,b 是两个正整数，则 [a,b] 是 a,b 的最小公倍数。 素数 * 素数的概念定义：一个大于 1 的整数，如果它的正因数只有 1 与它的本身，我们就称它为素数，否则就称为合数。 * 素数的性质： + 定理 1：设 n 是大于 1 的整数，则至少有一个素因数，并且当 n 是合数时，若 p 是它大于 1 的最小正因数，则 p 是素数。 + 定理 2：设 n 是正整数，如果对所有素数 p，n 不能被 p 整除，则 n 是素数。 * 素数的基本方法：爱拉托斯散筛法。