#
# number.py : Number-theoretic functions
#
# Part of the Python Cryptography Toolkit
#
# Written by Andrew M. Kuchling, Barry A. Warsaw, and others
#
# ===================================================================
# The contents of this file are dedicated to the public domain. To
# the extent that dedication to the public domain is not available,
# everyone is granted a worldwide, perpetual, royalty-free,
# non-exclusive license to exercise all rights associated with the
# contents of this file for any purpose whatsoever.
# No rights are reserved.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
# ===================================================================
#
import math
import sys
import struct
from Cryptodome import Random
from Cryptodome.Util.py3compat import _memoryview, iter_range
# Backward compatibility
_fastmath = None
def ceil_div(n, d):
"""Return ceil(n/d), that is, the smallest integer r such that r*d >= n"""
if d == 0:
raise ZeroDivisionError()
if (n < 0) or (d < 0):
raise ValueError("Non positive values")
r, q = divmod(n, d)
if (n != 0) and (q != 0):
r += 1
return r
def size (N):
"""Returns the size of the number N in bits."""
if N < 0:
raise ValueError("Size in bits only avialable for non-negative numbers")
bits = 0
while N >> bits:
bits += 1
return bits
def getRandomInteger(N, randfunc=None):
"""Return a random number at most N bits long.
If :data:`randfunc` is omitted, then :meth:`Random.get_random_bytes` is used.
.. deprecated:: 3.0
This function is for internal use only and may be renamed or removed in
the future. Use :func:`Cryptodome.Random.random.getrandbits` instead.
"""
if randfunc is None:
randfunc = Random.get_random_bytes
S = randfunc(N>>3)
odd_bits = N % 8
if odd_bits != 0:
rand_bits = ord(randfunc(1)) >> (8-odd_bits)
S = struct.pack('B', rand_bits) + S
value = bytes_to_long(S)
return value
def getRandomRange(a, b, randfunc=None):
"""Return a random number *n* so that *a <= n < b*.
If :data:`randfunc` is omitted, then :meth:`Random.get_random_bytes` is used.
.. deprecated:: 3.0
This function is for internal use only and may be renamed or removed in
the future. Use :func:`Cryptodome.Random.random.randrange` instead.
"""
range_ = b - a - 1
bits = size(range_)
value = getRandomInteger(bits, randfunc)
while value > range_:
value = getRandomInteger(bits, randfunc)
return a + value<