skip to content

🔢余数

#数学#Basic

前置知识

余数总是在一个固定的范围内。

整数是没有边界的，它可能是正无穷，也可能是负无穷。但是余数却可以通过某一种关系，让整数处于一个确定的边界内。

同余定理：简单来说，就是两个整数 a 和 b，如果它们除以正整数 m 得到的余数相等，我们就可以说 a 和 b 对于模 m 同余。

还有，我们经常提到的奇数和偶数，其实也是同余定理的一个应用。当然，这个应用里，它的模就是 2 了，2 除以 2 余 0，所以它是偶数；3 除以 2 余 1，所以它是奇数。2 和 4 除以 2 的余数都是 0，所以它们都是一类，都是偶数。3 和 5 除以 2 的余数都是 1，所以它们都是一类，都是奇数。

简单来说， 同余定理其实就是用来分类的 。你知道，我们有无穷多个整数，那怎么能够全面、多维度地管理这些整数？同余定理就提供了一个思路。

因为不管你的模是几，最终得到的余数肯定都在一个范围内。比如我们上面除以 7，就得到了星期几；我们除以 2，就得到了奇偶数。所以按照这种方式, 我们就可以把无穷多个整数分成有限多个类。

哈希

哈希有的时候也会被翻译为散列，简单来说，它就是 将任意长度的输入，通过哈希算法，压缩为某一固定长度的输出

公式

在这个公式中，x 表示等待被转换的数值，而 size 表示有限存储空间的大小，mod 表示取余操作。 通过余数，你就能将任何数值，转换为有限范围内的一个数值，然后根据这个新的数值，来确定将数据存放在何处。

让我以加密算法为例，举个例子，比如说我们要加密一组三位数，那我们设定一个这样的加密规则：

  1. 先对每个三位数的个、十和百位数，都加上一个较大的随机数
  2. 然后将每位上的数都除以 7，用所得的余数代替原有的个、十、百位数
  3. 最后将第一位和第三位交换。
// 加密
const hashEncrypt = (value, salt) => {
  let valueList = String(value)
    .split('')
    .map(item => +item)
  let result = valueList.map(item => {
    let quotient = Math.floor((item + salt) / 7)
    let rem = (item + salt) % 7
    return {
      quotient,
      rem
    }
  })
  let encryptValue = +result
    .map(item => item.rem)
    .reverse()
    .join('')
  let iv = result.map(item => item.quotient)
  return {
    encryptValue,
    iv
  }
}

// 解密
const hashDecrypt = (value, iv, salt) => {
  let valueList = String(value)
    .split('')
    .reverse()
    .map(item => +item)
  let result = valueList.map((item, index) => {
    return iv[index] * 7 + item - salt
  })
  let decryptValue = +result.join('')
  return decryptValue
}

let testValue = 751
let salt = 4523645
let { encryptValue, iv } = hashEncrypt(testValue, salt)
let decryptValue = hashDecrypt(encryptValue, iv, salt)
上一篇
迭代法