信息安全数学基础

创作时间:

2025-01-22 00:55:40

作者:

@小白创作中心

信息安全数学基础

这篇文章总结了信息安全数学基础中的一些基本概念，包括整数的可除性、整数的表示、最大公因数与广义欧几里得除法等内容。这些数论知识是信息安全领域的重要基础，对于学习和理解信息安全相关的算法和技术非常重要。

一、整数的可除性

1.整数的概念

1.1 整除
对于任意两个整数a和b，如果存在整数q使得a = bq，则称b整除a，或者a被b整除，其中b是偏小的一个，a是偏大的一个，记作b|a，b为a的因数，a为b的倍数。q常被写成a/b。

0是任何非零整数的倍数，1是任何整数的因数
任何非零整数a是其自身的倍数及因数
整数具有传递性

1.2 素数（质数/不可约数）
整数n≠0，±1.如果除了显然因数±1和±n外，n没有其他因数，那么n叫做素数（或质数，不可约数），否则为合数。素数有无数多个。

定理：设n是一个正合数，p是n的一个大于1的最小正因数，则p一定是素数，且p≦√n。

例如，n=20，p=5，5为素数。

1.3 欧几里得除法——最小非负余数
设a，b是两个整数，其中b>0，则存在唯一的整数q，r使得：
a = bq + r，0 ≦ r < b
q：a被b除所得的不完全商；r:a被b除所得的余数
[x]：x的整数部分为小于或等于x的最大整数，有：[x] ≦ x＜[x]+1，例如[4.99]=4≦ 4.99＜[x]+1=5
可以记q=[a/b]，r=a-q•b=a-[a/b]•b

1.4 素数的平凡判别
对于给定正整数N，设不大于√N的所有素数为p1，p2，···，ps.如果N被所有pi除的余数都不为零，即p不能整除n，1≦ i ≦ s，则N是素数。

1.5 欧几里得除法——一般余数
设a，b是两个整数，其中b＞0.则对任意的整数c，存在唯一的整数q，r使得：
a = bq + r，c ≦ r < b + c

2.整数的表示

2.1 b进制
这里已经基本理解，可以参考文章以及如下转换表：http://t.csdnimg.cn/2Nufj

3.最大公因数与广义欧几里得除法

3.1最大公因数
设a1，···，an是n(n≥2）个整数。若整数d是它们中每一个数的因数，则d就叫做a1，···，an的一个公因数，表达式为：
d|ai，1≦ i ≦ n
如果a1，···，an不全为零，那么整数a1，···，an的所有公因数中最大的一个公因数就叫做最大公因数，记作（a1，···，an）。
当（a1，···，an）=1时，称a1，···，an互素或互质。
d＞0是a1，···，an的最大公因数的数学表达式可叙述为：