1%% -*- mode: erlang; tab-width: 4; indent-tabs-mode: 1; st-rulers: [70] -*-
2%% vim: ts=4 sw=4 ft=erlang noet
3%%%-------------------------------------------------------------------
4%%% @author Andrew Bennett <potatosaladx@gmail.com>
5%%% @copyright 2014-2016, Andrew Bennett
6%%% @doc
7%%%
8%%% @end
9%%% Created :  06 Jan 2016 by Andrew Bennett <potatosaladx@gmail.com>
10%%%-------------------------------------------------------------------
11-module(jose_jwa_math).
12
13%% Public API
14-export([expmod/3]).
15-export([exprem/3]).
16-export([intpow/2]).
17-export([mod/2]).
18-export([mod_pow/3]).
19
20%% Private API
21-export([expmod_fast/3]).
22-export([expmod_slow/3]).
23-export([exprem_fast/3]).
24-export([exprem_slow/3]).
25
26%%====================================================================
27%% Public API
28%%====================================================================
29
30expmod(B, E, M) ->
31	expmod_fast(B, E, M).
32
33exprem(B, E, M) ->
34	exprem_fast(B, E, M).
35
36intpow(B, E) when is_integer(B) andalso is_integer(E) andalso E >= 0 ->
37	case B of
38		0 ->
39			0;
40		1 ->
41			1;
42		2 ->
43			1 bsl E;
44		_ ->
45			intpow(B, E, 1)
46	end.
47
48mod(B, M) ->
49	(B rem M + M) rem M.
50
51mod_pow(B, E, M) ->
52	Bytes = crypto:mod_pow(B, E, M),
53	Size = byte_size(Bytes),
54	<< ((crypto:bytes_to_integer(Bytes) + M) rem M):Size/signed-big-integer-unit:8 >>.
55
56%%====================================================================
57%% Private API
58%%====================================================================
59
60% @private
61expmod_fast(B, E, M) ->
62	(exprem_fast(B, E, M) + M) rem M.
63
64% @private
65expmod_slow(B, E, M) ->
66	(exprem_slow(B, E, M) + M) rem M.
67
68% @private
69exprem_fast(B, E, M) when B < 0 andalso E rem 2 =/= 0 ->
70	-exprem_fast(abs(B), E, M);
71exprem_fast(B, E, M) when B < 0 ->
72	exprem_fast(abs(B), E, M);
73exprem_fast(B, E, M) ->
74	crypto:bytes_to_integer(crypto:mod_pow(B, E, M)).
75
76%% @private
77exprem_slow(_B, 0, _M) ->
78	1;
79exprem_slow(B, E, M) ->
80	T0 = exprem_slow(B, E div 2, M),
81	T = (T0 * T0) rem M,
82	case E rem 2 of
83		0 ->
84			T band M;
85		_ ->
86			(T * B) rem M
87	end.
88
89%%%-------------------------------------------------------------------
90%%% Internal functions
91%%%-------------------------------------------------------------------
92
93%% @private
94intpow(B, E, R) when (E rem 2) =:= 0 ->
95	intpow(B * B, E div 2, R);
96intpow(B, E, R) when (E div 2) =:= 0 ->
97	B * R;
98intpow(B, E, R) ->
99	intpow(B * B, E div 2, B * R).
100