jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2020, Ali Mohammad Pur <mpfard@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#pragma once
8
9#include <AK/Random.h>
10#include <LibCrypto/BigInt/UnsignedBigInteger.h>
11
12namespace Crypto {
13namespace NumberTheory {
14
15UnsignedBigInteger ModularInverse(UnsignedBigInteger const& a_, UnsignedBigInteger const& b);
16UnsignedBigInteger ModularPower(UnsignedBigInteger const& b, UnsignedBigInteger const& e, UnsignedBigInteger const& m);
17
18// Note: This function _will_ generate extremely huge numbers, and in doing so,
19// it will allocate and free a lot of memory!
20// Please use |ModularPower| if your use-case is modexp.
21template<typename IntegerType>
22static IntegerType Power(IntegerType const& b, IntegerType const& e)
23{
24 IntegerType ep { e };
25 IntegerType base { b };
26 IntegerType exp { 1 };
27
28 while (!(ep < IntegerType { 1 })) {
29 if (ep.words()[0] % 2 == 1)
30 exp.set_to(exp.multiplied_by(base));
31
32 // ep = ep / 2;
33 ep.set_to(ep.divided_by(IntegerType { 2 }).quotient);
34
35 // base = base * base
36 base.set_to(base.multiplied_by(base));
37 }
38
39 return exp;
40}
41
42UnsignedBigInteger GCD(UnsignedBigInteger const& a, UnsignedBigInteger const& b);
43UnsignedBigInteger LCM(UnsignedBigInteger const& a, UnsignedBigInteger const& b);
44
45UnsignedBigInteger random_number(UnsignedBigInteger const& min, UnsignedBigInteger const& max_excluded);
46bool is_probably_prime(UnsignedBigInteger const& p);
47UnsignedBigInteger random_big_prime(size_t bits);
48
49}
50}