Encryption

1) Fermat's Little Theorem

Input

function pow(n,e,m){ if (e<=0) return 1n; let h = e/2n; let r = pow(n,h,m); r = (r*r) % m; if (e % 2n === 1n){ return (n * r) % m; } return r; } function modInverse(a, m){ a = (a % m + m) % m if (!a || m < 2n) { return NaN // invalid input } // find the gcd const s = [] let b = m while(b) { [a, b] = [b, a % b] s.push({a, b}) } if (a !== 1n) { return NaN // inverse does not exists } // find the inverse let x = 1n let y = 0n for(let i = s.length - 2; i >= 0; --i) { [x, y] = [y, x - y * (s[i].a / s[i].b)] } return (y % m + m) % m }

xxxxxxxxxx

 

1

function pow(n,e,m){

2

    if (e<=0) return 1n;

3

    let h = e/2n;

4

    let r = pow(n,h,m);

5

    r = (r*r) % m;

6

    if (e % 2n === 1n){

7

        return (n * r) % m;

8

    }

9

    return r;

10

}

11

​

12

function modInverse(a, m){

13

  a = (a % m + m) % m

14

  if (!a || m < 2n) {

15

    return NaN // invalid input

16

  }

17

  // find the gcd

18

  const s = []

19

  let b = m

20

  while(b) {

21

    [a, b] = [b, a % b]

22

    s.push({a, b})

23

  }

24

  if (a !== 1n) {

25

    return NaN // inverse does not exists

26

  }

27

  // find the inverse

28

  let x = 1n

29

  let y = 0n

30

  for(let i = s.length - 2; i >= 0; --i) {

31

    [x, y] = [y,  x - y * (s[i].a / s[i].b)]

32

  }

33

  return (y % m + m) % m

34

}

35

​

Go reset

Output

function pow(n,e,m){
    if (e<=0) return 1n;
    let h = e/2n;
    let r = pow(n,h,m);
    r = (r*r) % m;
    if (e % 2n === 1n){
        return (n * r) % m;
    }
    return r;
}

function modInverse(a, m){
  a = (a % m + m) % m
  if (!a || m < 2n) {
    return NaN // invalid input
  }
  // find the gcd
  const s = []
  let b = m
  while(b) {
    [a, b] = [b, a % b]
    s.push({a, b})
  }
  if (a !== 1n) {
    return NaN // inverse does not exists
  }
  // find the inverse
  let x = 1n
  let y = 0n
  for(let i = s.length - 2; i >= 0; --i) {
    [x, y] = [y,  x - y * (s[i].a / s[i].b)]
  }
  return (y % m + m) % m
}