pyecsca.ec.scalar module¶
Provides functions for computing various scalar representations (like NAF, or different bases).
- wnaf(k, w)[source]¶
Compute width w NAF (Non-Adjacent Form) of the scalar k.
Algorithm 9.35 from [GECC], Algorithm 9.20 from [HEHCC].
Note
According to HEHCC this is actually not unique
A left-to-right variant to compute an NAFw expansion of an integer can be found both in [AVA 2005a] and in [MUST 2005]. The result may differ from the expansion produced by Algorithm 9.20 but they have the same digit set and the same optimal weight.
According to GECC it is.
- naf(k)[source]¶
Compute the NAF (Non-Adjacent Form) of the scalar k.
- Properties ([GECC] 3.29):
k has a unique NAF denoted NAF(k).
NAF(k) has the fewest non-zero digits of any signed digit representation of k.
The length of NAF(k) is at most one more than the bit-length of k.
If the length of NAF(k) is l, then $2^l / 3 < k < 2^(l+1) / 3$.
The average density of non-zero digits among all NAFs of length l is approximately 1/3.
- Parameters:
k¶ (
int
) – The scalar.- Return type:
List
[int
]- Returns:
The NAF.
- booth(k)[source]¶
Original Booth binary recoding, from [B51].
- Parameters:
k¶ (
int
) – The scalar to recode.- Return type:
List
[int
]- Returns:
The recoded list of digits (0, 1, -1), little-endian.