Thin layer on top of the li module that provides mutable signed
integers with basic modular arithmetic along with a few low level
routines that requires signed integers to implement.
It also provides a minimal container class SLI that represents a
signed integer. All operations on are executed on pre-existing SLI
instances, so it is the responsibility of the programmer to ensure
that data fits inside the allocated space.
This approach is motivated by the need to preserve efficiency and
still encapsulate as much implementation details as possible.
- Source:
Classes
- SLI
Methods
(static) add(a, b, c)
Sets a = b + c.
ASSUMES: b and c have B and B' bits and a can store B + B' + 1
bits, or B + B' bits depending on if the signs of b and c are equal
or not.
Parameters:
| Name |
Type |
Description |
a |
|
SLI holding the result. |
b |
|
Left term. |
c |
|
Right term. |
- Source:
(static) cmp(a, b)
Returns -1, 0, or 1 depending on if a < b, a == b, or
a > b.
Parameters:
| Name |
Type |
Description |
a |
|
Left SLI. |
b |
|
Right SLI. |
- Source:
Returns:
Value of comparison predicate on a and b.
(static) copy(a, len)
Returns a copy of a, where the length of the
underlying array is len if this increases it.
Parameters:
| Name |
Type |
Description |
a |
|
Original array. |
len |
|
Length of resulting SLI if it is larger than the
length of the original SLI. |
- Source:
Returns:
Copy of original SLI.
(static) div_qr(q, a, b)
Computes q, r such that q = a / b + r with a / b and r
rounded with sign, in particular, if b is positive, then 0 <= r <
b. Then it sets a = r. We are faithful to the mathematical
definition for signs.
ASSUMES: a and b are positive, a has L words and at least L + 2
limbs (i.e., two leading unused zero words), b has L' limbs, and q
has at least L'' = max{L - L', L', 0} + 1 limbs and will finally
hold a result with at most L'' words and a leading zero limb.
Parameters:
| Name |
Type |
Description |
q |
|
SLI holding the quotient. |
a |
|
Dividend. |
b |
|
Divisor. |
- Source:
(static) egcd(a, b, v, x, y)
Sets a, b, and v such that a * x + b * y = v and v is
the greatest common divisor of x and y.
References: HAC 14.61 (5th printing + errata)
Parameters:
| Name |
Type |
Description |
a |
|
Linear coefficient of Bezout expression. |
b |
|
Linear coefficient of Bezout expression. |
v |
|
Greatest common divisor of x and y. |
x |
|
Left integer. |
y |
|
Right integer. |
- Source:
(static) egcd(w, x, p)
Sets a such that w * x = 1 mod p.
ASSUMES: p > 0 is on odd prime.
References: HAC 14.61
Parameters:
| Name |
Type |
Description |
w |
|
SLI holding the result. |
x |
|
Integer to invert. |
p |
|
Positive odd prime modulus. |
- Source:
(static) equals(a, b)
Returns true or false depending on if a = b or not.
Parameters:
| Name |
Type |
Description |
a |
|
Left SLI. |
b |
|
Right SLI. |
- Source:
Returns:
True or false depending on if the SLIs represent the same
integer or not.
(static) hex(a)
Returns a raw (no leading "0x" or similar) hexadecimal
representation of the input with sign indicated by a leading "-"
character if negative and capital characters.
Parameters:
| Name |
Type |
Description |
a |
|
SLI to represent. |
- Source:
Returns:
Hexadecimal representation of SLI.
(static) iszero(a)
Returns true or false depending on a = 1 or not.
Parameters:
| Name |
Type |
Description |
a |
|
Integer represented as a SLI. |
- Source:
Returns:
True or false depending on if a is zero or not.
(static) iszero(a)
Returns true or false depending on a = 0 or not.
Parameters:
| Name |
Type |
Description |
a |
|
Integer represented as a SLI. |
- Source:
Returns:
True or false depending on if a is zero or not.
(static) legendre(w, x, p)
Sets w to an integer such that w^2 = x mod p, i.e., it
computes the square root of an integer modulo a positive odd prime
employing the Shanks-Tonelli algorithm.
Parameters:
| Name |
Type |
Description |
w |
|
Holding the result. |
x |
|
Integer of which the square root is computed. |
p |
|
Positive odd prime modulus. |
- Source:
(static) legendre(a, b)
Returns (a | b), i.e., the Legendre symbol of a modulo
b for an odd prime b. (This is essentially a GCD algorithm that
keeps track of the symbol.)
References: HAC 2.149.
Parameters:
| Name |
Type |
Description |
a |
|
Integer modulo b. |
b |
|
An odd prime modulus. |
- Source:
Returns:
Legendre symbol of this instance modulo the input.
(static) mod(a, b, c)
Sets a = b mod c (this is merely syntactic sugar for
div_qr).
Parameters:
| Name |
Type |
Description |
a |
|
SLI holding the result. |
b |
|
Dividend. |
c |
|
Modulus. |
- Source:
(static) modpow(w, b, e, m)
Sets w = b^e mod m.
ASSUMES: b >= 0, e >= 0, and m >= 1, and w, b and m have L limbs.
Parameters:
| Name |
Type |
Description |
w |
|
SLI holding the result. |
b |
|
Basis integer. |
e |
|
Exponent. |
m |
|
Modulus. |
- Source:
(static) mul(a, b, c)
Sets a = b * c.
ASSUMES: b and c have L and L' limbs and a has at least L + L' limbs.
Parameters:
| Name |
Type |
Description |
a |
|
SLI holding the result. |
b |
|
Left factor. |
c |
|
Right factor. |
- Source:
(static) mul_number(a, b, c)
Sets a = b * c, where c is a Javascript "number".
ASSUMES: b has L limbs, c is a Javascript "number" such that 0 <=
|c| < 2^28, and a has at least L + 1 limbs.
Parameters:
| Name |
Type |
Description |
a |
|
SLI holding the result. |
b |
|
Left factor. |
c |
|
Right factor. |
- Source:
(static) normalize(x, mask_top)
Truncates the input to the shortest possible array
that represents the same absolute value in two's complement, i.e.,
there is always a leading zero bit.
Parameters:
| Name |
Type |
Description |
x |
|
Array to be truncated. |
mask_top |
|
Word used to normalize. |
- Source:
(static) resize(a, len)
Resizes the underlying array to the given length.
Parameters:
| Name |
Type |
Description |
a |
|
SLI to be resized. |
len |
|
New length of SLI. |
- Source:
(static) set(a, b)
Sets a = b, where b may be an SLI instance or a
"number"
ASSUMES: b has L words and a has at least L limbs. If b is a
"number", then it is assumed that 0 <= |b| < 2^28.
Parameters:
| Name |
Type |
Description |
a |
|
SLI holding the result. |
b |
|
Integer value represented as a SLI or Javascript "number". |
- Source:
(static) shiftleft(x, offset)
Shifts the given number of bits within the SLI,
i.e., the allocated space is not expanded.
ASSUMES: offset >= 0.
Parameters:
| Name |
Type |
Description |
x |
|
SLI to be shifted. |
offset |
|
Number of bit positions to shift. |
- Source:
(static) shiftright(x, offset)
Shifts the given number of bits to the right within
the allocated space, i.e., the space is not reduced.
ASSUMES: offset >= 0.
Parameters:
| Name |
Type |
Description |
x |
|
SLI to be shifted. |
offset |
|
Number of bit positions to shift. |
- Source:
(static) sign(n)
Returns the sign of a number.
Parameters:
| Name |
Type |
Description |
n |
|
A Javascript "number". |
- Source:
Returns:
Sign of number as -1, 0, or 1.
(static) square(a, b)
Sets a = b^2.
ASSUMES: b has L words and a has at least 2 * L limbs.
Parameters:
| Name |
Type |
Description |
a |
|
SLI holding the result. |
b |
|
Factor. |
- Source:
(static) sub(a, b, c)
Sets a = b - c.
ASSUMES: b and c have B and B' bits and a can store B + B' + 1
bits, or B + B' bits depending on if the signs of b and c are
distinct or not.
Parameters:
| Name |
Type |
Description |
a |
|
SLI holding the result. |
b |
|
Left term. |
c |
|
Right term. |
- Source: