Function
Static Public Summary | ||
public |
modN(r: *, N: *, x: *): * |
|
public |
modR(k: *, x: *): * |x| >= k |
Static Private Summary | ||
private |
|
|
private |
|
|
private |
_montgomery(b: Number, N: Array): {"k": *, "M": *, "R": *, "R2": *, "R3": *} N has no leading zeroes |
|
private |
_mul(r: *, N: *, M: *, a: *, b: *, c: *): * abR mod N = REDC((aR mod N)(bR mod N)) |
|
private |
Function REDC is |
Static Public
public modN(r: *, N: *, x: *): * source
import modN from '@arithmetic-operations-for/integers-modulo-n-big-endian/src/modN.js'
Params:
Name | Type | Attribute | Description |
r | * | ||
N | * | ||
x | * |
Return:
* |
public modR(k: *, x: *): * source
import modR from '@arithmetic-operations-for/integers-modulo-n-big-endian/src/modR.js'
|x| >= k
Params:
Name | Type | Attribute | Description |
k | * | ||
x | * |
Return:
* |
Static Private
private _iadd(r: Number, N: Array, a: Array, b: Array): boolean source
import _iadd from '@arithmetic-operations-for/integers-modulo-n-big-endian/src/_iadd.js'
Params:
Name | Type | Attribute | Description |
r | Number | the radix |
|
N | Array | number array of length k. |
|
a | Array | ||
b | Array | (a+b)R mod N = aR mod N + bR mod N - ( 0/1 * N ) R = r^k N has no leading zeroes N has length k |N| = |a| >= |b| |a| = |b| if you want to avoid side channel attacks a < N b < N t = a + b mod r^k if t < b or t >= N then return t - N mod r^k else return t // Can subtract dummy zero vector here in case we want // to avoid side channel attacks |
private _isub(r: Number, N: Array, a: Array, b: Array): boolean source
import _isub from '@arithmetic-operations-for/integers-modulo-n-big-endian/src/_isub.js'
Params:
Name | Type | Attribute | Description |
r | Number | the radix |
|
N | Array | number array of length k. |
|
a | Array | ||
b | Array | (a+b)R mod N = aR mod N - bR mod N + ( 0/1 * N ) R = r^k N has no leading zeroes N has length k |N| = |a| >= |b| |a| = |b| if you want to avoid side channel attacks a < N b < N t = a - b mod r^k if a < b then return t + N mod r^k else return t // Can add dummy zero vector here in case we want // to avoid side channel attacks |
private _montgomery(b: Number, N: Array): {"k": *, "M": *, "R": *, "R2": *, "R3": *} source
import _montgomery from '@arithmetic-operations-for/integers-modulo-n-big-endian/src/_montgomery.js'
N has no leading zeroes
Return:
{"k": *, "M": *, "R": *, "R2": *, "R3": *} |
private _mul(r: *, N: *, M: *, a: *, b: *, c: *): * source
import _mul from '@arithmetic-operations-for/integers-modulo-n-big-endian/src/_mul.js'
abR mod N = REDC((aR mod N)(bR mod N))
|N| >= |a| >= |b| |c| = 2*|N| + 1 c = 0000.0000 is zero initialized
Params:
Name | Type | Attribute | Description |
r | * | ||
N | * | ||
M | * | ||
a | * | ||
b | * | ||
c | * |
Return:
* |
private _redc(b: *, k: *, N: *, Ni: *, Nj: *, M: *, Mi: *, Mj: *, T: *, Ti: *, Tj: *): boolean source
import _redc from '@arithmetic-operations-for/integers-modulo-n-big-endian/src/_redc.js'
Function REDC is
input: Integers R = b^k > N with gcd(R, N) = 1, Integer M in [0, R − 1] such that NM ≡ −1 mod R, Integer T in the range [0, RN − 1]
All numbers are given in base b (big endian order).
output: Integer S in the range [0, N − 1] such that S ≡ TR−1 mod N
m ← ((T mod R)M) mod R // Can be implemented by discarding limbs t ← (T + mN) / R // Can be implemented with a shift // /!\ T + mN is potentially RN - 1 + (R-1) N = 2RN - N - 1 so need one // extra limb for carry ? if t ≥ N then return t − N else return t // Can add dummy - zero vector here in case we want to avoid side // channel attacks end if end function
Params:
Name | Type | Attribute | Description |
b | * | ||
k | * | ||
N | * | ||
Ni | * | ||
Nj | * | ||
M | * | ||
Mi | * | ||
Mj | * | ||
T | * | ||
Ti | * | ||
Tj | * |